March 28, 2011 to April 20, 2011
Europe/Stockholm timezone

Significant communities in large sparse networks

Apr 6, 2011, 1:50 PM


Atieh Mirshahvalad (IceLab, Umeå University)


Researchers use community-detection algorithms to reveal large-scale organization in biological and social systems modeled by networks. But this community detection approach is useful only if the communities are significant and not a result of noisy data. To assess the statistical significance of the detected structure, the robustness of the network communities, one approach is to perturb the network structure and measure how much the communities change. However, perturbing sparse networks is challenging because they are inherently sensitive; the networks easily shatter if we perturb the networks by removing links. Here we propose a method to perturb sparse networks and assess the significance of their communities. In our approach, we first resample the network by adding extra links based on local information and then we aggregate the information from multiple re-sampled networks to find a coarse-grained description of significant clusters. We test our method both on benchmark and real-world networks, and find good performance on inherently sensitive sparse networks.

Presentation materials

There are no materials yet.