Random graph models: an overview of modeling approaches

Channarond, Antoine

Journal de la société française de statistique, Tome 156 (2015) no. 3, pp. 56-94.

Cet article établit une revue non exhaustive des modèles de graphes aléatoires destinés à la modélisation de réseaux d’interaction. Il commence par le modèle d’Erdős-Rényi qui a pu être étudié en profondeur car il repose sur des hypothèses simples d’indépendance et d’homogénéité des liens, cependant trop réductrices pour les applications. L’article se concentre ensuite sur les démarches de modélisation de l’hétérogénéité et des dépendances entre les liens. Il part de modèles probabilistes reproduisant les processus de génération des réseaux réels (modèles de Barabási-Albert ou de Watts-Strogatz par exemple) et arrive à des modèles plus adaptés à la statistique. Les modèles exponentiels (ERGM ou $p^{*}$) permettent d’introduire des dépendances entre les liens voulus. Les modèles à variables latentes permettent de modéliser l’hétérogénéité de la population et de l’analyser.

This article nonexhaustively reviews random graph models designed to model interaction networks. It begins with the Erdős-Rényi model which could be deeply studied, as it is based on simple assumptions: independence and homogeneity of the links. However they are too simplistic for applications. The article then focuses on modeling approaches of the hetereogeneity and of the dependences between the links. It starts from probabilistic models reproducing generative processes of the real-world networks (Barabási-Albert or Watts-Strogatz models for instance) and arrives to models more suitable for statistics. Exponential models (ERGM or $p^{*}$) enable to introduce dependences between the desired links. Models with latent variables enable to model heterogeneity of the population and to analyze it.

Keywords: random graph models, review, Erdős-Rényimodel, complex networks
Mot clés : modèles de graphes aléatoires, revue, modèle d’Erdős-Rényi, réseaux complexes

[1] Albert, R.; Barabási, A.L. Statistical mechanics of complex networks, Reviews of modern physics, Volume 74 (2002) no. 1, pp. 47-97 | DOI | MR | Zbl

[2] Airoldi, Edoardo M; Blei, David M; Fienberg, Stephen E; Xing, Eric P Mixed membership stochastic blockmodels, The Journal of Machine Learning Research, Volume 9 (2008), pp. 1981-2014 | Zbl

[3] Airoldi, Edoardo M; Costa, Thiago B; Chan, Stanley H Stochastic blockmodel approximation of a graphon: Theory and consistent estimation, Advances in Neural Information Processing Systems (2013), pp. 692-700

[4] Arias-Castro, Ery; Verzelen, Nicolas Community detection in random networks, arXiv preprint arXiv:1302.7099 (2013) | Zbl

[5] Arratia, Richard; Goldstein, Larry; Gordon, Louis Two moments suffice for Poisson approximations: the Chen-Stein method, The Annals of Probability, Volume 17 (1989) no. 1, pp. 9-25 | Zbl

[6] Aldous, David Brownian excursions, critical random graphs and the multiplicative coalescent, The Annals of Probability (1997), pp. 812-854 | Zbl

[7] Barabási, Albert-László; Albert, Réka Emergence of scaling in random networks, science, Volume 286 (1999) no. 5439, pp. 509-512 | Zbl

[8] Bhattacharyya, Sharmodeep; Bickel, Peter J Spectral Clustering and Block Models: A Review And A New Algorithm, arXiv preprint arXiv:1508.01819 (2015) | Zbl

[9] Bender, Edward A; Canfield, E Rodney The asymptotic number of labeled graphs with given degree sequences, Journal of Combinatorial Theory, Series A, Volume 24 (1978) no. 3, pp. 296-307 | Zbl

[10] Beal, Matthew James Variational algorithms for approximate Bayesian inference, University of London (2003) (Ph. D. Thesis)

[11] Besag, Julian Markov chain Monte Carlo for statistical inference, Center for Statistics and the Social Sciences (2001)

[12] Besag, Julian Spatial interaction and the statistical analysis of lattice systems, Journal of the Royal Statistical Society. Series B (Methodological) (1974), pp. 192-236 | Zbl

[13] Besag, Julian Statistical analysis of non-lattice data, The statistician (1975), pp. 179-195

