Génération de graphes aléatoires par échanges multiples d’arêtes

Tabourier, Lionel; Cointet, Jean-Philippe; Roth, Camille

Journal de la société française de statistique, Tome 158 (2017) no. 2, pp. 118-134.

La génération de graphes aléatoires vérifiant un ensemble de propriétés fixé est un problème majeur pour l’étude des réseaux d’interaction. Pourtant, il n’existe pas de solution générale qui soit satisfaisante dans les cas pratiques, où l’ensemble de propriétés à satisfaire est complexe. Nous proposons une méthode de génération permettant théoriquement d’obtenir un échantillon parfaitement aléatoire de n’importe quel ensemble de graphes, à condition que la distribution des degrés soit fixée et que l’on dispose d’un élément de cet ensemble. Cette méthode dite de $k$-échanges, généralise les procédures de Monte-Carlo par chaîne de Markov de la littérature, selon lesquelles on échange itérativement les extrêmités d’arêtes du graphe. Nous décrivons sa réalisation, les difficultés techniques à résoudre et comment il est possible de les surmonter. Nous appliquons cette méthode sur des réseaux de collaborations scientifiques, et montrons que l’on peut identifier un petit nombre de propriétés suffisantes pour expliquer des caractéristiques typiques du réseau.

Generating random graphs which verify a set of predefined properties is a major issue for the analysis of interaction networks. However, there is no general method available for practical cases, where the set of desired properties is complex. We propose a generation method which theoretically allows to obtain a uniform sample of any set of graphs, as long as we have an element of this set and the degree distribution is one of the required properties. This method, called $k$-edge switching, is a generalization of Monte-Carlo Markov Chain methods of the literature which rely on iterating exchanges of edges ends. We describe its conception and implementation, as well as the technical difficulties encountered and how to overcome them. This method is applied on scientific collaboration networks, and we show that we can point out a small set of properties which can explain typical characteristics of the network.

Mot clés : graphes aléatoires, génération de graphes, algorithmes MCMC
Keywords: random graphs, graph generation, MCMC algorithms

[1] Artzy-Randrup, Y.; Stone, L. Generating uniformly distributed random networks, PRE, Volume 72 (2005) no. 5 | DOI

[2] Bender, E.A.; Canfield, E.R. The asymptotic number of labeled graphs with given degree sequences, J. Combin. Theory Ser. A, Volume 24 (1978) no. 3, pp. 296-307 | Zbl

[3] Bansal, S.; Khandelwal, S.; Meyers, L.A. Evolving Clustered Random Networks, Arxiv preprint cs.DM/0808.0509 (2008)

[4] Cooper, C.; Dyer, M.; Greenhill, C. Sampling regular graphs and a peer-to-peer network, Combinatorics, Probability and Computing, Volume 16 (2006) no. 04, pp. 557-593 | Zbl

[5] Coolen, A.C.C.; De Martino, A.; Annibale, A. Constrained Markovian dynamics of random graphs, Journal of Statistical Physics, Volume 136 (2009) no. 6, pp. 1035-1067 | Zbl

[6] 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 | DOI

[7] Colbourn, C.J. Graph generation, University of Waterloo, 1977

[8] Eggleton, R.B. Graphic sequences and graphic polynomials : a report, Infinite and Finite Sets, Volume 1 (1973), pp. 385-392 | Zbl

[9] Feder, T.; Guetz, A.; Mihail, M.; Saberi, A. A local switch Markov chain on given degree graphs with application in connectivity of peer-to-peer networks, Proc. of FOCS, Volume 6 (2006), pp. 69-76

[10] Guillaume, J.L.; Latapy, M. Bipartite structure of all complex networks, Information Processing Letters, Volume 90 (2004) no. 5, pp. 215-221 | MR | Zbl

[11] Guillaume, J.L.; Latapy, M.; Le-Blond, S. Statistical analysis of a P2P query graph based on degrees and their time-evolution, Distributed Computing-IWDC 2004 (2005), pp. 439-465

[12] Gkantsidis, C.; Mihail, M.; Zegura, E.W. The Markov Chain Simulation Method for Generating Connected Power Law Random Graphs, Proc. 5th Workshop on Algorithm Engineering and Experiments (ALENEX) (2003)

