Community Detection Methods based on Network Communicability

We propose a series of methods for detecting communities based on the concept of communicability between nodes in a complex network. These method are based on a relaxed definition of community C as a subset of nodes for which the intracluster communicability is larger than the intercluster one for most, but not necessarily all, of the pairs of nodes in C . The first method proposed is a modification of the Girvan-Newman algorithm that considers the communicability graph associated to a network instead of the network itself. The communicability graph

of a network is build using the same set of nodes but connecting two nodes if, and only if they have larger intra- than intercluster communicability. Two other methods are proposed on the basis of the communicability graph. They are based on similarity techniques using the adjacency and distance matrices of the communicability graph. A fourth method uses a real-value communicability matrix of a network as a similarity between nodes. In general, we have shown that the communicability-based techniques produce partitions with better modularity than the classical algorithms. In particular, the method using the communicability matrix produces the best results reported so far for partitioning two classically used networks with known partitions. Communities play fundamental organizational and functional roles in 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 series of new techniques 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. One of these methods, which build the similarity between nodes on the basis of the communicability matrix of the network, produces partitions displaying the highest modularity reported so far for some real-world networks with known community structures. I. INTRODUCTION Complex networks are the structural skeleton of complex systems, which are ubiquitous 1-3 in nature, society and technology. A network is represented by a graph, G = ( V , E ) , where the set of nodes V represents the entities of the system and the set of links E represents the 2 (binary) relationship between these entities. A ‘microscopic’ analysis of a complex network is possible by considering its local topological properties, i.e., those derived from the analysis of close environments around individual nodes and links. Some examples of these local 4 properties are those of centrality, such as degree, closeness, betweenness, etc., or network 5 6 motifs and graphlets, which are small subgraphs centred at a given node. On the other side of the scale we can study some ‘macroscopic’ properties of these complex networks by analyzing their global topological properties. Some examples of these global properties are 7 8 9 10 degree distributions, ‘small-worldness’, self-similarity, good expansion properties, etc. However, a closer inspection of the structure of...

Website: www.mathstat.strath.ac.uk | Filesize: -
No of Page(s): 35
Source to download Community Detection Methods based on Network Communicability.