Clique percolation method
Encyclopedia
The clique percolation method is a popular approach for analyzing the overlapping community structure
of networks
. The term network community (also called a module, cluster or cohesive group)
has no widely accepted unique definition and it is usually defined as a group of nodes that are more densely connected to each other than to other nodes in the network. There are numerous alternative methods for detecting communities in networks, for example, the Girvan–Newman algorithm, hierarchical clustering
or modularity maximization.
, which correspond to complete (fully connected) sub-graphs of k nodes. (E.g., a k-clique at k = 3 is equivalent to a triangle). Two k-cliques are considered adjacent if they share k − 1 nodes. A community is defined as the maximal union of k-cliques that can be reached from each other through a series of adjacent k-cliques. Such communities can be best interpreted with the help of a k-clique template (an object isomorphic to a complete graph of k nodes). Such a template can be placed onto any k-clique in the graph, and rolled to an adjacent k-clique by relocating one of its nodes and keeping its other k − 1 nodes fixed. Thus, the k-clique communities of a network are all those sub-graphs that can be fully explored by rolling a k-clique template in them, but cannot be left by this template.
This definition allows overlaps between the communities in a natural way, as illustrated in in Fig.1, showing four k-clique communities at k = 4. The communities are color coded and the overlap between them is emphasized in red. The definition above is also local: if a certain sub-graph fulfils the criteria to be considered as a community, then it will remain a community independent of what happens to another part of the network far away. In contrast, when searching for the communities by optimizing with respect to a global quantity, a change far away in the network can reshape the communities in the unperturbed regions as well. Furthermore, it has been shown that global methods can suffer from a resolution limit problem, where the size of the smallest community that can be extracted is dependent on the system size. A local community definition such as here circumvents this problem automatically.
Since even small networks can contain a vast number of k-cliques, the implementation of this approach is based on locating the maximal cliques rather than the individual k-cliques. Thus, the complexity of this approach in practice is equivalent to that of the NP-complete
maximal clique finding, (in spite that finding k-cliques is polynomial). This means that although networks with few million nodes have already been analyzed successfully with this approach, no prior estimate can be given for the runtime of the algorithm based simply on the system size.
of the k (k - 1) / 2 link weights within the k-clique is greater than a selected threshold value, I. The weighted Clique Percolation Method defines weighted network communities as the percolation clusters of weighted k-cliques. Note that the geometric mean of link weights within a subgraph is called the intensity of that subgraph .
shows a series of interesting transitions when the probability p of two nodes being connected is increased. For each k one can find a certain threshold probability pc above which the k-cliques organize into a giant community. (The size of the giant community is comparable to the system size, in oder words the giant community occupies a finite part of the system even in the thermodynamic limit.) This transition is analogous to the percolation transition
in statistical physics
. A similar phenomenon can be observed in many real networks as well: if k is large, only the most densely linked parts are accepted as communities, thus, they usually remain small and dispersed. When k is lowered, both the number and the size of the communities start to grow. However, in most cases a critical k value can be reached, below which a giant community emerges, smearing out the details of the community structure by merging (and making invisible) many smaller communities.
through various social network
s to document clustering and economical networks.
Community structure
In the study of complex networks, a network is said to have community structure if the nodes of the network can be easily grouped into sets of nodes such that each set of nodes is densely connected internally...
of networks
Social network
A social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...
. The term network community (also called a module, cluster or cohesive group)
has no widely accepted unique definition and it is usually defined as a group of nodes that are more densely connected to each other than to other nodes in the network. There are numerous alternative methods for detecting communities in networks, for example, the Girvan–Newman algorithm, hierarchical clustering
Hierarchical clustering
In statistics, hierarchical clustering is a method of cluster analysis which seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two types:...
or modularity maximization.
Clique Percolation Method (CPM)
The clique percolation method builds up the communities from k-cliquesClique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
, which correspond to complete (fully connected) sub-graphs of k nodes. (E.g., a k-clique at k = 3 is equivalent to a triangle). Two k-cliques are considered adjacent if they share k − 1 nodes. A community is defined as the maximal union of k-cliques that can be reached from each other through a series of adjacent k-cliques. Such communities can be best interpreted with the help of a k-clique template (an object isomorphic to a complete graph of k nodes). Such a template can be placed onto any k-clique in the graph, and rolled to an adjacent k-clique by relocating one of its nodes and keeping its other k − 1 nodes fixed. Thus, the k-clique communities of a network are all those sub-graphs that can be fully explored by rolling a k-clique template in them, but cannot be left by this template.
This definition allows overlaps between the communities in a natural way, as illustrated in in Fig.1, showing four k-clique communities at k = 4. The communities are color coded and the overlap between them is emphasized in red. The definition above is also local: if a certain sub-graph fulfils the criteria to be considered as a community, then it will remain a community independent of what happens to another part of the network far away. In contrast, when searching for the communities by optimizing with respect to a global quantity, a change far away in the network can reshape the communities in the unperturbed regions as well. Furthermore, it has been shown that global methods can suffer from a resolution limit problem, where the size of the smallest community that can be extracted is dependent on the system size. A local community definition such as here circumvents this problem automatically.
Since even small networks can contain a vast number of k-cliques, the implementation of this approach is based on locating the maximal cliques rather than the individual k-cliques. Thus, the complexity of this approach in practice is equivalent to that of the NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
maximal clique finding, (in spite that finding k-cliques is polynomial). This means that although networks with few million nodes have already been analyzed successfully with this approach, no prior estimate can be given for the runtime of the algorithm based simply on the system size.
Directed Clique Percolation Method (CPMd)
On a network with directed links a directed k-clique is a complete subgraph with k nodes fulfilling the following condition. The k nodes can be ordered such that between an arbitrary pair of them there exists a directed link pointing from the node with the higher rank towards the node with the lower rank. The directed Clique Percolation Method defines directed network communities as the percolation clusters of directed k-cliques.Weighted Clique Percolation Method (CPMw)
On a network with weighted links a weighted k-clique is a complete subgraph with k nodes such that the geometric meanGeometric mean
The geometric mean, in mathematics, is a type of mean or average, which indicates the central tendency or typical value of a set of numbers. It is similar to the arithmetic mean, except that the numbers are multiplied and then the nth root of the resulting product is taken.For instance, the...
of the k (k - 1) / 2 link weights within the k-clique is greater than a selected threshold value, I. The weighted Clique Percolation Method defines weighted network communities as the percolation clusters of weighted k-cliques. Note that the geometric mean of link weights within a subgraph is called the intensity of that subgraph .
Percolation transition in the CPM
The Erdős–Rényi modelErdos–Rényi model
In graph theory, the Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges...
shows a series of interesting transitions when the probability p of two nodes being connected is increased. For each k one can find a certain threshold probability pc above which the k-cliques organize into a giant community. (The size of the giant community is comparable to the system size, in oder words the giant community occupies a finite part of the system even in the thermodynamic limit.) This transition is analogous to the percolation transition
Percolation
In physics, chemistry and materials science, percolation concerns the movement and filtering of fluids through porous materials...
in statistical physics
Statistical physics
Statistical physics is the branch of physics that uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approximations, in solving physical problems. It can describe a wide variety of fields with an inherently stochastic...
. A similar phenomenon can be observed in many real networks as well: if k is large, only the most densely linked parts are accepted as communities, thus, they usually remain small and dispersed. When k is lowered, both the number and the size of the communities start to grow. However, in most cases a critical k value can be reached, below which a giant community emerges, smearing out the details of the community structure by merging (and making invisible) many smaller communities.
Applications
The clique percolation method is implemented by CFinder http://www.cfinder.org (freeware for non-commercial use) software for detecting and visualizing overlapping communities in networks. The program enables customizable visualization and allows easy strolling over the found communities. The package contains a command line version of the program as well, which is suitable for scripting. The clique percolation method had been used to detect communities from the studies of cancer metastasisMetastasis
Metastasis, or metastatic disease , is the spread of a disease from one organ or part to another non-adjacent organ or part. It was previously thought that only malignant tumor cells and infections have the capacity to metastasize; however, this is being reconsidered due to new research...
through various social network
Social network
A social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...
s to document clustering and economical networks.
See also
- Social networkSocial networkA social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...
- Community structureCommunity structureIn the study of complex networks, a network is said to have community structure if the nodes of the network can be easily grouped into sets of nodes such that each set of nodes is densely connected internally...
- Survey Article Communities in Networks
- Review Article Community detection in graphs
- Bibliography of community structure links