Inference on social graphs

Heterogeneous media and controls

September 22, 2019 — June 3, 2020

causality
collective knowledge
cooperation
distributed
game theory
networks
social graph

Suspiciously similar content

Placeholder.

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

Figure 1

1 Majority Illusions and filter bubbles

See majority illusions.

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.
Hayes, Fredrickson, and Levin. 2024. “Estimating Network-Mediated Causal Effects via Principal Components Network Regression.”
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. 2004. “Semi-Supervised Learning on Directed Graphs.” In Advances In Neural Information Processing Systems.