cdlib.algorithms.node_perception

node_perception(g_original: object, threshold: float, overlap_threshold: float, min_comm_size: int = 3) → cdlib.classes.node_clustering.NodeClustering

Node perception is based on the idea of joining together small sets of nodes. The algorithm first identifies sub-communities corresponding to each node’s perception of the network around it. To perform this step, it considers each node individually, and partition that node’s neighbors into communities using some existing community detection method. Next, it creates a new network in which every node corresponds to a sub-community, and two nodes are linked if their associated sub-communities overlap by at least some threshold amount. Finally, the algorithm identifies overlapping communities in this new network, and for every such community, merge together the associated sub-communities to identify communities in the original network.

Supported Graph Types

Undirected Directed Weighted
Yes No No
Parameters:
  • g_original – a networkx/igraph object
  • threshold – the tolerance required in order to merge communities
  • overlap_threshold – the overlap tolerance
  • min_comm_size – minimum community size default 3
Returns:

NodeClustering object

Example:
>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.node_perception(G, threshold=0.25, overlap_threshold=0.25)
References:

Sucheta Soundarajan and John E. Hopcroft. 2015. Use of Local Group Information to Identify Communities in Networks. ACM Trans. Knowl. Discov. Data 9, 3, Article 21 (April 2015), 27 pages. DOI=http://dx.doi.org/10.1145/2700404