Community detection based on network communicability

Estrada, Ernesto (2011) Community detection based on network communicability. Chaos, 21 (1). (https://doi.org/10.1063/1.3552144)

[thumbnail of Communties_Chaos_Revised.doc] Microsoft Word. Filename: Communties_Chaos_Revised.doc
Preprint
Download (3MB)

Abstract

We propose a new method for detecting communities based on the concept of communicability between nodes in a complex network. This method, designated as N-ComBa K-means, uses a normalized version of the adjacency matrix to build the communicability matrix and then applies K-means clustering to find the communities in a graph. We analyze how this method performs for some pathological cases found in the analysis of the detection limit of communities and propose some possible solutions on the basis of the analysis of the ratio of local to global densities in graphs. We use four different quality criteria for detecting the best clustering and compare the new approach with the Girvan-Newman algorithm for the analysis of two ‘classical’ networks: karate club and bottlenose dolphins. Finally, we analyze the more challenging case of homogeneous networks with community structure, for which the Girvan-Newman completely fails in detecting any clustering. The N-ComBa K-means approach performs very well in these situations and we applied it to detect the community structure in an international trade network of miscellaneous manufactures of metal having these characteristics. Some final remarks about the general philosophy of community detection are also discussed. Communities play fundamental organizational and functional roles in many networks representing complex systems. Most of the algorithms used to detect these structures use information directly contained in the topology of these networks, such as adjacency and distance relationships. This paper proposes a new technique for identifying communities using the concept of network communicability, which is based on walks on networks. Nodes are grouped into communities according to their capacity of communicating better among them than with outsiders. We analyze the problem of detection limit and propose some possible solutions for the method introduced here based on the analysis of local-to-global densities in networks. A more challenging example consisting of a super-homogeneous network with communities is presented and the advantages of using the current approach are analyzed.

ORCID iDs

Estrada, Ernesto ORCID logoORCID: https://orcid.org/0000-0002-3066-7418;
CORE (COnnecting REpositories)