Skip to Main content Skip to Navigation
Book sections

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.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Jens Gustedt Connect in order to contact the contributor
Submitted on : Wednesday, June 3, 2009 - 11:20:07 AM
Last modification on : Saturday, June 25, 2022 - 7:41:32 PM
Long-term archiving on: : Saturday, November 26, 2016 - 10:17:06 AM


Files produced by the author(s)



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⟩



Record views


Files downloads