cdlib.algorithms.ipca

ipca(g_original: object, weights: str = None, t_in: float = 0.5) → cdlib.classes.node_clustering.NodeClustering

IPCA was introduced by Li et al. (2008) as a modified version of DPClus. In contrast to DPClus, this method focuses on the maintaining the diameter of a cluster, defined as the maximum shortest distance between all pairs of vertices, rather than its density. In doing so, the seed growth aspect of IPCA emphasizes structural closeness of a predicted protein complex, as well as structural connectivity.

Like DPClus, IPCA computes local vertex and edge weights by counting the number of common neighbors shared between two vertices. However, IPCA calculates these values only once at the beginning of the algorithm, rather than updating them every time a discovered cluster is removed from the graph. This allows overlap to occur naturally between clusters, as cluster nodes are not permanently removed from the graph; however, it can also lead to a large amount of cluster overlap.

Supported Graph Types

Undirected Directed Weighted
Yes No Yes
Parameters:
  • g_original – a networkx/igraph object
  • weights – label used for the edge weights. Default, None.
  • t_in –
Returns:

NodeClustering object
Example: 
>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.ipca(G)
References:

Li, M., Chen, J., Wang, J., Hu, B., Chen, G. 2008. Modifying the DPClus algorithm for identifying protein complexes based on new topological structures. BMC Bioinformatics 9, 398.

Note

Reference Implementation: https://github.com/trueprice/python-graph-clustering