Building Real-World Complex Networks by Wandering on Random Graphs

Bruno Gaume (1, 2) , Fabien Mathieu (3, 4) , Emmanuel Navarro (5)

1 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage
2 CLLE-ERSS - Cognition, Langues, Langage, Ergonomie
3 GANG - Networks, Graphs and Algorithms
4 Orange Labs [Issy les Moulineaux]
5 IRIT - Institut de recherche en informatique de Toulouse

While most real-world graphs are known to share similar properties with respect to connectivity or degree distribution, generating artificial graphs with those properties is still a challenging issue. In this paper, we propose to use random walks on random graphs to create graphs similar to real-world ones.

La plupart des graphes de terrain représentant des phénomènes du monde réel partagent des propriétés similaires de connectivité et de distribution des degrés , cependant, la génération artificielle de graphes possédant ces propriétés reste encore une question difficile. Dans cet article, nous proposons d'utiliser des marches aléatoires sur des graphes aléatoires pour créer des graphes dont la connectivité et la distribution des degrés sont semblables aux graphes de terrain.

Mots clés: Markov chain; small world; graph; real-world complex network; random graph

Domaines: Réseaux et télécommunications [cs.NI]

Bruno Gaume, Fabien Mathieu, Emmanuel Navarro. Building Real-World Complex Networks by Wandering on Random Graphs. Revue I3 - Information Interaction Intelligence, 2010, 10 (1), pp.73-91. ⟨hal-01321872⟩