cdlib.algorithms.congo

cdlib.algorithms.congo(g_original: object, number_communities: int, height: int = 2) → NodeClustering

CONGO（CONGA优化）是对CONGA算法的优化。 CONGO算法与CONGA相同，但使用局部介数。完整的CONGO算法如下：

  1. 计算边的边介数和顶点的分割介数。

  2. 找到具有最大边介数的边或具有最大分裂介数的顶点，如果更大。

  3. Recalculate edge betweenness and split betweenness:

    1. 减去以移除边或分裂顶点为中心的h-区域的中介中心性。

    2. 移除边或分割顶点。

    3. 为同一区域添加中介中心性。

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

支持的图表类型

无向

有向

加权

是的

否

否
Parameters:

  • g_original – 一个 networkx/igraph 对象

  • number_communities – 所需的社区数量

  • height – CONGO 考虑的最长最短路径的长度，默认值为 2

Returns:

节点聚类对象

Example:

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

Gregory, Steve. 一种快速算法用于发现网络中的重叠社区。 欧洲机器学习与数据库知识发现联合会议。Springer, Berlin, Heidelberg, 2008.

注意

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