Graph sampling

Estimating functionals of graphs

2020-02-15 — 2021-07-06

Wherein various sampling procedures for social networks are surveyed, and edge-exchangeable and paintbox processes are invoked to characterize inference limitations under projective and design-unbiased schemes.

distributed

networks

probability

statistics

Notes on what you can infer through various sampling processes on graphs, as made famous by social network research. Paintbox processes? Edge exchangeability? Projectivity? We are notably terrible at this.

Nothing but chaos awaiting filing for now.

I am currently watching an overview seminar by Li Chun Zhang. He covers (Patone and Zhang 2020; Sanguiao Sande and Zhang 2020; L.-C. Zhang and Nguyen 2020; L.-C. Zhang and Oguz-Alper 2020; L.-C. Zhang and Patone 2017) and credits Thompson and Frank, although I don’t know which Thompson and which Frank.

1 Exponential random graph models

A.k.a. ERGMs.

2 References

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.

Cranmer, Desmarais, and Morgan. 2021. Inferential network analysis.

Draves, and Sussman. 2020. “Bias-Variance Tradeoffs in Joint Spectral Embeddings.” arXiv:2005.02511 [Math, Stat].

Green, and Shalizi. 2017. “Bootstrapping Exchangeable Random Graphs.” arXiv:1711.00813 [Stat].

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.

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.

Kandiros, Dagan, Dikkala, et al. 2021. “Statistical Estimation from Dependent Data.” In International Conference on Machine Learning.

Kitsak. n.d. “Identifying Influential Spreaders in Complex Networks.”

Krivitsky, and Handcock. 2014. “A Separable Model for Dynamic Networks.” Journal of the Royal Statistical Society: Series B (Statistical Methodology).

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

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

Patone, and Zhang. 2020. “Incidence Weighting Estimation Under Bipartite Incidence Graph Sampling.” arXiv:2004.04257 [Math, Stat].

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.

Shalizi, and Rinaldo. 2013. “Consistency Under Sampling of Exponential Random Graph Models.” Annals of Statistics.

Snijders. 2010. “Conditional Marginalization for Exponential Random Graph Models.” The Journal of Mathematical Sociology.

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.

Vega-Oliveros. n.d. “Inﬂuence Maximization Based on the Least Inﬂuential Spreaders.”

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.

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.