Inference on social graphs

Heterogeneous media and controls


Fun keywords: Egocentric sampling, graph sampling, friendship paradox, majority illusion, and the analysis of projectivity. 🏗

Majority Illusions and filter bubbles

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

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 here 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)

To file

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).


Acemoglu, Daron, and Asuman Ozdaglar. 2011. “Opinion Dynamics and Learning in Social Networks.” Dynamic Games and Applications 1 (1): 3–49.
Achlioptas, Dimitris, Aaron Clauset, David Kempe, and Cristopher Moore. 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, 694–703. STOC ’05. New York, NY, USA: ACM.
Aral, Sinan, Lev Muchnik, and Arun Sundararajan. 2009. “Distinguishing Influence-Based Contagion from Homophily-Driven Diffusion in Dynamic Networks.” Proceedings of the National Academy of Sciences 106 (51): 21544–49.
Baker, Antoine, Indaco Biazzo, Alfredo Braunstein, Giovanni Catania, Luca Dall’Asta, Alessandro Ingrosso, Florent Krzakala, et al. 2021. “Epidemic Mitigation by Statistical Inference from Contact Tracing Data.” Proceedings of the National Academy of Sciences 118 (32).
Bakshy, Eytan, Itamar Rosenn, Cameron Marlow, and Lada Adamic. 2012. “The Role of Social Networks in Information Diffusion.” In Proceedings of the 21st International Conference on World Wide Web, 519–28. WWW ’12. New York, NY, USA: ACM.
Barbieri, Nicola, Francesco Bonchi, and Giuseppe Manco. 2013. “Cascade-Based Community Detection.” In Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, 33–42. WSDM ’13. New York, NY, USA: ACM.
Bonchi, Francesco, Francesco Gullo, Bud Mishra, and Daniele Ramazzotti. 2018. “Probabilistic Causal Analysis of Social Influence.” In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, 1003–12. CIKM ’18. New York, NY, USA: ACM.
Bond, Robert M., Christopher J. Fariss, Jason J. Jones, Adam D. I. Kramer, Cameron Marlow, Jaime E. Settle, and James H. Fowler. 2012. “A 61-Million-Person Experiment in Social Influence and Political Mobilization.” Nature 489 (7415): 295–98.
Braunstein, Alfredo, and Alessandro Ingrosso. 2016. “Inference of Causality in Epidemics on Temporal Contact Networks.” Scientific Reports 6 (1): 27538.
Cai, Diana, Trevor Campbell, and Tamara Broderick. 2016. “Edge-Exchangeable Graphs and Sparsity.” In Proceedings of the 30th International Conference on Neural Information Processing Systems, 4249–57. NIPS’16. USA: Curran Associates Inc.
Cha, Meeyoung, Hamed Haddadi, Fabricio Benevenuto, and Krishna P. Gummadi. 2010. “Measuring User Influence in Twitter: The Million Follower Fallacy.” In Fourth International AAAI Conference on Weblogs and Social Media.
Coscia, Michele. 2017. “Popularity Spikes Hurt Future Chances for Viral Propagation of Protomemes.” Communications of the ACM 61 (1): 70–77.
Costello, Cory, Sanjay Srivastava, Reza Rejaie, and Maureen Zalewski. 2021. “Predicting Mental Health From Followed Accounts on Twitter.” Collabra: Psychology 7 (18731).
Crane, Harry, and Walter Dempsey. 2016. “A Framework for Statistical Network Modeling.” arXiv:1509.08185 [math, Stat], December.
———. 2018. “Edge Exchangeable Models for Interaction Networks.” Journal of the American Statistical Association 113 (523): 1311–26.
———. 2019. “Relational Exchangeability.” Journal of Applied Probability 56 (1): 192–208.
Cranmer, Skyler J, Bruce A Desmarais, and Jason W Morgan. 2021. Inferential network analysis.
DiTraglia, Francis J., Camilo Garcia-Jimeno, Rossa O’Keeffe-O’Donovan, and Alejandro Sanchez-Becerra. 2020. “Identifying Causal Effects in Experiments with Social Interactions and Non-Compliance.” arXiv:2011.07051 [econ, Stat], November.
Dodds, Peter Sheridan, and Duncan J. Watts. 2005. “A Generalized Model of Social and Biological Contagion.” Journal of Theoretical Biology 232 (4): 587–604.
Draves, Benjamin, and Daniel L. Sussman. 2020. “Bias-Variance Tradeoffs in Joint Spectral Embeddings.” arXiv:2005.02511 [math, Stat], May.
Elwert, Felix, and Christopher Winship. 2014. “Endogenous Selection Bias: The Problem of Conditioning on a Collider Variable.” Annual Review of Sociology 40 (1): 31–53.
Gelman, Andrew, and Yotam Margalit. 2021. “Social Penumbras Predict Political Attitudes.” Proceedings of the National Academy of Sciences 118 (6).
Goel, Sharad, Ashton Anderson, Jake Hofman, and Duncan J. Watts. 2015. “The Structural Virality of Online Diffusion.” Management Science, July, 150722112809007.
Golub, Benjamin, and Matthew O. Jackson. 2011. “Network Structure and the Speed of Learning: Measuring Homophily Based on Its Consequences.” SSRN Scholarly Paper ID 1784542. Rochester, NY: Social Science Research Network.
Gomez-Rodriguez, Manuel, Jure Leskovec, and Andreas Krause. 2012. “Inferring Networks of Diffusion and Influence.” ACM Trans. Knowl. Discov. Data 5 (4): 21:1–37.
Gonzalez-Bailon, Sandra. 2009. “Opening the Black Box of Link Formation: Social Factors Underlying the Structure of the Web.” Social Networks 31 (4): 271–80.
Goyal, Amit, Francesco Bonchi, and Laks V.S. Lakshmanan. 2010. “Learning Influence Probabilities in Social Networks.” In Proceedings of the Third ACM International Conference on Web Search and Data Mining, 241–50. WSDM ’10. New York, NY, USA: ACM.
Goyal, Amit, Francesco Bonchi, and Laks V. S. Lakshmanan. 2011. “A Data-Based Approach to Social Influence Maximization.” In Proc. VLDB Endow., 5:73–84.
Green, Alden, and Cosma Rohilla Shalizi. 2017. “Bootstrapping Exchangeable Random Graphs.” arXiv:1711.00813 [stat], November.
Greenland, Sander, and James M Robins. 2009. “Identifiability, Exchangeability and Confounding Revisited.” Epidemiologic Perspectives & Innovations : EP+I 6 (September): 4.
Guille, Adrien, Hakim Hacid, Cecile Favre, and Djamel A. Zighed. 2013. “Information Diffusion in Online Social Networks: A Survey.” SIGMOD Rec. 42 (2): 17–28.
Harris, Jenine K. 2013. An Introduction to Exponential Random Graph Modeling. SAGE Publications.
Hunter, David R., Pavel N. Krivitsky, and Michael Schweinberger. 2012. “Computational Statistical Methods for Social Network Models.” Journal of Computational and Graphical Statistics 21 (4): 856–82.
Iribarren, Jose Luis, and Esteban Moro. 2009. “Impact of Human Activity Patterns on the Dynamics of Information Diffusion.” Physical Review Letters 103 (3): 038702.
Jackson, Matthew O. 2008. Social and Economic Networks. Princeton University Press.
Jackson, Matthew O. 2009. “Social Structure, Segregation, and Economic Behavior.” Presented as the Nancy Schwartz Memorial Lecture, February.
———. 2014. “Networks in the Understanding of Economic Behaviors.” Journal of Economic Perspectives 28 (4): 3–22.
———. 2018. “The Friendship Paradox and Systematic Biases in Perceptions and Social Norms.” Journal of Political Economy 127 (2): 777–818.
Jaeger, Manfred, and Oliver Schulte. 2020. “A Complete Characterization of Projectivity for Statistical Relational Models.” arXiv:2004.10984 [cs, Stat], April.
Kempe, David, Jon Kleinberg, and Éva 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, 137–46. KDD ’03. New York, NY, USA: ACM.
Kiss, István Z., Joel Miller, and Péter L. Simon. 2017. Mathematics of Epidemics on Networks: From Exact to Approximate Models. Interdisciplinary Applied Mathematics. New York, NY: Springer International Publishing.
Kitsak, Maksim. n.d. “Identifying Influential Spreaders in Complex Networks.” Accessed June 24, 2019.
Kolaczyk, Eric D., and Pavel N. 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 30 (2): 184–98.
Krivitsky, Pavel N., and Mark S. Handcock. 2014. “A Separable Model for Dynamic Networks.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 76 (1): 29–46.
Krivitsky, Pavel N., Mark S. Handcock, Adrian E. Raftery, and Peter D. Hoff. 2009. “Representing Degree Distributions, Clustering, and Homophily in Social Networks with Latent Cluster Random Effects Models.” Social Networks 31 (3): 204–13.
Krivitsky, Pavel N., and Martina 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 11 (1): 427–55.
Laga, Ian, Le Bao, and Xiaoyue Niu. 2020. “Thirty Years of The Network Scale up Method.” arXiv:2011.12516 [stat], November.
Lee, Eun, Fariba Karimi, Hang-Hyun Jo, Markus Strohmaier, and Claudia Wagner. 2017. “Homophily Explains Perception Biases in Social Networks.” arXiv:1710.08601 [physics], October.
Lerman, Kristina, Xiaoran Yan, and Xin-Zeng Wu. 2016. “The ‘Majority Illusion’ in Social Networks.” PLOS ONE 11 (2): e0147617.
Leskovec, Jure. 2012. “Information Diffusion and External Influence in Networks.” Eprint arXiv:1206.1331, June.
Levin, Keith, Avanti Athreya, Minh Tang, Vince Lyzinski, Youngser Park, and Carey E. Priebe. 2019. “A Central Limit Theorem for an Omnibus Embedding of Multiple Random Graphs and Implications for Multiscale Network Inference.” arXiv:1705.09355 [stat], June.
Li, Tianxi, Cheng Qian, Elizaveta Levina, and Ji Zhu. 2020. “High-Dimensional Gaussian Graphical Models on Network-Linked Data.” Journal of Machine Learning Research 21 (74): 1–45.
Lin, Qiaohui, Robert Lunde, and Purnamrita Sarkar. 2020. “On the Theoretical Properties of the Network Jackknife.” arXiv:2004.08935 [math, Stat], April.
Liu, Ka-Yuet, Marissa King, and Peter S. Bearman. 2010. “Social Influence and the Autism Epidemic.” American Journal of Sociology 115 (5): 1387.
Lyons, Russell. 2011. “The Spread of Evidence-Poor Medicine via Flawed Social-Network Analysis.” Statistics, Politics, and Policy 2 (1).
Madar, N., T. Kalisky, R. Cohen, D. ben-Avraham, and S. Havlin. 2004. “Immunization and Epidemic Dynamics in Complex Networks.” The European Physical Journal B 38 (2): 269–76.
Malinsky, Daniel, Ilya Shpitser, and Thomas Richardson. 2019. “A Potential Outcomes Calculus for Identifying Conditional Path-Specific Effects.” arXiv:1903.03662 [stat], March.
Morozova, Olga, Ted Cohen, and Forrest W. Crawford. 2018. “Risk Ratios for Contagious Outcomes.” Journal of The Royal Society Interface 15 (138): 20170696.
Noel, Hans, and Brendan Nyhan. 2011. “The ‘Unfriending’ Problem: The Consequences of Homophily in Friendship Retention for Causal Estimates of Social Influence.” Social Networks 33 (3): 211–18.
Olteanu, Alexandra, Carlos Castillo, Fernando Diaz, and Emre Kıcıman. 2019. “Social Data: Biases, Methodological Pitfalls, and Ethical Boundaries.” Frontiers in Big Data 2.
Onnela, J P, and Felix Reed-Tsochas. 2010. “Spontaneous Emergence of Social Influence in Online Systems.” Proceedings of the National Academy of Sciences 107 (43): 18375–80.
Orbanz, P., and D. M. Roy. 2015. “Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures.” IEEE Transactions on Pattern Analysis and Machine Intelligence 37 (2): 437–61.
Ormerod, Paul. 2006. “Hayek, the Intellectuals and Socialism, and Weighted Scale-Free Networks.” Economic Affairs 26: 41–47.
Pastor-Satorras, Romualdo, Claudio Castellano, Piet Van Mieghem, and Alessandro Vespignani. 2015. “Epidemic Processes in Complex Networks.” Reviews of Modern Physics 87 (3): 925–79.
Pastor-Satorras, Romualdo, and Alessandro Vespignani. 2002. “Immunization of Complex Networks.” Physical Review E 65 (3): 036104.
Patone, Martina, and Li-Chun Zhang. 2020. “Incidence Weighting Estimation Under Bipartite Incidence Graph Sampling.” arXiv:2004.04257 [math, Stat], April.
Pattison, Philippa E., Garry L. Robins, Tom A. B. Snijders, and Peng Wang. 2013. “Conditional Estimation of Exponential Random Graph Models from Snowball Sampling Designs.” Journal of Mathematical Psychology, Social Networks, 57 (6): 284–96.
Pinto, Julio Cesar Louzada, and Tijani 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, 339–46. SITIS ’14. Washington, DC, USA: IEEE Computer Society.
Rehkopf, David H., M. Maria Glymour, and Theresa L. Osypuk. 2016. “The Consistency Assumption for Causal Inference in Social Epidemiology: When a Rose Is Not a Rose.” Current Epidemiology Reports 3 (1): 63–71.
Saichev, A., and D. Sornette. 2011. “Hierarchy of Temporal Responses of Multivariate Self-Excited Epidemic Processes.” arXiv:1101.1611 [cond-Mat, Physics:physics], January.
Salamanos, Nikos, Elli Voudigari, and Emmanuel J. Yannakoudakis. n.d. “Deterministic Graph Exploration for Efficient Graph Sampling.” Social Network Analysis and Mining 7 (1). Accessed June 24, 2019.
Sanguiao Sande, Luis, and Li-Chun Zhang. 2020. “Design-Unbiased Statistical Learning in Survey Sampling.” Sankhya: The Indian Journal of Statistics, October.
Schweinberger, Michael. 2020. “Consistent structure estimation of exponential-family random graph models with block structure.” Bernoulli 26 (2): 1205–33.
Seshadhri, C., Aneesh Sharma, Andrew Stolman, and Ashish Goel. 2020. “The Impossibility of Low-Rank Representations for Triangle-Rich Complex Networks.” Proceedings of the National Academy of Sciences 117 (11): 5631–37.
Shalizi, Cosma Rohilla, and Edward McFowland III. 2016. “Controlling for Latent Homophily in Social Networks Through Inferring Latent Locations.” arXiv:1607.06565 [physics, Stat], July.
Shalizi, Cosma Rohilla, and Alessandro Rinaldo. 2013. “Consistency under sampling of exponential random graph models.” Annals of Statistics 41 (2): 508–35.
Shalizi, Cosma Rohilla, and Andrew C. Thomas. 2011. “Homophily and Contagion Are Generically Confounded in Observational Social Network Studies.” Sociological Methods & Research 40 (2): 211–39.
Sharma, Amit, Jake M. Hofman, and Duncan J. Watts. 2015. “Estimating the Causal Impact of Recommendation Systems from Observational Data.” Proceedings of the Sixteenth ACM Conference on Economics and Computation - EC ’15, 453–70.
Snijders, Tom A. B. 2010. “Conditional Marginalization for Exponential Random Graph Models.” The Journal of Mathematical Sociology 34 (4): 239–52.
Snijders, Tom A.B. 2011. “Statistical Models for Social Networks.” Annual Review of Sociology 37 (1): 131–53.
Stewart, Leo G, Ahmer Arif, and Kate Starbird. 2018. “Examining Trolls and Polarization with a Retweet Network,” 6.
Stumpf, Michael P. H., Carsten Wiuf, and Robert M. 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 102 (12): 4221–24.
Valente, Thomas W., and Stephanie R. Pitts. 2017. “An Appraisal of Social Network Theory and Analysis as Applied to Public Health: Challenges and Opportunities.” Annual Review of Public Health 38 (1): 103–18.
Vega-Oliveros, Didier. n.d. “Influence Maximization Based on the Least influential Spreaders.” Accessed June 24, 2019.
Venkatasubramanian, Suresh, Carlos Scheidegger, Sorelle Friedler, and Aaron Clauset. 2021. “Fairness in Networks: Social Capital, Information Access, and Interventions.” In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 4078–79. KDD ’21. New York, NY, USA: Association for Computing Machinery.
Watts, Duncan J. 2014. “Common Sense and Sociological Explanations.” American Journal of Sociology 120 (2): 313–51.
Watts, Duncan J., and Peter Sheridan Dodds. 2007. “Influentials, Networks, and Public Opinion Formation.” Journal of Consumer Research 34 (4): 441–58.
Wu, Weichi, Sofia Olhede, and Patrick Wolfe. 2020. “Tractably Modelling Dependence in Networks Beyond Exchangeability.” arXiv:2007.14365 [math, Stat], July.
Yang, Shuang-Hong, Bo Long, Alex Smola, Narayanan Sadagopan, Zhaohui Zheng, and Hongyuan Zha. 2011. “Like Like Alike: Joint Friendship and Interest Propagation in Social Networks.” In Proceedings of the 20th International Conference on World Wide Web, 537–46. WWW ’11. New York, NY, USA: ACM.
Yannakoudakis, Emmanuel J., Elli Voudigari, and Nikos 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, Reza, Mohammad Ali Abbasi, and Huan Liu. 2014. Social Media Mining: An Introduction. Cambridge University Press.
Zarezade, Ali, Utkarsh Upadhyay, Hamid R. Rabiee, and Manuel Gomez-Rodriguez. 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, 51–60. WSDM ’17. New York, NY, USA: ACM Press.
Zhang, L.-C., and M. Patone. 2017. “Graph Sampling.” METRON 75 (3): 277–99.
Zhang, Li-Chun, and Nancy 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 36 (1): 151–72.
Zhang, Li-Chun, and Melike Oguz-Alper. 2020. “BIG Sampling.” arXiv:2003.09467 [math, Stat], March.
Zheleva, Elena, and David Arbour. 2021. “Causal Inference from Network Data.” In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 4096–97. KDD ’21. New York, NY, USA: Association for Computing Machinery.
Zhou, Dengyong, Thomas Hofmann, and Bernhard Schölkopf. n.d. “Semi-Supervised Learning on Directed Graphs,” 8.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.