Multifractal Network Generator

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 the complexity of the generated network is increasing with the size. 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.

Preprint. Final version appeared in PNAS.

References in corpus (15)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Hierarchical structure and the prediction of missing links in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Self-similarity of complex networks
• The phase transition in inhomogeneous random graphs
• Deterministic Scale-Free Networks
• Class of correlated random networks with hidden variables
• The entropy of randomized network ensembles
• Solution of the 2-star model of a network
• Tuning clustering in random networks with arbitrary degree distributions
• Systematic Topology Analysis and Generation Using Degree Correlations
• On scale-free and poly-scale behaviors of random hierarchical network

Cited by in corpus (35)

• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Community structure and scale-free collections of Erdös-Rényi graphs
• Multiplicative Attribute Graph Model of Real-World Networks
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Eigenvalue Spectra of Modular Networks
• Random Graph Modeling: A survey of the concepts
• Modeling Social Networks with Node Attributes using the Multiplicative Attribute Graph Model
• Mapping Koch curves into scale-free small-world networks
• Multifractal analysis of complex networks
• Unveiling the Multi-fractal Structure of Complex Networks
• A Hebbian approach to complex network generation
• Generating hierarchial scale free graphs from fractals
• Hierarchical benchmark graphs for testing community detection algorithms
• Variational Bayes model averaging for graphon functions and motif frequencies inference in W-graph models
• BioCode: A Data-Driven Procedure to Learn the Growth of Biological Networks
• Multiscale Network Generation
• Learning multifractal structure in large networks
• From sparse to dense and from assortative to disassortative in online social networks
• Features and heterogeneities in growing network models
• Islands of stability in motif distributions of random networks
• On sparsity, power-law and clustering properties of graphex processes
• Overlapping modularity at the critical point of k-clique percolation
• Complex networks as an emerging property of hierarchical preferential attachment
• A computationally-efficient sandbox algorithm for multifractal analysis of large-scale complex networks with tens of millions of nodes
• Goodness of fit of logistic models for random graphs
• On the motifs distribution in random hierarchical networks
• Discovering universal statistical laws of complex networks
• Rotated multifractal network generator
• Modular Networks for Validating Community Detection Algorithms
• Generalised thresholding of hidden variable network models with scale-free property
• Edge Union of Networks on the Same Vertex Set
• Testing goodness-of-fit of random graph models
• Automatically generating models of IT systems
• Modular decomposition of graphs and hierarchical modeling
• Fractal Gaussian Networks: A sparse random graph model based on Gaussian Multiplicative Chaos