Subgraph Sampling Methods for Social Networks: The Good, the Bad, and the Ugly
Résumé
The trajectories of social processes (e.g., peer pressure, imitation, and assimilation) that take place on social networks depend on the structure of those networks. Thus, to understand a social process or to predict the associated outcomes accurately, marketers would need good knowledge of the social network structure. However, many social networks of relevance to marketers are large, complex, or hidden, making it prohibitively expensive to map out an entire social network. Instead, marketers often need to work with a sample (i.e., a subgraph) of a social network. In this paper we evaluate the efficacy of nine different sampling methods for generating subgraphs that recover four structural characteristics of importance to marketers, namely, the distributions of degree, clustering coefficient, betweenness centrality, and closeness centrality, which are important for understanding how social network structure influences outcomes of processes that take place on the network.
Via extensive simulations, we find that sampling methods differ substantially in their ability to recover network characteristics. Traditional sampling procedures, such as random node sampling, result in poor subgraphs. When the focus is on understanding local network effects (e.g., peer influence) then forest fire sampling with a medium burn rate performs the best, i.e., it is most effective for recovering the distributions of degree and clustering coefficient. When the focus is on global network effects (e.g., speed of diffusion, identifying influential nodes, or the “multiplier” effects of network seeding), then random-walk sampling (i.e., forest-fire sampling with a low burn rate) performs the best, and it is most effective for recovering the distributions of betweenness and closeness centrality. Further, we show that accurate recovery of social network structure in a sample is important for inferring the properties of a network process, when one observes only the process in the sampled network. We validate our findings on four different real-world networks, including a Facebook network and a co-authorship network, and conclude with recommendations for practice.