Berlin 2012 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
DY: Fachverband Dynamik und Statistische Physik
DY 30: Networks IV (with SOE)
DY 30.4: Talk
Friday, March 30, 2012, 10:45–11:00, MA 001
Statistical description of subgraph fluctuations in random graphs — •Christoph Fretter1, Matthias Müller-Hannemann2, and Marc-Thorsten Hütt1 — 1School of Engineering and Science, Jacobs University, Bremen, Germany — 2Institut für Informatik, Martin-Luther Universität Halle-Wittenberg, Germany
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. We explored this relationship in previous publications [1,2]. Understanding statistical properties of subgraph counts in random graphs, their fluctuations and their interdependencies with other topological attributes is an important prerequisite for such investigations. Here we introduce a formalism for predicting subgraph fluctuations induced by perturbations of uni-directional and bi-directional edge densities. On this basis we predict the over- and underrepresentation of subgraphs arising from a density mismatch between a network and the corresponding pool of randomized graphs serving as null model. Such mismatches occur for example in modular and hierarchical graphs.
[1] Krumov L., Fretter, C., Müller-Hannemann, M., Weihe, K. and Hütt, M.-Th., Motifs in co-authorship networks and their relation to the impact of scientific publications. Eur. Phys. J. B, (2011) in press. [2] Marr, C., Theis, F.J., Liebovitch, L.S. and Hütt, M.-Th., Patterns of subnet usage in the transcriptional regulatory network of Escherichia coli. PLoS Computational Biology 6, e1000836 (2010).