Community detection in complex networks

Introduction and background

Most networks are not homogenious, meaning that some sets of nodes are more connected among themselves than to the rest of the network. The aim of community detection is to study this mezo-scale structure and devise algorithms that would identify these sets of nodes.

Our work

The result of any community detection algorithm is one possible split of network into groups. In order to asses the quality and meaningfulness of this split one needs to compare it with some other source of node classification. One such source can be nodes’ metadata – extra pieces of information about each node that naturally puts them into different classes. For social networks where nodes are people this metadata can be persons’ gender, age, location, or political alignment, in gene regulatory networks each gene has a set of roles, etc.

Ideally, these two classifications would be the same, or very similar. By comparing the results of several most commonly used community detection algorithms with metadata classes we found that there is no clear correspondence. For this we used real-world networks of different nature, but this had little effect on the conclusion.

Publications

L. Cantini, E. Medico, S. Fortunato, M. Caselle Detection of gene communities in multinetworks reveals cancer drivers Scientific reports 5, 17386 (2015)

C. Orsini, M. M. Dankulov, P. Colomer-de-Simon, A. Jamakovic, P. Mahadevan, A. Vahdat, K. E. Bassler, Z. Toroczkai, M. Boguna, G. Caldarelli, S. Fortunato, D. Krioukov Quantifying randomness in real networks Nature Communications 6, 8627 (2015)

C. Granell, R. K. Darst, A. Arenas, S. Fortunato, S. Gomez Benchmark model to assess community structure in evolving networks Physical Review E 92, 012805 (2015)

G. Bianconi, R. K. Darst, J. Iacovacci, S. Fortunato Triadic closure as a basic generating mechanism of communities in complex networks Physical Review E 90, 042806 (2014)

D. Hric, R. K. Darst, S. Fortunato Community detection in networks: Structural communities versus ground truth Physical Review E 90, 062805 (2014)

S. Fortunato, J. Saramaki, J.-P. Onnela Adding network structure onto the map of collective behavior Behavioral and Brain Sciences 37, 82-83 (2014)

R. K. Darst, Z. Nussinov, S. Fortunato Improving the performance of algorithms to find communities in networks Physical Review E 89, 032809 (2013)