[14] Barbour, Andrew D; Holst, Lars; Janson, Svante Poisson approximation, Clarendon press Oxford, 1992 | Zbl

[15] Birmele, Etienne Detecting local network motifs, Electronic Journal of Statistics, Volume 6 (2012), pp. 908-933 | Zbl

[16] Bollobás, B.; Janson, S.; Riordan, O. The phase transition in inhomogeneous random graphs, Random Structures & Algorithms, Volume 31 (2007) no. 1, pp. 3-122 | Zbl

[17] Blondel, Vincent; Krings, Gautier; Thomas, Isabelle Regions and borders of mobile telephony in Belgium and in the Brussels metropolitan zone, Brussels Studies, Volume 42 (2010) no. 4

[18] Barbour, Andrew; Mollison, Denis Epidemics and random graphs, Stochastic processes in epidemic theory, Volume 86 (1990), pp. 86-89

[19] Buckley, Pierce G; Osthus, Deryk Popularity based random graph models leading to a scale-free degree sequence, Discrete Mathematics, Volume 282 (2004) no. 1, pp. 53-68 | Zbl

[20] Bollobás, B. Random graphs, Cambridge Univ Pr, 2001 | Zbl

[21] Bollobás, Béla; Riordan, Oliver Mathematical results on scale-free random graphs, Handbook of graphs and networks, Volume 1 (2003), 34 pages

[22] Bollobás, Béla; Riordan, Oliver Robustness and vulnerability of scale-free random graphs, Internet Mathematics, Volume 1 (2004) no. 1, pp. 1-35 | Zbl

[23] Bollobás, Béla; Riordan, Oliver The diameter of a scale-free random graph, Combinatorica, Volume 24 (2004) no. 1, pp. 5-34 | Zbl

[24] Bollobás, Béla; Riordan, Oliver; Spencer, Joel; Tusnády, Gábor The degree sequence of a scale-free random graph process, Random Structures & Algorithms, Volume 18 (2001) no. 3, pp. 279-290 | Zbl

[25] Barbillon, Pierre; Thomas, Mathieu; Goldringer, Isabelle; Hospital, Frédéric; Robin, Stéphane Network impact on persistence in a finite population dynamic diffusion model: application to an emergent seed exchange network, Journal of theoretical biology, Volume 365 (2015), pp. 365-376 | Zbl

[26] Chatterjee, Sourav Matrix estimation by universal singular value thresholding, The Annals of Statistics, Volume 43 (2014) no. 1, pp. 177-214 | Zbl

[27] Charbonnier, Camille; Chiquet, Julien; Ambroise, Christophe Weighted-LASSO for structured network inference from time course data, Statistical applications in genetics and molecular biology, Volume 9 (2010) no. 1 | Zbl

[28] Célisse, Alain; Daudin, Jean-Jacques; Pierre, Laurent Consistency of maximum-likelihood and variational estimators in the stochastic block model, Electronic Journal of Statistics, Volume 6 (2012), pp. 1847-1899 | Zbl

[29] Channarond, Antoine; Daudin, Jean-Jacques; Robin, Stéphane Classification and estimation in the Stochastic Blockmodel based on the empirical degrees, Electronic Journal of Statistics, Volume 6 (2012), pp. 2574-2601 | Zbl

[30] Channarond, Antoine Recherche de structure dans un graphe aléatoire: modèles à espace latent, Université Paris Sud-Paris XI (2013) (Ph. D. Thesis)

[31] Chen, Louis HY Poisson approximation for dependent trials, The Annals of Probability (1975), pp. 534-545 | Zbl

[32] Chung, Fan; Lu, Linyuan; Dewey, T Gregory; Galas, David J Duplication models for biological networks, Journal of Computational Biology, Volume 10 (2003) no. 5, pp. 677-687

[33] Cappé, Olivier; Moulines, Eric; Rydén, Tobias Inference in hidden Markov models, Springer Science & Business Media, 2006 | Zbl

[34] Callaway, Duncan S; Newman, Mark EJ; Strogatz, Steven H; Watts, Duncan J Network robustness and fragility: Percolation on random graphs, Physical review letters, Volume 85 (2000) no. 25, pp. 5468-5471 | DOI

[35] Dempster, A.P.; Laird, N.M.; Rubin, D.B. Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society. Series B (Methodological), Volume 39 (1977) no. 1, pp. 1-38 | Zbl

