Coarse-grained diffusion distance for community structure detection in complex networks

One of the most relevant features of complex networks representing real systems is the community structure. In this paper, we extend the measure of diffusion distance between nodes in a network to a generalized form on the coarse-grained network with data parameterization via eigenmaps. This notion of proximity of meta-nodes in the coarse-grained networks reflects the intrinsic geometry of the partition in terms of connectivity of the communities in a diffusion process. Nodes are then grouped into communities through an agglomerative hierarchical clustering technique under this measure and the modularity function is used to select the best partition of the resulting dendrogram. The present algorithm can identify the community structure with a high degree of efficiency and accuracy. An appropriate number of communities can be automatically determined without any prior knowledge about the community structure. The computational results on several artificial and real-world networks confirm the capability of the algorithm.