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.
%0 Journal Article
%1 Palla2010Multifractal
%A Palla, G.
%A Lovasz, L.
%A Vicsek, T.
%D 2010
%J Proceedings of the National Academy of Sciences
%K networks
%N 17
%P 7640--7645
%R 10.1073/pnas.0912983107
%T Multifractal Network Generator
%U http://dx.doi.org/10.1073/pnas.0912983107
%V 107
%X 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.
@article{Palla2010Multifractal,
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.},
added-at = {2018-12-02T16:09:07.000+0100},
archiveprefix = {arXiv},
author = {Palla, G. and Lovasz, L. and Vicsek, T.},
biburl = {https://www.bibsonomy.org/bibtex/253eb863ac70fd57a33de30c273f3543f/karthikraman},
citeulike-article-id = {7018811},
citeulike-linkout-0 = {http://arxiv.org/abs/1004.5225},
citeulike-linkout-1 = {http://arxiv.org/pdf/1004.5225},
citeulike-linkout-2 = {http://dx.doi.org/10.1073/pnas.0912983107},
citeulike-linkout-3 = {http://www.pnas.org/content/107/17/7640.abstract},
citeulike-linkout-4 = {http://www.pnas.org/content/107/17/7640.full.pdf},
citeulike-linkout-5 = {http://view.ncbi.nlm.nih.gov/pubmed/20385847},
citeulike-linkout-6 = {http://www.hubmed.org/display.cgi?uids=20385847},
day = 29,
doi = {10.1073/pnas.0912983107},
eprint = {1004.5225},
interhash = {76329d8d369b78a38c8fd61ee4406766},
intrahash = {53eb863ac70fd57a33de30c273f3543f},
issn = {1091-6490},
journal = {Proceedings of the National Academy of Sciences},
keywords = {networks},
month = apr,
number = 17,
pages = {7640--7645},
pmid = {20385847},
posted-at = {2010-04-14 12:44:15},
priority = {2},
timestamp = {2018-12-02T16:09:07.000+0100},
title = {Multifractal Network Generator},
url = {http://dx.doi.org/10.1073/pnas.0912983107},
volume = 107,
year = 2010
}