[36] Draief, M; Massoulié, L Epidemics and rumours in complex networks, volume 369 of London Mathematical Society Lecture Notes, 2010 | Zbl

[37] Daudin, J.J.; Picard, F.; Robin, S. A mixture model for random graphs, Statistics and computing, Volume 18 (2008) no. 2, pp. 173-183

[38] Durrett, Richard Random graph dynamics, 20, Cambridge university press, 2007 | Zbl

[39] Durkheim, Emile De la division du travail social: étude sur l’organisation des sociétés supérieures, F. Alcan, 1893

[40] Dommers, Sander; van der Hofstad, Remco; Hooghiemstra, Gerard Diameters in preferential attachment models, Journal of Statistical Physics, Volume 139 (2010) no. 1, pp. 72-107 | Zbl

[41] Erdős, P.; Rényi, A. On random graphs, I, Publicationes Mathematicae (Debrecen), Volume 6 (1959), pp. 290-297 | Zbl

[42] Erdos, Paul; Rényi, Alfréd On the evolution of random graphs, Bull. Inst. Internat. Statist, Volume 38 (1961) no. 4, pp. 343-347 | Zbl

[43] Erdős, Paul; Renyi, Alfred On the strength of connectedness of a random graph, Acta Mathematica Hungarica, Volume 12 (1961) no. 1, pp. 261-267 | Zbl

[44] Euler, Leonhard Solutio problematis ad geometriam situs pertinentis, Commentarii academiae scientiarum Petropolitanae, Volume 8 (1741), pp. 128-140

[45] Fortunato, Santo Community detection in graphs, Physics Reports, Volume 486 (2010) no. 3, pp. 75-174

[46] Frank, Ove; Strauss, David Markov graphs, Journal of the american Statistical association, Volume 81 (1986) no. 395, pp. 832-842 | Zbl

[47] Gerbaud, Antoine Modélisation de réseaux d’interactions par des graphes aléatoires, Université de Grenoble, December (2010) (Ph. D. Thesis)

[48] Gilbert, E.N. Random graphs, The Annals of Mathematical Statistics, Volume 30 (1959) no. 4, pp. 1141-1144 | Zbl

[49] Gupta, Piyush; Kumar, Panganamala R Critical power for asymptotic connectivity in wireless networks, Stochastic analysis, control, optimization and applications, Springer, 1998, pp. 547-566 | Zbl

[50] Goldenberg, Anna; Zheng, Alice X; Fienberg, Stephen E; Airoldi, Edoardo M A survey of statistical network models, Foundations and Trends® in Machine Learning, Volume 2 (2010) no. 2, pp. 129-233 | Zbl

[51] Hartigan, John A Clustering algorithms, John Wiley & Sons, Inc., 1975 | Zbl

[52] Hunter, David R; Handcock, Mark S Inference in curved exponential family models for networks, Journal of Computational and Graphical Statistics, Volume 15 (2006) no. 3, pp. 565-583

[53] Holland, P.W.; Leinhardt, S. An exponential family of probability distributions for directed graphs, Journal of the American Statistical Association, Volume 76 (1981) no. 373, pp. 33-50 | Zbl

[54] Holland, P.W.; Laskey, K.B.; Leinhardt, S. Stochastic blockmodels: First steps, Social Networks, Volume 5 (1983) no. 2, pp. 109-137

[55] Hoff, P.D.; Raftery, A.E.; Handcock, M.S. Latent space approaches to social network analysis, Journal of the American Statistical Association, Volume 97 (2002) no. 460, pp. 1090-1098 | Zbl

[56] Handcock, M.S.; Raftery, A.E.; Tantrum, J.M. Model-based clustering for social networks, Journal of the Royal Statistical Society: Series A (Statistics in Society), Volume 170 (2007) no. 2, pp. 301-354

[57] Jaakkola, T.S. Tutorial on variational approximation methods, Advanced mean field methods: theory and practice (2000), pp. 129-159

[58] Janson, Svante; Knuth, Donald E; Łuczak, Tomasz; Pittel, Boris The birth of the giant component, Random Structures & Algorithms, Volume 4 (1993) no. 3, pp. 233-358 | Zbl

