Python implemention of the SCP algorithm
Below is a link to a Python script illustrating the sequential algorithm
for the clique percolation method introduced in the paper
A sequential algorithm
for fast clique percolation . Note that as this script is
written in pure Python without external modules it has some
performance limitations. These are mainly related to the memory
consumption of the network data structure and the data structure of the
disjoint-set forest, but the overal speed also suffers from the
limitations of the Python. See the source code for more information.
The calculations in the above mentioned paper were conducted with a more efficient
c++ implementation of the SCP algorithm. Note also that the dendrogram
building described in the paper is not implemented in this script.
The Python implementation of the SCP algorithm: kclique.py
An example network: kclique_testnet.edg
Usage: python kclique.py netname k [start end numberofevaluations] [weight]
If only netname and k are specified, the k-communities are returned. If, in addition, parameters start, end, and numberofevaluations are specified, the community structure will be evaluated at several points. Parameters start and end refer to the indexes of the first and last links to be used for evaluating the community structure when links are added to the network in order of decreasing weight. Link sorting is done automatically by kclique.py. The community evaluations are made linearly at numberofevaluations points between start and end. If parameter weight is not defined, the evaluations are made with respect to edge weights, and if intensity is specified as the weight, weighted k-clique percolation is used. In the case of weighted k-clique percolation parameters start and end refer to the indexes of sorted k-cliques.
Example: python kclique.py kclique_testnet.edg 3
This example returns the 3-clique communities in the network.
Example: python kclique.py kclique_testnet.edg 4 1000 3000 5
This example returns the 3-clique communities in the network when 1000, 1500, 2000, 2500, and 3000 of the strongest links have been added to the network.
Example: python kclique.py kclique_testnet.edg 3 100 900 5 intensity
This example returns nodes in 3-clique communities when 100, 300, 500, 700, and 900 first 5-cliques have been added to the network after sorting them with respect to intensity. Note that clique sorting is rather slow in this implementation.
Output is given as a list of nodes separated by space and communities separated by line change.
For better performance, try C++ implementation: http://www.lce.hut.fi/research/mm/complex/software/