The physics of communicability in complex networks

被引:300
作者
Estrada, Ernesto [1 ,2 ,3 ,4 ]
Hatano, Naomichi [5 ]
Benzi, Michele [6 ]
机构
[1] Univ Strathclyde, Inst Complex Syst, Glasgow G1 1XQ, Lanark, Scotland
[2] Univ Strathclyde, Dept Math & Stat, Glasgow G1 1XQ, Lanark, Scotland
[3] Univ Strathclyde, Dept Phys, Glasgow G1 1XQ, Lanark, Scotland
[4] Univ Strathclyde, SUPA, Glasgow G1 1XQ, Lanark, Scotland
[5] Univ Tokyo, Inst Ind Sci, Meguro Ku, Tokyo 1538505, Japan
[6] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 USA
来源
PHYSICS REPORTS-REVIEW SECTION OF PHYSICS LETTERS | 2012年 / 514卷 / 03期
基金
美国国家科学基金会; 日本学术振兴会;
关键词
ESSENTIAL PROTEINS; STATISTICAL-MECHANICS; EXPANSION PROPERTIES; SUBGRAPH CENTRALITY; BIODIVERSITY LOSS; SPECTRAL GAP; FOOD WEBS; MATRIX; ROBUSTNESS; GRAPHS;
D O I
10.1016/j.physrep.2012.01.006
中图分类号
O4 [物理学];
学科分类号
070305 [高分子化学与物理];
摘要
A fundamental problem in the study of complex networks is to provide quantitative measures of correlation and information flow between different parts of a system. To this end, several notions of communicability have been introduced and applied to a wide variety of real-world networks in recent years. Several such communicability functions are reviewed in this paper. It is emphasized that communication and correlation in networks can take place through many more routes than the shortest paths, a fact that may not have been sufficiently appreciated in previously proposed correlation measures. In contrast to these, the communicability measures reviewed in this paper are defined by taking into account all possible routes between two nodes, assigning smaller weights to longer ones. This point of view naturally leads to the definition of communicability in terms of matrix functions, such as the exponential, resolvent, and hyperbolic functions, in which the matrix argument is either the adjacency matrix or the graph Laplacian associated with the network. Considerable insight on communicability can be gained by modeling a network as a system of oscillators and deriving physical interpretations, both classical and quantum-mechanical, of various communicability functions. Applications of communicability measures to the analysis of complex systems are illustrated on a variety of biological, physical and social networks. The last part of the paper is devoted to a review of the notion of locality in complex networks and to computational aspects that by exploiting sparsity can greatly reduce the computational efforts for the calculation of communicability functions for large networks. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码:89 / 119
页数:31
相关论文
共 142 条
[1]
Statistical mechanics of complex networks [J].
Albert, R ;
Barabási, AL .
REVIEWS OF MODERN PHYSICS, 2002, 74 (01) :47-97
[2]
LAMBDA-1, ISOPERIMETRIC-INEQUALITIES FOR GRAPHS, AND SUPERCONCENTRATORS [J].
ALON, N ;
MILMAN, VD .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 38 (01) :73-88
[3]
EIGENVALUES AND EXPANDERS [J].
ALON, N .
COMBINATORICA, 1986, 6 (02) :83-96
[4]
[Anonymous], GROOMING GOSSIP EVOL
[5]
[Anonymous], THESIS U MUNCHEN MUN
[6]
[Anonymous], INTERNET MA IN PRESS
[7]
[Anonymous], NETWORKS BRAIN
[8]
[Anonymous], ARXIV11054479V1
[9]
[Anonymous], TR2010025 EM U
[10]
[Anonymous], 1999, Thermal Physics