Multifractal network generator
- 12 April 2010
- journal article
- research article
- Published by National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 107 (17) , 7640-7645
Abstract
We introduce a new approach to constructing networks with realistic features. Our method, in spite of its conceptual simplicity (it has only two parameters) is capable of generating a wide variety of network types with prescribed statistical properties, e.g., with degree or clustering coefficient distributions of various, very different forms. In turn, these graphs can be used to test hypotheses or as models of actual data. The method is based on a mapping between suitably chosen singular measures defined on the unit square and sparse infinite networks. Such a mapping has the great potential of allowing for graph theoretical results for a variety of network topologies. The main idea of our approach is to go to the infinite limit of the singular measure and the size of the corresponding graph simultaneously. A very unique feature of this construction is that with the increasing system size the generated graphs become topologically more structured. We present analytic expressions derived from the parameters of the—to be iterated—initial generating measure for such major characteristics of graphs as their degree, clustering coefficient, and assortativity coefficient distributions. The optimal parameters of the generating measure are determined from a simple simulated annealing process. Thus, the present work provides a tool for researchers from a variety of fields (such as biology, computer science, biology, or complex systems) enabling them to create a versatile model of their network data.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- On scale-free and poly-scale behaviors of random hierarchical networksJournal of Statistical Mechanics: Theory and Experiment, 2009
- Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testingAdvances in Mathematics, 2008
- Hierarchical structure and the prediction of missing links in networksNature, 2008
- The human disease networkProceedings of the National Academy of Sciences, 2007
- Systematic topology analysis and generation using degree correlationsACM SIGCOMM Computer Communication Review, 2006
- Tuning clustering in random networks with arbitrary degree distributionsPhysical Review E, 2005
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- A critical point for random graphs with a given degree sequenceRandom Structures & Algorithms, 1995
- Markov GraphsJournal of the American Statistical Association, 1986