[13] Girvan, M.; Newman, M.E.J. Community structure in social and biological networks, Proceedings of the National Academy of Sciences, Volume 99 (2002) no. 12, pp. 7821-7826 | DOI | MR | Zbl

[14] Guruswami, V. Rapidly mixing markov chains : A comparison of techniques (2000) (Available on cs.washington.edu/homes/venkat/pubs/papers.html)

[15] Henriet, F.; Hallegatte, S.; Tabourier, L. Firm-network characteristics and economic robustness to natural disasters, Journal of Economic Dynamics and Control, Volume 36 (2012) no. 1, pp. 150-167 | MR | Zbl

[16] Holland, P.W.; Leinhardt, S. Transitivity in structural models of small groups., Comparative Group Studies (1971)

[17] Kannan, R.; Tetali, P.; Vempala, S. Simple Markov-chain algorithms for generating bipartite graphs and tournaments, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms (1997), pp. 193-200 | MR | Zbl

[18] Levin, D.A.; Peres, Y.; Wilmer, E.L. Markov chains and mixing times, AMS Bookstore, 2009 | MR | Zbl

[19] Mahadevan, P.; Krioukov, D.; Fall, K.; Vahdat, A. Systematic Topology Analysis and Generation Using Degree Correlations, Proc. SIGCOMM’06, ACM (2006)

[20] Milo, R.; Kashtan, N.; Itzkovitz, S.; Newman, M.E.J.; Alon, U. On the uniform generation of random graphs with prescribed degree sequences, Arxiv preprint cond-mat/0312.028 (2003)

[21] Miklós, I.; Podani, J. Randomization of presence-absence matrices : comments and new algorithms, Ecology Archives, Volume 85 (2004) no. 1, pp. 86-92 (Appendix A available on http ://esapubs.org/archive/ecol/E085/001/appendix-A.htm)

[22] Molloy, M.; Reed, B. A critical point for random graphs with a given degree sequence, Random Structures and Algorithms, Volume 161 (1995) no. 6, pp. 161-179 | MR | Zbl

[23] Newman, M.E.J. Coauthorship networks and patterns of scientific collaboration, Proceedings of the National Academy of Sciences of the United States of America, Volume 101 (2004) no. Suppl 1, pp. 5200-5205 | DOI

[24] Newman, M.E.J.; Strogatz, S.H.; Watts, D.J. Random graphs models of social networks, PNAS, Volume 99 (2002), pp. 2566-2572 | Zbl

[25] Rao, A.R.; Jana, R.; Bandyopadhyay, S. A Markov chain Monte Carlo method for generating random (0, 1)-matrices with given marginals, Sankhyā : The Indian Journal of Statistics, Series A (1996), pp. 225-242 | MR | Zbl

[26] Roberts, J.M. Simple methods for simulating sociomatrices with given marginal totals, Social Networks, Volume 22 (2000) no. 3, pp. 273-283

[27] Stauffer, A.O.; Barbosa, V.C. A study of the edge-switching Markov-chain method for the generation of random graphs, Arxiv preprint cs.DM/0512.105 (2005)

[28] Sinclair, A. Algorithms for random generation and counting : a Markov chain approach, Springer, 1993 | MR | Zbl

[29] Taylor, R. Constrained switchings in graphs, Combinatorial Mathematics, Volume 8 (1980), p. 314--336 | MR | Zbl

[30] Taylor, R. Switchings constrained to 2-connectivity in simple graphs, SIAM Journal on Algebraic and Discrete Methods, Volume 3 (1982), pp. 114-121 | DOI | MR | Zbl

[31] Tangmunarunkit, H.; Govindan, R.; Jamin, S.; Shenker, S.; Willinger, W. Network Topology Generators : Degree-Based vs. Structural, Proc. SIGCOMM’02 (2002), pp. 147-159

[32] Viger, F.; Latapy, M. Efficient and simple generation of random simple connected graphs with prescribed degree sequence, Lecture Notes in Computer Science, Volume 3595 (2005), pp. 440-449 | DOI | MR | Zbl

[33] Wernicke, S. Efficient detection of network motifs, Computational Biology and Bioinformatics, IEEE/ACM Transactions on, Volume 3 (2006) no. 4, pp. 347-359

[34] Wasserman, S.; Faust, K. Social network analysis : Methods and applications, Cambridge university press, 1994 | Zbl