Communicability in complex networks

Ernesto Estrada and Naomichi Hatano

Phys. Rev. E 77, 036111 – Published 11 March 2008

Abstract

We propose a new measure of the communicability of a complex network, which is a broad generalization of the concept of the shortest path. According to the new measure, most of the real-world networks display the largest communicability between the most connected (popular) nodes of the network (assortative communicability). There are also several networks with the disassortative communicability, where the most “popular” nodes communicate very poorly to each other. Using this information we classify a diverse set of real-world complex systems into a small number of universality classes based on their structure-dynamic correlation. In addition, the new communicability measure is able to distinguish finer structures of networks, such as communities into which a network is divided. A community is unambiguously defined here as a set of nodes displaying larger communicability among them than to the rest of the nodes in the network.

Received 21 August 2007

DOI:https://doi.org/10.1103/PhysRevE.77.036111

Authors & Affiliations

Ernesto Estrada^1,* and Naomichi Hatano²

¹Complex Systems Research Group, X-rays Unit, RIAIDT, Edificio CACTUS, University of Santiago de Compostela, 15076 Santiago de Compostela, Spain
²Institute of Industrial Science, University of Tokyo, 4-6-1 Komaba, Meguro, Tokyo 153-8505, Japan

^*Corresponding author; FAX: +34 981 547 077; estrada66@yahoo.com

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 77, Iss. 3 — March 2008

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
(Color online) Simple illustration of networks with homogeneous and nonhomogeneous structures as well as their typical scaling between a local and a global property of nodes.Reuse & Permissions
Figure 2
Illustration of three different organizations of nodes in networks and their communicability patterns. The contour plot represents the relative communicability between every pair of nodes as a function of their degrees $(k_{p}, k_{q})$ . (a) Superhomogeneous network where the information can flow among hubs without passing through structural bottlenecks. A superhomogeneous network displays the largest communicability between the most connected nodes (gray nodes) and the lowest communicability between the nodes of low degree (white nodes), i.e., assortative communicability. (b) Network formed by two (or more) clusters of highly interconnected nodes which have very few intercluster connections (bottleneck). In this case the hubs (gray nodes) of one cluster are directly connected to the hubs of the other. Consequently, the communicability pattern is of the assortative (AC) type. (c) Network with two (or more) clusters in which the “information” arising at the hubs (gray nodes) of one cluster needs to travel through the bottleneck to reach the hubs (gray nodes) of the other cluster. This network displays an “atypical” disassortative communicability pattern in which hubs are better communicated with nodes of low degree and the interhub communicability is poor.Reuse & Permissions
Figure 3
Communicability degree contour plots for several real-world networks. The first two plots are typical of networks with assortative communicability (AC) and the network structures correspond to cases like the ones illustrated in Figs. 2a, 2b. The plot in (c) also corresponds to AC but due to the large preference of the hubs to be attached to low-degree nodes the interhub communicability is reduced. The last three cases correspond to typical disassortative communicability (DC) patterns. The corresponding networks have structures that match the topology illustrated in Fig. 2c. (a) The airport network in the USA in 1997. (b) The semantic network of the Roget’s thesaurus. (c) The food web of Bridge Brook. (d) The direct transcription network between genes of yeast. (e) The social network of injecting drug users. (f) The social network of people with HIV infection in Colorado Springs during the period of 1985–1999.Reuse & Permissions
Figure 4
(a) Illustration of the process of identifying communities in a simple network at the top of the figure. (b) A representation of the signed complete graph for the network in (a), where the black lines indicate negative $Δ G_{p q}$ and the gray fat ones indicate positive $Δ G_{p q}$ . (c) The four completely positive cliques existing in the network. (d) Identification of the communities by grouping the positive (gray) entries of the adjacency matrix. (e) Illustration of the different communities in the network and their overlapping.Reuse & Permissions
Figure 5
(Color online) The community structure of the Zachary karate club network. The two factions in which the network was divided are illustrated in different shapes of the nodes (and color online). The matrix plot illustrates the values of $Δ G_{p q}$ for every pair of nodes $(p, q)$ in the network. A positive value of $Δ G_{p q}$ (dark contour) indicates that the pair of nodes is in the same community and a negative value of $Δ G_{p q}$ (clear contour) indicates that the pair is in different communities. The nodes are ordered according to their values of $Δ G_{p q}$ in decreasing order.Reuse & Permissions
Figure 6
Example illustrating the overlapping between two groups or neighborhoods formed among the followers of the administrator (node 34) in the Zachary karate club network.Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics