Detecting the overlapping and hierarchical community structure in complex networks

By Andrea Lancichinetti, Santo Fortunato, János Kertész. 2008

1,934 citations recorded by the source corpus.

Many networks in nature, society and technology are characterized by a mesoscopic level of organization, with groups of nodes forming tightly connected units, called communities or modules, that are only weakly linked to each other. Uncovering this community structure is one of the most important problems in the field of complex networks. Networks often show a hierarchical organization, with communities embedded within other communities; moreover, nodes can be shared between different communities. Here, we present the first algorithm that finds both overlapping communities and the hierarchical structure. The method is based on the local optimization of a fitness function. Community structure is revealed by peaks in the fitness histogram. The resolution can be tuned by a parameter enabling different hierarchical levels of organization to be investigated. Tests on real and artificial networks give excellent results.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/2efae1bfccab8c45fed26065f602863cf7f4b842

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Detecting highly overlapping community structure by greedy clique expansion (2010, methodology): “, one cannot argue that any given ﬁtness function will be appropriate for all types of network data. Nevertheless, in our experiments, we found that the ﬁtness function deﬁned by Lancichinetti et al. [14] provided good results on a wide range of synthetic and empirical data. They deﬁne the ﬁtness of”
Consensus clustering in complex networks (2012, background): “The most typical scenario is when the seeked partition or individual clusters correspond to extrema of a cost functio”
Communities in Networks (2009, methodology): “yield smaller communities (and vice versa). Resolution parameters have now been incorporated (both explicitly and implicitly) into several methods that use modularity [10,95], other quality functions [5,61], and other perspectives [7,88]. Although introducing a resolution parameter into equations li”
SLPA: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process (2011, background): “For this reason, overlapping community detection algorithms have been investigated.”
Walklets: Multiscale Graph Embeddings for Interpretable Network Classification (2016, background): “Multiscale Community Detection Many techniques for detecting multiple scales of discrete communities in graphs have been proposed [1, 10, 15].”
Complex Network Clustering by Multiobjective Discrete Particle Swarm Optimization Based on Decomposition (2014, background): “Lancichinetti et al. [51] have introduced the concept of community fitness (CF) and Pizzuti [7] has put forward the community score (CS) criteria to stop the division of the network.”
Link communities reveal multiscale complexity in networks (2009, background): “6,7,9,10,14,15 Pervasive overlap in real networks is distinct from ‘fuzzy’ community overlap with relaxed interfaces, 19–21 because overlap can exist for each and every node (Fig.”
Community detection in graphs (2009, methodology): “…the average similarity used by Ronhovde and Nussinov (Ronhovde and Nussinov, 2008; Ronhovde and Nussinov, 2009)) than on properties of the individual partitions (like the measures of occurrence used by Arenas et al. (Arenas et al., 2008b) and by Lancichinetti et al. (Lancichinetti et al., 2009)).”
A classification for community discovery methods in complex networks (2011, methodology): “) 108k 330k 2005 [34] Bridge Edge Betweenness X X O(m2n) 271 1k 2002 [4] CONGO* X X O(nlogn) 30k 116k 2008 [35] L-Shell X X O(n3) 77 254 2005 [36] Internal-External Degree X O(n2 logn) 775k 4.7M 2009 [37] Diﬀusion Label Propagation X X X O(m +n) 374k 30M 2007 [38] Node Colouring X X O(ntk2) 2k ? 200”
Overlapping community detection in networks: The state-of-the-art and comparative study (2011, methodology): “LFM [Lancichinetti et al. 2009] expands a community from a random seed node to form a natural community until the fitness function”
Community Discovery in Dynamic Networks (2017, neutral): “…on slight modiﬁca-tions of a network, in term of their modularity (New-man, 2004; Newman and Girvan, 2004), Normalized Mu-tual Information (NMI (Lancichinetti et al. , 2008)) be-9 tween successive results, and number of transformations between two consecutive runs (a transformation being the…”
Finding Statistically Significant Communities in Networks (2010, neutral): “Such type of local optimization was originally implemented in the Local Fitness Method [23], to handle overlapping communities.”
Towards Linear Time Overlapping Community Detection in Social Networks (2012, methodology): “NMI measures the fraction of nodes in agreement in two covers, while Omega is based VI on pairs of nodes.”
Tracking the Evolution of Communities in Dynamic Social Networks (2010, methodology): “We can use the generalised form of Normalised Mutual Information (NMI) introduced in [17] to compare the memberships of nodes in this grouping relative to those in the grouping derived in the same manner on the ground truth dynamic communities at the same time step.”