[59] Janson, Svante; Luczak, Tomasz; Kolchin, VF Random graphs, Cambridge Univ Press, 2000 | Zbl

[60] Kleinberg, Jon M; Kumar, Ravi; Raghavan, Prabhakar; Rajagopalan, Sridhar; Tomkins, Andrew S The web as a graph: Measurements, models, and methods, Computing and combinatorics, Springer, 1999, pp. 1-17

[61] Kleinberg, Jon The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, ACM (2000), pp. 163-170 | Zbl

[62] Kolaczyk, Eric D Statistical analysis of network data, Springer, 2009 | Zbl

[63] Latouche, Pierre; Birmelé, Etienne; Ambroise, Christophe Overlapping stochastic block models with application to the french political blogosphere, The Annals of Applied Statistics, Volume 5 (2011) no. 1, pp. 309-336 | Zbl

[64] Leger, Jean-Benoist Wmixnet: Software for clustering the nodes of binary and valued graphs using the stochastic block model, arXiv preprint arXiv:1402.3410 (2014)

[65] Lotka, Alfred James The frequency distribution of scientific productivity., Journal of Washington Academy Sciences (1926)

[66] Lovász, László; Szegedy, Balázs Limits of dense graph sequences, Journal of Combinatorial Theory, Series B, Volume 96 (2006) no. 6, pp. 933-957 | Zbl

[67] Luce, R Duncan Two decomposition theorems for a class of finite oriented graphs, American Journal of Mathematics (1952), pp. 701-722 | Zbl

[68] Leger, Jean-Benoist; Vacher, Corinne; Daudin, Jean-Jacques Detection of structurally homogeneous subsets in graphs, Statistics and Computing (2013), pp. 1-18 | Zbl

[69] Lorrain, F.; White, H.C. Structural equivalence of individuals in social networks, The Journal of mathematical sociology, Volume 1 (1971) no. 1, pp. 49-80

[70] McFarland, David D; Brown, Daniel J Social Distance as Metric: A Systematic Introduction to Smallest Space Analysis, EO Laumann. Bonds of Pluralism: The Form and Substance of Urban Social Networks. New York: John Wiley (1973), pp. 213-252

[71] Milgram, Stanley The small world problem, Psychology today, Volume 2 (1967) no. 1, pp. 60-67

[72] Moreno, Jacob L; Jennings, Helen H Statistics of social configurations, Sociometry (1938), pp. 342-374

[73] Mariadassou, Mahendra; Matias, Catherine Convergence of the groups posterior distribution in latent or stochastic block models, Bernoulli, Volume 21 (2015) no. 1, pp. 537-573 | Zbl

[74] Moreno, Jacob L Sociometry in relation to other social sciences, Sociometry, Volume 1 (1937) no. 1/2, pp. 206-219

[75] Matias, Catherine; Robin, Stéphane Modeling heterogeneity in random graphs through latent space models: a selective review, ESAIM: Proceedings and Surveys, Volume 47 (2014), pp. 55-74 | Zbl

[76] Molloy, Michael; Reed, Bruce A critical point for random graphs with a given degree sequence, Random structures & algorithms, Volume 6 (1995) no. 2-3, pp. 161-180 | Zbl

[77] Milo, Ron; Shen-Orr, Shai; Itzkovitz, Shalev; Kashtan, Nadav; Chklovskii, Dmitri; Alon, Uri Network motifs: simple building blocks of complex networks, Science, Volume 298 (2002) no. 5594, pp. 824-827

[78] Murphy, Kevin Patrick Dynamic bayesian networks: representation, inference and learning, University of California, Berkeley (2002) (Ph. D. Thesis)

[79] Newman, Mark EJ The structure and function of complex networks, SIAM review, Volume 45 (2003) no. 2, pp. 167-256 | Zbl

[80] Nielsen, Thomas Dyhre; Jensen, Finn Verner Bayesian networks and decision graphs, Springer Science & Business Media, 2009

[81] Nachmias, Asaf; Peres, Yuval The critical random graph, with martingales, Israel Journal of Mathematics, Volume 176 (2010) no. 1, pp. 29-41 | Zbl

