Inference on social graphs

Heterogeneous media and controls

September 22, 2019 β€” June 3, 2020


Fun keywords: Egocentric sampling, graph sampling, friendship paradox, majority illusion, and the analysis of projectivity. πŸ—

Figure 1

1 Majority Illusions and filter bubbles

Figure 2

In homophilic networks (0.5 ≀ h ≀ 1), the minority overestimates their own size (filter bubble) and the majority underestimates the size of the minority. The insets show the same information on log scale to make the amount of underestimation and overestimation comparable. As group sizes become more disproportionate, perception bias increases. (Lerman, Yan, and Wu 2016)

This insight is one of those ones that seems trivial in hindsight, but people are terrible at articulating in advance. Related, perhaps a consequence of this, is pluralistic ignorance

Figure 3

2 Confounding on graphs

Cosma Shalizi, Return of β€œHomophily, Contagion, Confounding: Pick Any Three”, or, The Adventures of Irene and Joey Along the Back-Door Paths and sequel. and Experiments on Social Networks. See also his Neutral cultural networks stuff.

My colleague at UNSW, Pavel Krivitsky is highly productive in this area, especially with the exponential family random graph (pronounced β€œergum”.) model, and I will list the articles he wrote so that I can pester him for details: (Hunter, Krivitsky, and Schweinberger 2012; Kolaczyk and Krivitsky 2015; Krivitsky and Morris 2017; Krivitsky et al. 2009; Krivitsky and Handcock 2014)

3 Incoming

Michele Coscia. Michele Coscia’s new paper uses a graph Laplacian to calculate an approximate Earth mover distance over a graph topology. (buzzword use case: inferring graph transmission rate of a disease interpretably). This looks simple; surely it must be a known result in optimal transport metric studies?

For models, specifically, of actual disease contagion, see Shalizi’s review of Kiss, Miller, and Simon (2017).

4 References

