Detect overlapping and hierarchical community structure in networks

By Huawei Shen, Xueqi Cheng, Kai Cai, Maobin Hu. arXiv.org, 2008

719 citations recorded by the source corpus.

Clustering and community structure is crucial for many network systems and the related dynamic processes. It has been shown that communities are usually overlapping and hierarchical. However, previous methods investigate these two properties of community structure separately. This paper proposes an algorithm (EAGLE) to detect both the overlapping and hierarchical properties of complex community structure together. This algorithm deals with the set of maximal cliques and adopts an agglomerative framework. The quality function of modularity is extended to evaluate the goodness of a cover. The examples of application to real world networks give excellent results.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/84360cc9277253fadf40c854b9dc055964129105

How researchers see this paper

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

In Artificial Intelligence

1. Huan Liu
2. Fosca Giannotti
3. Dino Pedreschi
4. Chuan Zhou
5. Lei Tang
6. Michele Coscia
7. Punam Bedi
8. Chhavi Sharma

In Statistical and Nonlinear Physics

1. Punam Bedi
2. Chhavi Sharma
3. Jure Leskovec
4. Fosca Giannotti
5. Dino Pedreschi
6. Michele Coscia
7. Huan Liu
8. Lei Tang

Citations in the corpus

• Scalable Learning of Collective Behavior (2012, background): “A similar idea is presented in [32], in which the authors propose to find out all the maximal cliques of a network and then perform hierarchical clustering.”
• Community detection in graphs (2009, background): “[216], for instance, suggested the simple definition”
• Detecting highly overlapping community structure by greedy clique expansion (2010, background): “We note that other CAAs exploit these properties of cliques [9, 16, 19], but none of them utilize cliques as seeds in the greedy expansion strategy mentioned above.”
• Community detection in social networks (2016, methodology): “EAGLE, an agglomerativE hierarchicAl clusterinG based on maximaL cliquE algorithm has been proposed by Shen et al. 77 In the fi rst step, maximal cliques are discovered, and those smaller than a threshold are discarded.”
• A classification for community discovery methods in complex networks (2011, methodology): “The methods reviewed here are: clique percolation [3] and its evolution for bipartite graphs [48], the s-plexes detection [47] and a maximal clique approach [49].”
• A Comprehensive Survey on Community Detection With Deep Learning (2021, background): “Networks, such as the Web, often show a treelike hierarchical organization of communities at different scales, in which small communities at lower levels group together to form larger ones in higher levels [170].”
• Towards Linear Time Overlapping Community Detection in Social Networks (2012, background): “Algorithm Complexity Imp CFinder [11], 2005 C++ LFM [7], 2009 O(n(2)) C++ EAGLE [14], 2009 O(n(2)s) C++ CIS [6], 2009 O(n(2)) C++ GCE [9], 2010 O(mh) C++ COPRA [5], 2010 O(vm log(vm/n)) Java NMF [12], 2010 O(Kn(2)) Matlab Link [1], 2010 O(nk(2) max) C++ SLPA, 2011 O(Tm) C++ Table 2: The ranking of a”
• Overlapping community detection in networks: The state-of-the-art and comparative study (2011, methodology): “2009] O(n(2)) C++ EAGLE [Shen et al. 2009] O(n(2) + (h + n)s) C++ CIS [Kelley 2009] O(n(2)) C++ GCE [Lee et al.”