title: A new method to measure complexity in binary or weighted networks and applications to functional connectivity in the human brain.
abstract: BACKGROUND
  Networks or graphs play an important role in the biological sciences. Protein interaction networks and metabolic networks support the understanding of basic cellular mechanisms. In the human brain, networks of functional or structural connectivity model the information-flow between cortex regions. In this context, measures of network properties are needed. We propose a new measure, Ndim, estimating the complexity of arbitrary networks. This measure is based on a fractal dimension, which is similar to recently introduced box-covering dimensions. However, box-covering dimensions are only applicable to fractal networks. The construction of these network-dimensions relies on concepts proposed to measure fractality or complexity of irregular sets in [Formula: see text].
  
  
  RESULTS
  The network measure Ndim grows with the proliferation of increasing network connectivity and is essentially determined by the cardinality of a maximum k-clique, where k is the characteristic path length of the network. Numerical applications to lattice-graphs and to fractal and non-fractal graph models, together with formal proofs show, that Ndim estimates a dimension of complexity for arbitrary graphs. Box-covering dimensions for fractal graphs rely on a linear log-log plot of minimum numbers of covering subgraph boxes versus the box sizes. We demonstrate the affinity between Ndim and the fractal box-covering dimensions but also that Ndim extends the concept of a fractal dimension to networks with non-linear log-log plots. Comparisons of Ndim with topological measures of complexity (cost and efficiency) show that Ndim has larger informative power. Three different methods to apply Ndim to weighted networks are finally presented and exemplified by comparisons of functional brain connectivity of healthy and depressed subjects.
  
  
  CONCLUSIONS
  We introduce a new measure of complexity for networks. We show that Ndim has the properties of a dimension and overcomes several limitations of presently used topological and fractal complexity-measures. It allows the comparison of the complexity of networks of different type, e.g., between fractal graphs characterized by hub repulsion and small world graphs with strong hub attraction. The large informative power and a convenient computational CPU-time for moderately sized networks may make Ndim a valuable tool for the analysis of biological networks.
authors.affiliation: Institute of Computational Biology, HMGU-German Research Center for Environmental Health, Ingolstädter Landstraße 1, Neuherberg, 85764, Germany. hahn@helmholtz-muenchen.de.
authors.forename: Klaus
authors.initials: K
authors.lastname: Hahn
authors.affiliation: Institute of Computational Biology, HMGU-German Research Center for Environmental Health, Ingolstädter Landstraße 1, Neuherberg, 85764, Germany. massopust@ma.tum.de.|Centre of Mathematics, Research Unit M6, Technische Universität München, Boltzmannstrasse 3, Garching bei München, 85747, Germany. massopust@ma.tum.de.
authors.forename: Peter R
authors.initials: PR
authors.lastname: Massopust
authors.affiliation: Novosibirsk State University, Institute of Computational Mathematics and Mathematical Geophysics, Siberian Branch of Russian Academy of Sciences, Novosibirsk, Russia. sergeim.prigarin@gmail.com.
authors.forename: Sergei
authors.initials: S
authors.lastname: Prigarin
mesh_terms: D000465:Algorithms; D001921:Brain / Q000502:physiology*; D003863:Depression / Q000235:genetics* / Q000473:pathology; D017709:Fractals; D053263:Gene Regulatory Networks; D006801:Humans; D008962:Models, Theoretical; D009415:Nerve Net