Detecting Communities in Networks by Merging Cliques

Abstract

Many algorithms have been proposed for detecting disjoint communities (relatively densely connected subgraphs) in networks. One popular technique is to optimize modularity, a measure of the quality of a partition in terms of the number of intracommunity and intercommunity edges. Greedy approximate algorithms for maximizing modularity can be very fast and effective. We propose a new algorithm that starts by detecting disjoint cliques and then merges these to optimize modularity. We show that this performs better than other similar algorithms in terms of both modularity and execution speed.

5 pages, 7 figures

References in corpus (14)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• The structure of scientific collaboration networks
• The large-scale organization of metabolic networks
• Benchmark graphs for testing community detection algorithms
• Self-similar community structure in organisations
• CFinder: Locating cliques and overlapping modules in biological networks
• Extending the definition of modularity to directed graphs with overlapping communities

Cited by in corpus (8)

• Detecting highly overlapping community structure by greedy clique expansion
• Clique Graphs and Overlapping Communities
• Detecting community structure in networks using edge prediction methods
• Replicable Parallel Branch and Bound Search
• Finding overlapping communities in multiplex networks
• Comparison and Benchmark of Graph Clustering Algorithms
• The Atlas for the Aspiring Network Scientist
• Partitioning Breaks Communities