Generalized Attachment Models for the Genesis of Graphs with High Clustering Coefficient

Jens Gustedt 1
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Commonly used techniques for the random generation of graphs such as those of Erdős & Rényi and Barabási & Albert have two disadvantages, namely their lack of bias with respect to history of the evolution of the graph, and their incapability to produce families of graphs with non-vanishing prescribed clustering coefficient. In this work we propose a model for the genesis of graphs that tackles these two issues. When translated into random generation procedures it generalizes the above mentioned procedures.When just seen as composition schemes for graphs they generalize the perfect elimination schemes of chordal graphs. The model iteratively adds so-called contexts that introduce an explicit dependency to the previous evolution of the graph. Thereby they reflect a historical bias during this evolution that goes beyond the simple degree constraint of preference edge attachment. Fixing certain simple statical quantities during the genesis leads to families of random graphs with a clustering coefficient that can be bounded away from zero.
Type de document :
Chapitre d'ouvrage
Santo Fortunato and Giuseppe Mangioni and Ronaldo Menezes and Vincenzo Nicosia. Complex Networks - Results of the 2009 International Workshop on Complex Networks (CompleNet 2009), 207, Springer Berlin / Heidelberg, pp.99-113, 2009, Studies in Computational Intelligence, 978-3-642-01205-1. 〈10.1007/978-3-642-01206-8_9〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00312059
Contributeur : Jens Gustedt <>
Soumis le : mercredi 3 juin 2009 - 11:20:07
Dernière modification le : dimanche 20 mai 2018 - 20:20:10
Document(s) archivé(s) le : samedi 26 novembre 2016 - 10:17:06

Fichier

attachment-CompleNet.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jens Gustedt. Generalized Attachment Models for the Genesis of Graphs with High Clustering Coefficient. Santo Fortunato and Giuseppe Mangioni and Ronaldo Menezes and Vincenzo Nicosia. Complex Networks - Results of the 2009 International Workshop on Complex Networks (CompleNet 2009), 207, Springer Berlin / Heidelberg, pp.99-113, 2009, Studies in Computational Intelligence, 978-3-642-01205-1. 〈10.1007/978-3-642-01206-8_9〉. 〈inria-00312059v2〉

Partager

Métriques

Consultations de la notice

395

Téléchargements de fichiers

182