Network Comparison

Last update: 21 Apr 2025 21:17
First 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"

Notebooks :