1

我一直在寻找可以使用重叠顶点创建子图的包。根据我的理解， Networkx可以metis将图划分为两个或多个部分。但我找不到如何划分为具有重叠节点的子图。

关于支持重叠顶点分区的库的建议将非常有帮助。

编辑：我尝试了angelCDLIB 中的算法将原始图划分为具有 4 个重叠节点的子图。

import networkx as nx
from cdlib import algorithms
   
if __name__ == '__main__':
 
    g = nx.karate_club_graph()

    coms = algorithms.angel(g, threshold=4, min_community_size=10)
    print(coms.method_name)
    print(coms.method_parameters)  # Clustering parameters)
    print(coms.communities)
    print(coms.overlap)
    print(coms.node_coverage)

输出：

ANGEL
{'threshold': 4, 'min_community_size': 10}
[[14, 15, 18, 20, 22, 23, 27, 29, 30, 31, 32, 8], [1, 12, 13, 17, 19, 2, 21, 3, 7, 8], [14, 15, 18, 2, 20, 22, 30, 31, 33, 8]]
True
0.6470588235294118

从返回的社区中，我了解到 1 和 3 有 4 个节点的重叠，但 2 和 3 或 1 和 3 的重叠大小没有 4 个节点。我不清楚如何在此处指定重叠阈值（4 个重叠）algorithms. angel(g, threshold=4, min_community_size=10)。我尝试在这里设置 threshold=4 来定义 4 个节点的重叠大小。但是，从可用的文档中angel

:param 阈值：[0,1] 中的合并阈值。

我不确定如何将 4 个重叠转换为必须在边界 [0, 1] 之间设置的值。建议将非常有帮助。

4

1 回答 1

1

您可以查看CDLIB：

他们有大量适用于networkX的社区发现算法，包括一些重叠的社区算法。

具体关于angelCDLIB 中的算法：

根据ANGEL：efficient, and Effective, node-centric community discovery in static and dynamic networks，阈值不是重叠阈值，而是使用如下：

如果比率大于（或等于）给定阈值，则应用合并并更新节点标签。

  • 基本上，这个值决定了是否将节点进一步合并成更大的社区，并不等同于重叠节点的数量。

  • 此外，不要将“标签”与“节点的标签”混淆（如nx.relabel_nodes(G, labels)）。提到的“标签”实际上与ANGEL使用的标签传播算法相关。

至于改变这个阈值的影响：

[...] 增加阈值，我们获得更多社区，因为无法进行质量较低的合并。

[基于@JM Arnold 的评论]
从ANGEL 的 github 存储库中，您可以看到threshold >= 1仅使用该min_comsize值时：

self.threshold = threshold

if self.threshold < 1:
    self.min_community_size = max([3, min_comsize, int(1. / (1 - self.threshold))])
else:
    self.min_community_size = min_comsize
于 2020-12-30T23:53:41.470 回答