cdlib.algorithms.conga

cdlib.algorithms.conga(g_original: object, number_communities: int) → NodeClustering

CONGA（Cluster-Overlap Newman Girvan Algorithm）是一种用于发现重叠社区的算法。它通过特定的方法扩展了Girvan和Newman的算法，以决定何时以及如何分割顶点。算法如下：

  1. 计算网络中所有边的边介数。

  2. 从边的介数计算顶点的介数。

  3. 找到候选顶点集：那些顶点介数大于最大边介数的顶点。

  4. 如果候选集非空，计算候选顶点的对间性，然后计算候选顶点的分裂间性。

  5. 移除具有最大边介数的边或分割具有最大分割介数的顶点（如果更大）。

  6. 重新计算与移除的边或分裂的顶点在同一组件中的所有剩余边的边介数。

  7. 从步骤2重复，直到没有边剩余。

支持的图表类型

无向

有向

加权

是的

否

否
Parameters:

  • g_original – 一个 networkx/igraph 对象

  • number_communities – 所需的社区数量

Returns:

节点聚类对象

Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> com = algorithms.conga(G, number_communities=3)
References:

Gregory, Steve. 一种在网络中寻找重叠社区结构的算法。 欧洲数据挖掘与知识发现原理会议。Springer, Berlin, Heidelberg, 2007.

注意

参考实现: https://github.com/Lab41/Circulo/tree/master/circulo/algorithms