Network Comparison
Last update: 21 Apr 2025 21:17First version:
Yet Another Inadequate Placeholder.
Given two networks, can we tell whether they came from the same source distribution? If not, characterize how the sources differ.
Relatedly: change-point problems for sequences of networks.
See also: Graph Theory; Network Data Analysis; Two-sample Tests
- Recommended (painfully inadequate):
- Giuseppe Jurman, Samantha Riccadonna, Roberto Visintainer, Cesare Furlanello, "Biological network comparison via Ipsen-Mikhailov distance", arxiv:1109.0220 [The metric, to be honest, is not especially compelling, but it's nice to see this done at all.]
- Danai Koutra, Joshua T. Vogelstein, Christos Faloutsos, "DELTACON: A Principled Massive-Graph Similarity Function", arxiv:1304.4657 ["Principled" = compute page-rank affinity vectors, look at average distances. No modeling.]
- Minh Tang, Avanti Athreya, Daniel L. Sussman, Vince Lyzinski, Carey E. Priebe, "A nonparametric two-sample hypothesis testing problem for random dot product graphs", arxiv:1409.2344
- Pride compels me to recommend:
- Dena Marie Asta, Geometric Approaches to Inference: Non-Euclidean Data and Networks [Ph.D. thesis, CMU Departments of Statistics and of Engineering & Public Policy, 2015]
- Lawrence Wang, Network Comparisons using Sample Splitting [Ph.D. thesis, CMU Department of Statistics, 2016]
- Modesty forbids me to recommend:
- Dena Asta and CRS, "Geometric Network Comparison", UAI 2015, arxiv:1411.1350
- To read:
- Yonathan Aflalo, Alexander Bronstein and Ron Kimmel, "On convex relaxation of graph isomorphism", Proceedings of the National Academy of Sciences (USA) 112 (2015): 2942--2947
- James P. Bagrow, Erik M. Bollt, "An information-theoretic, all-scales approach to comparing networks", Applied Network Science 4 (2019): 45, arxiv:1804.03665
- Mohsen Bayati, David F. Gleich, Amin Saberi and Ying Wang, "Message-Passing Algorithms for Sparse Network Alignment", ACM Transactions on Knowledge Discovery from Data 7 (2013): 3 [PDF reprint via Prof. Gleich]
- Phillip Bonacich and Maureen J. McConaghy, "The Algebra of Blockmodeling", Sociological Methodology 11 (1980): 489--532
- Scott A. Boorman and Harrison C. White, "Social Structure from Multiple Networks. II. Role Structures", American Journal of Sociology 81 (1976): 1384--1446 [Ungated PDF copy]
- Ronald L. Breiger and Philippa E. Pattison, "The Joint Role Structure of Two Communities' Elites", Sociological Methods and Research 7 (1978): 213--226 [Thanks to Dr. Breiger for a reprint]
- Kathryn Cooper, Mauricio Barahona, "Role-similarity based comparison of directed networks", arxiv:1103.5582
- Marcelo Fiori, Pablo Sprechmann, Joshua Vogelstein, Pablo Musé, Guillermo Sapiro, "Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching", arxiv:1311.6425
- Lazaros K. Gallos, Nina H. Fefferman, "Revealing effective classifiers through network comparison", arxiv:1403.2668
- Debarghya Ghoshdastidar, Maurilio Gutzeit, Alexandra Carpentier, Ulrike von Luxburg, "Two-sample Hypothesis Testing for Inhomogeneous Random Graphs", arxiv:1707.00833
- Guilherme Gomes, Vinayak Rao, Jennifer Neville, "Multi-level hypothesis testing for populations of heterogeneous networks", arxiv:1809.02512
- Laurent Jacob, Pierre Neuvial, and Sandrine Dudoit, "More power via graph-structured tests for differential expression of gene networks", Annals of Applied Statistics 6 (2012): 561--600
- Giuseppe Jurman, Roberto Visintainer, Samantha Riccadonna, Michele Filosi, Cesare Furlanello, "A glocal distance for network comparison", arxiv:1201.2931
- Vince Lyzinski, Donniell Fishkind, Marcelo Fiori, Joshua T. Vogelstein, Carey E. Priebe, Guillermo Sapiro, "Graph Matching: Relax at Your Own Risk", arxiv:1405.3133
- Maureen J. McConaghy
- "The Common Role Structure Improved Blockmodeling Methods Applied to Two Communities' Elites", Sociological Methods and Research 9 (1981): 267--285 [Thanks to Dr. McConaghy for a reprint]
- "Negation of the Equation: Rejoinder to Pattison", Sociological Methods and Research 9 (1981): 303--312
- Sebastian Moreno and Jennifer Neville, "Network Hypothesis Testing Using Mixed Kronecker Product Graph Models" [PDF reprint via Prof. Neville — who I must thank for telling me about this paper as graciously and tactfully as was humanly possible]
- Philippa E. Pattison, "A Reply to McConaghy: Equating the 'Joint Reduction' with Blockmodel Common Role Structures", Sociological Methods and Research 9 (1981): 286--302
- Leto Peel, Aaron Clauset, "Detecting change points in the large-scale structure of evolving networks", arxiv:1403.0989
- Lucy F. Robinson, Carey E. Priebe, "Detecting Time-dependent Structure in Network Data via a New Class of Latent Process Models", arxiv:1212.3587
- Matthieu Roy, Stefan Schmid, Gilles Trédan, "Modeling and Measuring Graph Similarity: The Case for Centrality Distance", arxiv:1406.5481
- Hamida Seba, Sofiane Lagraa, Elsen Ronando, "Comparison Issues in Large Graphs: State of the Art and Future Directions", arxiv:1502.07576
- Nicolas Städler, Sach Mukherjee, "Two-Sample Testing in High-Dimensional Models", arxiv:1210.4584
- Heng Wang, Minh Tang, Youngser Park, Carey E. Priebe, "Locality statistics for anomaly detection in time series of graphs", arxiv:1306.0267
- Harrison C. White, Scott A. Boorman and Ronald L. Breiger, "Social Structure from Multiple Networks. I. Blockmodels of Roles and Positions", American Journal of Sociology 81 (1976): 730--780 [Ungated PDF copy]
- To write:
- Co-conspirators + CRS, "Detecting Differences in Network Diffusion Patterns"
- CRS + co-conspirators, "Statistical Network Comparisons"