Acemoglu, and Ozdaglar. 2011. β€œOpinion Dynamics and Learning in Social Networks.” Dynamic Games and Applications.
Achlioptas, Clauset, Kempe, et al. 2005. β€œOn the Bias of Traceroute Sampling: Or, Power-Law Degree Distributions in Regular Graphs.” In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing. STOC ’05.
Aral, Muchnik, and Sundararajan. 2009. β€œDistinguishing Influence-Based Contagion from Homophily-Driven Diffusion in Dynamic Networks.” Proceedings of the National Academy of Sciences.
Baker, Biazzo, Braunstein, et al. 2021. β€œEpidemic Mitigation by Statistical Inference from Contact Tracing Data.” Proceedings of the National Academy of Sciences.
Bakshy, Rosenn, Marlow, et al. 2012. β€œThe Role of Social Networks in Information Diffusion.” In Proceedings of the 21st International Conference on World Wide Web. WWW ’12.
Barbieri, Bonchi, and Manco. 2013. β€œCascade-Based Community Detection.” In Proceedings of the Sixth ACM International Conference on Web Search and Data Mining. WSDM ’13.
Bonchi, Gullo, Mishra, et al. 2018. β€œProbabilistic Causal Analysis of Social Influence.” In Proceedings of the 27th ACM International Conference on Information and Knowledge Management. CIKM ’18.
Bond, Fariss, Jones, et al. 2012. β€œA 61-Million-Person Experiment in Social Influence and Political Mobilization.” Nature.
Braunstein, and Ingrosso. 2016. β€œInference of Causality in Epidemics on Temporal Contact Networks.” Scientific Reports.
Cai, Campbell, and Broderick. 2016. β€œEdge-Exchangeable Graphs and Sparsity.” In Proceedings of the 30th International Conference on Neural Information Processing Systems. NIPS’16.
Cha, Haddadi, Benevenuto, et al. 2010. β€œMeasuring User Influence in Twitter: The Million Follower Fallacy.” In Fourth International AAAI Conference on Weblogs and Social Media.
Coscia. 2017. β€œPopularity Spikes Hurt Future Chances for Viral Propagation of Protomemes.” Communications of the ACM.
Costello, Srivastava, Rejaie, et al. 2021. β€œPredicting Mental Health From Followed Accounts on Twitter.” Collabra: Psychology.
Crane, and Dempsey. 2016. β€œA Framework for Statistical Network Modeling.” arXiv:1509.08185 [Math, Stat].
β€”β€”β€”. 2018. β€œEdge Exchangeable Models for Interaction Networks.” Journal of the American Statistical Association.
β€”β€”β€”. 2019. β€œRelational Exchangeability.” Journal of Applied Probability.
Cranmer, Desmarais, and Morgan. 2021. Inferential network analysis.
DiTraglia, Garcia-Jimeno, O’Keeffe-O’Donovan, et al. 2020. β€œIdentifying Causal Effects in Experiments with Social Interactions and Non-Compliance.” arXiv:2011.07051 [Econ, Stat].
Dodds, and Watts. 2005. β€œA Generalized Model of Social and Biological Contagion.” Journal of Theoretical Biology.
Draves, and Sussman. 2020. β€œBias-Variance Tradeoffs in Joint Spectral Embeddings.” arXiv:2005.02511 [Math, Stat].
Elwert, and Winship. 2014. β€œEndogenous Selection Bias: The Problem of Conditioning on a Collider Variable.” Annual Review of Sociology.
Gelman, and Margalit. 2021. β€œSocial Penumbras Predict Political Attitudes.” Proceedings of the National Academy of Sciences.
Goel, Anderson, Hofman, et al. 2015. β€œThe Structural Virality of Online Diffusion.” Management Science.
Golub, and Jackson. 2011. β€œNetwork Structure and the Speed of Learning: Measuring Homophily Based on Its Consequences.” SSRN Scholarly Paper ID 1784542.
Gomez-Rodriguez, Leskovec, and Krause. 2012. β€œInferring Networks of Diffusion and Influence.” ACM Trans. Knowl. Discov. Data.
Gonzalez-Bailon. 2009. β€œOpening the Black Box of Link Formation: Social Factors Underlying the Structure of the Web.” Social Networks.
Goyal, Bonchi, and Lakshmanan. 2010. β€œLearning Influence Probabilities in Social Networks.” In Proceedings of the Third ACM International Conference on Web Search and Data Mining. WSDM ’10.
Goyal, Bonchi, and Lakshmanan. 2011. β€œA Data-Based Approach to Social Influence Maximization.” In Proc. VLDB Endow.
Greenland, and Robins. 2009. β€œIdentifiability, Exchangeability and Confounding Revisited.” Epidemiologic Perspectives & Innovations : EP+I.
Green, and Shalizi. 2017. β€œBootstrapping Exchangeable Random Graphs.” arXiv:1711.00813 [Stat].
Guille, Hacid, Favre, et al. 2013. β€œInformation Diffusion in Online Social Networks: A Survey.” SIGMOD Rec.
Harris. 2013. An Introduction to Exponential Random Graph Modeling.
Hunter, Krivitsky, and Schweinberger. 2012. β€œComputational Statistical Methods for Social Network Models.” Journal of Computational and Graphical Statistics.
Iribarren, and Moro. 2009. β€œImpact of Human Activity Patterns on the Dynamics of Information Diffusion.” Physical Review Letters.
Jackson, Matthew O. 2008. Social and Economic Networks.
Jackson, Matthew O. 2009. β€œSocial Structure, Segregation, and Economic Behavior.” Presented as the Nancy Schwartz Memorial Lecture.
β€”β€”β€”. 2014. β€œNetworks in the Understanding of Economic Behaviors.” Journal of Economic Perspectives.
β€”β€”β€”. 2018. β€œThe Friendship Paradox and Systematic Biases in Perceptions and Social Norms.” Journal of Political Economy.
Jaeger, and Schulte. 2021. β€œA Complete Characterization of Projectivity for Statistical Relational Models.” In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. IJCAI’20.
Kempe, Kleinberg, and Tardos. 2003. β€œMaximizing the Spread of Influence Through a Social Network.” In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’03.
Kiss, Miller, and Simon. 2017. Mathematics of Epidemics on Networks: From Exact to Approximate Models. Interdisciplinary Applied Mathematics.
Kitsak. n.d. β€œIdentifying Influential Spreaders in Complex Networks.”
Kolaczyk, and Krivitsky. 2015. β€œOn the Question of Effective Sample Size in Network Modeling: An Asymptotic Inquiry.” Statistical Science : A Review Journal of the Institute of Mathematical Statistics.
Krivitsky, and Handcock. 2014. β€œA Separable Model for Dynamic Networks.” Journal of the Royal Statistical Society: Series B (Statistical Methodology).
Krivitsky, Handcock, Raftery, et al. 2009. β€œRepresenting Degree Distributions, Clustering, and Homophily in Social Networks with Latent Cluster Random Effects Models.” Social Networks.
Krivitsky, and Morris. 2017. β€œInference For Social Network Models From Egocentrically Sampled Data, With Application To Understanding Persistent Racial Disparities In Hiv Prevalence In The Us.” The Annals of Applied Statistics.
Laga, Bao, and Niu. 2020. β€œThirty Years of The Network Scale up Method.” arXiv:2011.12516 [Stat].
Lee, Karimi, Jo, et al. 2017. β€œHomophily Explains Perception Biases in Social Networks.” arXiv:1710.08601 [Physics].
Lerman, Yan, and Wu. 2016. β€œThe β€˜Majority Illusion’ in Social Networks.” PLOS ONE.
Leskovec. 2012. β€œInformation Diffusion and External Influence in Networks.” Eprint arXiv:1206.1331.
Levin, Athreya, Tang, et al. 2019. β€œA Central Limit Theorem for an Omnibus Embedding of Multiple Random Graphs and Implications for Multiscale Network Inference.” arXiv:1705.09355 [Stat].
Lin, Lunde, and Sarkar. 2020. β€œOn the Theoretical Properties of the Network Jackknife.” arXiv:2004.08935 [Math, Stat].
Li, Qian, Levina, et al. 2020. β€œHigh-Dimensional Gaussian Graphical Models on Network-Linked Data.” Journal of Machine Learning Research.
Liu, King, and Bearman. 2010. β€œSocial Influence and the Autism Epidemic.” American Journal of Sociology.
Lyons. 2011. β€œThe Spread of Evidence-Poor Medicine via Flawed Social-Network Analysis.” Statistics, Politics, and Policy.
Madar, Kalisky, Cohen, et al. 2004. β€œImmunization and Epidemic Dynamics in Complex Networks.” The European Physical Journal B.
Malinsky, Shpitser, and Richardson. 2019. β€œA Potential Outcomes Calculus for Identifying Conditional Path-Specific Effects.” arXiv:1903.03662 [Stat].
Morozova, Cohen, and Crawford. 2018. β€œRisk Ratios for Contagious Outcomes.” Journal of The Royal Society Interface.
Noel, and Nyhan. 2011. β€œThe β€˜Unfriending’ Problem: The Consequences of Homophily in Friendship Retention for Causal Estimates of Social Influence.” Social Networks.
Olteanu, Castillo, Diaz, et al. 2019. β€œSocial Data: Biases, Methodological Pitfalls, and Ethical Boundaries.” Frontiers in Big Data.
Onnela, and Reed-Tsochas. 2010. β€œSpontaneous Emergence of Social Influence in Online Systems.” Proceedings of the National Academy of Sciences.
Orbanz, and Roy. 2015. β€œBayesian Models of Graphs, Arrays and Other Exchangeable Random Structures.” IEEE Transactions on Pattern Analysis and Machine Intelligence.
Ormerod. 2006. β€œHayek, the Intellectuals and Socialism, and Weighted Scale-Free Networks.” Economic Affairs.
Pastor-Satorras, Castellano, Van Mieghem, et al. 2015. β€œEpidemic Processes in Complex Networks.” Reviews of Modern Physics.
Pastor-Satorras, and Vespignani. 2002. β€œImmunization of Complex Networks.” Physical Review E.
Patone, and Zhang. 2020. β€œIncidence Weighting Estimation Under Bipartite Incidence Graph Sampling.” arXiv:2004.04257 [Math, Stat].
Pattison, Robins, Snijders, et al. 2013. β€œConditional Estimation of Exponential Random Graph Models from Snowball Sampling Designs.” Journal of Mathematical Psychology, Social Networks,.
Pinto, and Chahed. 2014. β€œModeling Multi-Topic Information Diffusion in Social Networks Using Latent Dirichlet Allocation and Hawkes Processes.” In Proceedings of the 2014 Tenth International Conference on Signal-Image Technology and Internet-Based Systems. SITIS ’14.
Rehkopf, Glymour, and Osypuk. 2016. β€œThe Consistency Assumption for Causal Inference in Social Epidemiology: When a Rose Is Not a Rose.” Current Epidemiology Reports.
Robins. 2015. Doing Social Network Research: Network-Based Research Design for Social Scientists.
Saichev, and Sornette. 2011. β€œHierarchy of Temporal Responses of Multivariate Self-Excited Epidemic Processes.” arXiv:1101.1611 [Cond-Mat, Physics:physics].
Salamanos, Voudigari, and Yannakoudakis. n.d. β€œDeterministic Graph Exploration for Efficient Graph Sampling.” Social Network Analysis and Mining.
Sanguiao Sande, and Zhang. 2020. β€œDesign-Unbiased Statistical Learning in Survey Sampling.” Sankhya: The Indian Journal of Statistics.
Schweinberger. 2020. β€œConsistent Structure Estimation of Exponential-Family Random Graph Models with Block Structure.” Bernoulli.
Seshadhri, Sharma, Stolman, et al. 2020. β€œThe Impossibility of Low-Rank Representations for Triangle-Rich Complex Networks.” Proceedings of the National Academy of Sciences.
Shalizi, and McFowland III. 2016. β€œControlling for Latent Homophily in Social Networks Through Inferring Latent Locations.” arXiv:1607.06565 [Physics, Stat].
Shalizi, and Rinaldo. 2013. β€œConsistency Under Sampling of Exponential Random Graph Models.” Annals of Statistics.
Shalizi, and Thomas. 2011. β€œHomophily and Contagion Are Generically Confounded in Observational Social Network Studies.” Sociological Methods & Research.
Sharma, Hofman, and Watts. 2015. β€œEstimating the Causal Impact of Recommendation Systems from Observational Data.” Proceedings of the Sixteenth ACM Conference on Economics and Computation - EC ’15.
Snijders, Tom A. B. 2010. β€œConditional Marginalization for Exponential Random Graph Models.” The Journal of Mathematical Sociology.
Snijders, Tom A.B. 2011. β€œStatistical Models for Social Networks.” Annual Review of Sociology.
Stewart, Arif, and Starbird. 2018. β€œExamining Trolls and Polarization with a Retweet Network.”
Stumpf, Wiuf, and May. 2005. β€œSubnets of Scale-Free Networks Are Not Scale-Free: Sampling Properties of Networks.” Proceedings of the National Academy of Sciences of the United States of America.
Valente. 2012. β€œNetwork Interventions.” Science.
Valente, and Pitts. 2017. β€œAn Appraisal of Social Network Theory and Analysis as Applied to Public Health: Challenges and Opportunities.” Annual Review of Public Health.
Vega-Oliveros. n.d. β€œInfluence Maximization Based on the Least Influential Spreaders.”
Venkatasubramanian, Scheidegger, Friedler, et al. 2021. β€œFairness in Networks: Social Capital, Information Access, and Interventions.” In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. KDD ’21.
Watts. 2014. β€œCommon Sense and Sociological Explanations.” American Journal of Sociology.
Watts, and Dodds. 2007. β€œInfluentials, Networks, and Public Opinion Formation.” Journal of Consumer Research.
Wu, Olhede, and Wolfe. 2020. β€œTractably Modelling Dependence in Networks Beyond Exchangeability.” arXiv:2007.14365 [Math, Stat].
Yang, Long, Smola, et al. 2011. β€œLike Like Alike: Joint Friendship and Interest Propagation in Social Networks.” In Proceedings of the 20th International Conference on World Wide Web. WWW ’11.
Yannakoudakis, Voudigari, and Salamanos. 2020. β€œIdentifying Influential Spreaders by Graph Sampling.” Salamanos N, Voudigari E, Yannakoudakis EJ (2016) Identifying Influential Spreaders by Graph Sampling. In: Proceedings of the 5th International Workshop on Complex Networks and Their Applications, Milan, Italy, November 30 - December 02, 2016.
Zafarani, Abbasi, and Liu. 2014. Social Media Mining: An Introduction.
Zarezade, Upadhyay, Rabiee, et al. 2017. β€œRedQueen: An Online Algorithm for Smart Broadcasting in Social Networks.” In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining. WSDM ’17.
Zhang, Li-Chun, and Nguyen. 2020. β€œAn Appraisal of Common Reweighting Methods for Nonresponse in Household Surveys Based on Norwegian Labour Force Survey and Statistics on Income and Living Conditions Survey.” Journal of Official Statistics.
Zhang, Li-Chun, and Oguz-Alper. 2020. β€œBIG Sampling.” arXiv:2003.09467 [Math, Stat].
Zhang, L.-C., and Patone. 2017. β€œGraph Sampling.” METRON.
Zheleva, and Arbour. 2021. β€œCausal Inference from Network Data.” In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. KDD ’21.
Zhou, Hofmann, and SchΓΆlkopf. n.d. β€œSemi-Supervised Learning on Directed Graphs.”