2012 · 39 citations · 24 references
ComputingComputer ScienceComplex SystemsData MiningGraph VisualizationCommunity DetectionCommunity StructureGraph AlgorithmsGraph MiningGraph TheorySocial Network AnalysisClique AlgorithmsClique StructureCliquesComplex NetworksNetwork Community DetectionOverlapping Community DetectionPercolationSimple Algorithm
K-clique percolation is an overlapping community finding algorithm which extracts particular structures, comprised of overlapping cliques, from complex networks. While it is conceptually straightforward, and can be elegantly expressed using clique graphs, certain aspects of k-clique percolation are computationally challenging in practice. In this paper we investigate aspects of empirical social networks, such as the large numbers of overlapping maximal cliques contained within them, that make clique percolation, and clique graph representations, computationally expensive. We motivate a simple algorithm to conduct clique percolation, and investigate its performance compared to current best-in-class algorithms. We present improvements to this algorithm, which allow us to perform k-clique percolation on much larger empirical datasets. Our approaches perform much better than existing algorithms on networks exhibiting pervasively overlapping community structure, especially for higher values of k. However, clique percolation remains a hard computational problem, current algorithms still scale worse than some other overlapping community finding algorithms.
24
Santo Fortunato · Physics Reports · 2009 · 11.3K citations · Full text
Multidimensional binary search trees used for associative searching
Jon Bentley · Communications of the ACM · 1975 · 7.5K citations · Full text
Uncovering the overlapping community structure of complex networks in nature and society
Gergely Palla, Imre Derényi, Illés J. Farkas et al. · Nature · 2005 · 5.4K citations · Full text
Algorithm 457: finding all cliques of an undirected graph
Coen Bron, Joep Kerbosch · Communications of the ACM · 1973 · 2.5K citations · Full text
Link communities reveal multiscale complexity in networks
Yong‐Yeol Ahn, James P. Bagrow, Sune Lehmann · Nature · 2010 · 2K citations · Full text