[82] Nowicki, K.; Snijders, T.A.B. Estimation and prediction for stochastic blockstructures, Journal of the American Statistical Association, Volume 96 (2001) no. 455, pp. 1077-1087 | Zbl

[83] Newman, Mark EJ; Watts, Duncan J Renormalization group analysis of the small-world network model, Physics Letters A, Volume 263 (1999) no. 4, pp. 341-346 | Zbl

[84] Newman, Mark EJ; Watts, Duncan J Scaling and percolation in the small-world network model, Physical Review E, Volume 60 (1999) no. 6, pp. 7332-7342 | DOI

[85] Opper, Manfred; Saad, David Advanced mean field methods: Theory and practice, MIT press, 2001 | Zbl

[86] Olhede, Sofia C; Wolfe, Patrick J Network histograms and universality of blockmodel approximation, Proceedings of the National Academy of Sciences, Volume 111 (2014) no. 41, pp. 14722-14727

[87] Penrose, Mathew Random geometric graphs, 5, Oxford University Press Oxford, 2003 | Zbl

[88] Picard, F.; Miele, V.; Daudin, J.J.; Cottret, L.; Robin, S. Deciphering the connectivity structure of biological networks using MixNet, BMC bioinformatics, Volume 10 (2009) no. Suppl 6 | DOI

[89] Rohe, K.; Chatterjee, S.; Yu, B. Spectral clustering and the high-dimensional Stochastic Block Model, Arxiv preprint arXiv:1007.1684 (2010) | Zbl

[90] Robins, Garry; Pattison, Pip; Kalish, Yuval; Lusher, Dean An introduction to exponential random graph $\left(p^{*}\right)$ models for social networks, Social networks, Volume 29 (2007) no. 2, pp. 173-191

[91] Strauss, David; Ikeda, Michael Pseudolikelihood estimation for social networks, Journal of the American Statistical Association, Volume 85 (1990) no. 409, pp. 204-212

[92] Snijders, T.A.B.; Nowicki, K. Estimation and prediction for stochastic blockmodels for graphs with latent block structure, Journal of Classification, Volume 14 (1997) no. 1, pp. 75-100 | Zbl

[93] Snijders, Tom AB Markov chain Monte Carlo estimation of exponential random graph models, Journal of Social Structure, Volume 3 (2002) no. 2, pp. 1-40

[94] Snijders, Tom AB Statistical models for social networks, Annual Review of Sociology, Volume 37 (2011), pp. 131-153

[95] Snijders, Tom AB; Pattison, Philippa E; Robins, Garry L; Handcock, Mark S New specifications for exponential random graph models, Sociological methodology, Volume 36 (2006) no. 1, pp. 99-153

[96] Von Luxburg, U. A tutorial on spectral clustering, Statistics and Computing, Volume 17 (2007) no. 4, pp. 395-416

[97] Van Der Hofstad, R. Random graphs and complex networks, Available on http://www. win. tue. nl/rhofstad/NotesRGCN. pdf (2009)

[98] Wainwright, M.J.; Jordan, M.I. Graphical models, exponential families, and variational inference, Foundations and Trends® in Machine Learning, Volume 1 (2008) no. 1-2, pp. 1-305 | Zbl

[99] Wasserman, Stanley; Robins, Garry L An introduction to random graphs, dependence graphs, and p*, Models and methods in social network analysis, Volume 27 (2005), pp. 148-161

[100] Watts, Duncan J; Strogatz, Steven H Collective dynamics of ‘small-world’networks, nature, Volume 393 (1998) no. 6684, pp. 440-442 | Zbl

[101] Wang, Bo; Titterington, DM Lack of consistency of mean field and variational Bayes approximations for state space models, Neural Processing Letters, Volume 20 (2004) no. 3, pp. 151-170

[102] Yule, G Udny A mathematical theory of evolution, based on the conclusions of Dr. JC Willis, FRS, Philosophical Transactions of the Royal Society of London. Series B, Containing Papers of a Biological Character, Volume 213 (1925), pp. 21-87

[103] Zachary, Wayne W An information flow model for conflict and fission in small groups, Journal of anthropological research (1977), pp. 452-473

[104] Zhang, Jun The mean field theory in EM procedures for Markov random fields, Signal Processing, IEEE Transactions on, Volume 40 (1992) no. 10, pp. 2570-2583 | Zbl