• Go Mobile »
  • Access by Staats- und Universitaetsbibliothek Bremen

Subgraph fluctuations in random graphs

Phys. Rev. E 85, 056119 – Published 29 May 2012
Christoph Fretter, Matthias Müller-Hannemann, and Marc-Thorsten Hütt

Abstract

The pattern of over- and under-representations of three-node subgraphs has become a standard method of characterizing complex networks and evaluating how this intermediate level of organization contributes to network function. Understanding statistical properties of subgraph counts in random graphs, their fluctuations, and their interdependences with other topological attributes is an important prerequisite for such investigations. Here we introduce a formalism for predicting subgraph fluctuations induced by perturbations of unidirectional and bidirectional edge densities. On this basis we predict the over- and under-representation of subgraphs arising from a density mismatch between a network and the corresponding pool of randomized graphs serving as a null model. Such mismatches occur, for example, in modular and hierarchical graphs.

DOI: http://dx.doi.org/10.1103/PhysRevE.85.056119

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
1 More
  • Received 13 September 2011
  • Published 29 May 2012

©2012 American Physical Society

Authors & Affiliations

Christoph Fretter and Matthias Müller-Hannemann

  • Institut für Informatik, Martin-Luther-Universität Halle-Wittenberg, 06120 Halle, Germany

Marc-Thorsten Hütt

  • School of Engineering and Science, Jacobs University, 28759 Bremen, Germany

Article Text

Click to Expand

Supplemental Material

Click to Expand

References

Click to Expand

Authorization Required


×
×

Images

3 of 8
×

Log In

Cancel
×

Search


Article Lookup
Paste a citation or DOI

Enter a citation
×

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 3.0 License. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

×