Spreading paths in partially observed social networks

Abstract

Understanding how and how far information, behaviors, or pathogens spread in social networks is an important problem, having implications for both predicting the size of epidemics, as well as for planning effective interventions. There are, however, two main challenges for inferring spreading paths in real-world networks. One is the practical difficulty of observing a dynamic process on a network, and the other is the typical constraint of only partially observing a network. Using a static, structurally realistic social network as a platform for simulations, we juxtapose three distinct paths: (1) the stochastic path taken by a simulated spreading process from source to target; (2) the topologically shortest path in the fully observed network, and hence the single most likely stochastic path, between the two nodes; and (3) the topologically shortest path in a partially observed network. In a sampled network, how closely does the partially observed shortest path (3) emulate the unobserved spreading path (1)? Although partial observation inflates the length of the shortest path, the stochastic nature of the spreading process also frequently derails the dynamic path from the shortest path. We find that the partially observed shortest path does not necessarily give an inflated estimate of the length of the process path; in fact, partial observation may, counterintuitively, make the path seem shorter than it actually is.

12 pages, 9 figures, 1 table

References in corpus (12)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Understanding individual human mobility patterns
• Structure and tie strengths in mobile communication networks
• Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
• Social Network Sensors for Early Detection of Contagious Outbreaks
• Path lengths, correlations, and centrality in temporal networks
• Analysis of a large-scale weighted network of one-to-one human communication
• Modeling social networks from sampled data
• Information dynamics shape the networks of Internet-mediated prostitution
• Emergence of communities in weighted networks
• Describing and Simulating Internet Routes

Cited by in corpus (10)

• Compensating for population sampling in simulations of epidemic spread on temporal contact networks
• Social Contagion Theory: Examining Dynamic Social Networks and Human Behavior
• Epidemic risk from friendship network data: an equivalence with a non-uniform sampling of contact networks
• Bayesian Discovery of Threat Networks
• Network Detection Theory and Performance
• Impact of spatially constrained sampling of temporal contact networks on the evaluation of the epidemic risk
• Inferring propagation paths for sparsely observed perturbations on complex networks
• Dynamical phase transition due to preferential cluster growth of collective emotions in online communities
• A survey of results on mobile phone datasets analysis
• Causal Effects with Hidden Treatment Diffusion on Observed or Partially Observed Networks