A cluster – also called a community or module – in a network is a group of nodes more densely connected to each other than to nodes outside the group.

In real networks clusters often overlap.

CFinder

• is a free software for finding and visualizing overlapping dense groups of nodes in networks, based on the Clique Percolation Method (CPM) of Palla et. al., Nature 435, 814-818 (2005),
• has been frequently applied to the quantitative description of the evolution of social groups, see, for example: Palla et. al., Nature 446, 664-667 (2007),
• offers a fast and efficient method for clustering data represented by large graphs, such as genetic or social networks and microarray data,
• is also very efficient for locating the cliques of large sparse graphs.

> Download CFinder (12MB zip)

Examples

The overlapping network modules of the word "bright" in a word association network – the South Florida Free Association norms list – represent the different meanings of this word. Communities are color coded, the overlapping nodes and links between them are emphasized in red, and the volume of a ball (the width of a link) is proportional to the total number of communities it belongs to. Parameter values of the algorithm are k=4 (clique size) and w*=0.025 (weight cutoff threshold). From Palla et. al., Nature 435, 814-818 (2005).

The network of protein modules in the protein-protein interaction network of yeast. Overlaps between the communities are shown in red. Top. The network of protein communities in the DIP S. cerevisiae core list of protein-protein interactions. Bottom. "Zoom-in": showing a smaller number of selected clusters. Communities are color coded, the overlapping nodes and links between them are emphasized in red, and the area of a node (the width of a link) is proportional to the total number of communities it belongs to. Clique size parameter: k=4. From Adamcsek et. al., Bioinformatics 22, 1021 (2006).

Structure and schematic dynamics of the two networks considered in Palla et. al., Nature 446, 664 (2007) (this is Figure 1 from the paper). (a) The co-authorship network. The figure shows the local community structure at a given time step in the vicinity of a randomly selected node. (b) As (a) but for the phone-call network. (c, d) Statistical analyses of the network of phone calls. (e) Possible events in community evolution. (f) The identification of evolving communities. The links at t (blue) and the links at t+1 (yellow) are merged into a joint graph (green). Any CPM (Clique Percolation Method) community at t or t+1 is part of a CPM community in the joined graph, so these can be used to match the two sets of communities.

Three of the overlapping directed modules identified by the directed Clique Percolation Method (CPMd) in the directed net of Google's static pages at k=6. From Palla et. al., New J. Phys. 9, 186 (2007). These modules overlap with several further ones not shown in the figure; the size of each node is proportional to the number of its modules. The nodes and links of the three modules are coloured brown, green and blue, while their overlaps (nodes contained by more than one of these three modules) are red. The node marked with a + sign at the centre is the starting page, google.com, and the names of the other nodes are their relative URLs. Observe that each module contains a number of nodes with many incoming links (a "core"), some of which are in the overlaps. Please see the original paper for further details. For the weighted Clique Percolation Method (CPMw), see Farkas et. al., New J. Phys. 9, 180 (2007).

Funding for CFinder was provided by the Hungarian National Science Foundation (OTKA) under Grants No. K-49674, K-68669 and K-75334, and the Hungarian National Office for Research and Technology (NKTH), CellCom RET and TEXTREND.