A new method to measure complexity in binary or weighted networks and applications to functional connectivity in the human brain

BMC Bioinformatics

Methodology Article

Klaus Hahn¹  Peter R. Massopust²  Sergei Prigarin³ 

[1] Institute of Computational Biology, HMGU–German Research Center for Environmental Health, Ingolstädter Landstraße 1, 85764, Neuherberg, Germany;Institute of Computational Biology, HMGU–German Research Center for Environmental Health, Ingolstädter Landstraße 1, 85764, Neuherberg, Germany;Centre of Mathematics, Research Unit M6, Technische Universität München, Boltzmannstrasse 3, 85747, Garching bei München, Germany;Novosibirsk State University, Institute of Computational Mathematics and Mathematical Geophysics, Siberian Branch of Russian Academy of Sciences, Novosibirsk, Russia;

关键词: Network analysis;    Complexity measure;    Computational algorithm;    Fractal dimension;    Human brain application;    Functional connectivity;   

DOI  :  10.1186/s12859-016-0933-9

 received in 2015-10-02, accepted in 2016-01-29,  发布年份 2016

来源: Springer

【 摘 要 】

BackgroundNetworks 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 ℝn\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$\mathbb {R}^{n}$\end{document}.ResultsThe 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.ConclusionWe 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.

【 授权许可】

CC BY   
© Hahn et al. 2016

【 图 表 】

Fig. 2

Fig. 2

Fig. 3

Fig. 2

Fig. 4

12936_2017_2051_Article_IEq54.gif

Fig. 1

Fig. 12

12936_2015_966_Article_IEq12.gif

Fig. 5

12936_2016_1315_Article_IEq9.gif

Fig. 3

Fig. 4

12944_2023_1932_Article_IEq4.gif

Fig. 1

Fig. 5

12944_2023_1932_Article_IEq1.gif

Fig. 3

Fig. 1

Fig. 5

Fig. 4

Fig. 2

12936_2016_1315_Article_IEq8.gif

Fig. 5

Fig. 3

Fig. 2

Fig. 1

Fig. 1

Fig. 1

Fig. 2

12864_2017_4133_Article_IEq35.gif

Fig. 3

Fig. 3

Fig. 2

Fig. 1

Fig. 2

Fig. 1

Fig. 5

12951_2016_171_Article_IEq6.gif

Fig. 1

Fig. 4

12951_2015_155_Article_IEq91.gif

Fig. 1

Fig. 1

12951_2016_225_Article_IEq2.gif

Fig. 3

Fig. 6

Fig. 11