Source-linked AI summary
A sequential algorithm for fast clique percolation
Jussi M. Kumpula, Mikko Kivela, Kimmo Kaski, Jari Saramaki
TL;DR
Community detection in weighted and unweighted networks needs a fast method that handles chosen clique sizes, overlap, and hierarchical structure. The paper introduces SCP, which sequentially inserts links while tracking newly formed cliques and their communities. Its runtime scales linearly with the number of k-cliques, and it supports multiple weight thresholds and dendrogram construction in one run.
Problem
Community detection requires methods that accommodate weighted networks and hierarchical communities, where topology alone may be insufficient in dense weighted networks.
Method
SCP sequentially inserts network links, detects k-cliques completed by each link, and tracks community formation and merging.
Results
The SCP runtime grows practically linearly with the number of k-cliques, and the method supports community detection across weight thresholds with dendrogram representations.
Takeaways & Limitations
SCP provides a fast way to study nested k-clique communities in weighted networks, including product association networks.
Takeaways & Limitations
The method performs best for small k when networks contain large cliques, and can become extremely slow for k > 10 in the largest CM networks.
Abstract
from arXiv · showhide
In complex network research clique percolation, introduced by Palla et al., is a deterministic community detection method, which allows for overlapping communities and is purely based on local topological properties of a network. Here we present a sequential clique percolation algorithm (SCP) to do fast community detection in weighted and unweighted networks, for cliques of a chosen size. This method is based on sequentially inserting the constituent links to the network and simultaneously keeping track of the emerging community structure. Unlike existing algorithms, the SCP method allows for detecting k-clique communities at multiple weight thresholds in a single run, and can simultaneously produce a dendrogram representation of hierarchical community structure. In sparse weighted networks, the SCP algorithm can also be used for implementing the weighted clique percolation method recently introduced by Farkas et al. The computational time of the SCP algorithm scales linearly with the number of k-cliques in the network. As an example, the method is applied to a product association network, revealing its nested community structure.
I. INTRODUCTION
Community detection requires definitions that address locality, overlap, weighting, hierarchy, and algorithmic scalability. The paper introduces SCP as a rapid implementation of clique percolation for chosen clique sizes, especially weighted networks.
- Community definitions must determine whether properties are local or global, memberships overlap, networks are weighted, and communities form nested hierarchies.
- SCP implements deterministic clique percolation using local topology and supports overlapping community memberships.
- Unlike implementations that first enumerate maximal cliques for all k, SCP rapidly detects communities for a chosen k by sequentially inserting links.
- The paper applies SCP to weighted networks containing hierarchical communities and examines its scaling and use on a product association network.
II. THE SCP ALGORITHM
The SCP algorithm defines k-cliques and k-communities, then detects communities in two linked phases. It focuses on storing communities as they emerge while links are sequentially inserted.
- A k-clique is a fully connected set of k nodes, while a k-community joins k-cliques through overlaps of k −1 nodes.
- The method commonly targets k = 3 or k = 4, which the paper identifies as useful values in practical applications.
- SCP has two phases: detecting k-cliques formed by inserted links, then tracking the formation and merging of k-communities.
A. Phase I: Detecting the k-cliques
Phase I identifies every new k-clique completed by each inserted link. It uses common neighbors of the link’s endpoints and searches for the required smaller cliques among them.
- A newly inserted link between vi and vj can create a k-clique only when both endpoints have degree at least k −1.
- The algorithm collects common neighbors Nij = Ni∩Nj, where each contained (k −2)-clique completes a newly formed k-clique with the inserted link.
- For k = 4, connected pairs in Nij generate new 4-cliques, while for 3-cliques the required smaller cliques are single nodes.
- In the illustrated case, the inserted link generates three 4-cliques and one 5-clique.
B. Phase II: Detecting the k-communities
Phase II tracks k-community formation and merging by representing overlap through (k −1)-cliques. Sequential updates to connected components yield the communities without explicitly constructing the full projected network.
- Phase II detects overlaps between each incoming k-clique and existing communities, updating community structure locally as cliques arrive.
- A bipartite network of k-cliques and (k −1)-cliques has connected components corresponding to k-clique communities.
- The (k −1)-clique projection Γ∗ uses nodes for (k −1)-cliques and links between sub-cliques belonging to the same k-clique.
- SCP sequentially builds Γ∗ from detected k-cliques while tracking its connected components, which represent the evolving communities.
- The implementation avoids constructing Γ∗ and instead tracks component indices with disjoint-set forests.
- After all cliques are processed, original-network nodes are assigned to communities using the component indices of their corresponding (k −1)-cliques.
C. Scaling of the algorithm
SCP runtime is practically linear in the number of k-cliques across tested networks, while network-size scaling depends on how clique counts grow. Large cliques can make high-k analyses slow, although sparse networks with small cliques remain tractable.
- Scaling results: Runtime grows practically linearly with the number of k-cliques for all tested networks.The analysis used GN, WSN, and CM networks with adjustable sizes.
- Scaling results: For GN and WSN networks, runtime also appears linear in network size because their local structure remains essentially unchanged as networks grow.
- Scaling results: CM runtime grows faster than linearly with network size because projection-induced large cliques generate rapidly increasing numbers of k-cliques.The number of k-cliques within a clique of size s grows as the k-th power of s for large s.
- Practical limits: For networks containing large cliques, SCP performs best for relatively small k; analyses with k > 10 became extremely slow on the largest CM networks.
- Practical limits: Detecting 4-clique communities in a mobile-phone network with approximately 4 million nodes and 6 million links took approximately one minute on a standard desktop computer.
- Comparison: Compared with CFinder 1.21 on GN networks, SCP scaled linearly with network size after summing SCP times across all k, whereas CFinder appeared to scale as N^2.The comparison is complicated because CFinder processes all clique sizes while SCP is limited to one k per run.
A. Thresholding and nested communities
Weighted networks can require thresholding or direct use of weights, while a single threshold may miss hierarchical community structure. SCP supports threshold sweeps and dendrograms that expose nested k-communities.
- Weighted networks may require thresholding because dense topology can obscure structure encoded in link weights.
- Thresholding removes links with insignificantly small weights, but selecting one threshold is non-trivial and may warrant multiple resolutions.
- SCP processes links in descending weight order, yielding the k-community structure for every corresponding threshold in one run.
- Tracking community emergence and merging across thresholds preserves nested structure that can be lost when only one threshold is examined.
- Dendrograms encode communities as horizontal lines and merges as branches, with a threshold represented by a vertical slice.
- Figure 4 visualizes Huuto.net product-category communities for k = 3 and k = 4, displaying only communities larger than k.The network contains N = 345 product-category nodes; the display threshold is N_th = k.
B. Weighted k-clique percolation
Weighted clique percolation can use clique intensities rather than thresholded links. SCP adapts by detecting, weighting, sorting, and then processing all k-cliques, with additional memory and dense-network costs.
- Farkas et al.’s weighted clique percolation assigns each k-clique an intensity equal to the geometric mean of its edge weights.
- SCP implements intensity-based percolation by storing all k-cliques, calculating intensities, sorting them, and processing them sequentially.
- Intensity-based processing requires all k-cliques in memory alongside (k −1)-cliques, with clique sorting adding log-linear computational work.
- In dense networks, the number of k-cliques can make individual processing costly, and intensity-based percolation cannot stop early because all cliques must first be detected and sorted.
IV. CONCLUSIONS
The paper introduces SCP, which inserts edges sequentially while tracking emerging k-clique communities. Its processing time scales linearly with the number of k-cliques in test networks.
- SCP detects k-clique communities by sequentially inserting network edges and tracking the communities that emerge.
- SCP is designed for dense weighted networks where thresholding links or formed cliques is needed to obtain meaningful structural information.
- Computational time scales linearly with the number of k-cliques in test networks.