创建具有重叠顶点的子图
Creating subgraphs with overlapping vertices
我一直在寻找可以用来创建具有重叠顶点的子图的包。
根据我在 Networkx 和 metis 中的理解，可以将图形划分为两个或多个部分。但是我找不到如何分割成具有重叠节点的子图。
关于支持重叠顶点分区的库的建议将非常有用。
编辑：我尝试了 CDLIB 中的 angel 算法，将原始图划分为具有 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 个节点的重叠大小。但是，从 documentation available for angel
:param threshold: merging threshold in [0,1].
我不确定如何将 4 个重叠转换为必须在边界 [0, 1] 之间设置的值。建议将非常有帮助。
你可以看看CDLIB:
他们有大量适用于networkX的社区发现算法，包括一些overlapping communities algorithms。
- 旁注:
return 类型的函数称为 Node Clustering 起初可能有点混乱所以这里是 the methods applicable to it, usually you simply want to convert to a Python dictionary.
具体关于angel algorithm in CDLIB：
根据ANGEL: efficient, and effective, node-centric community discovery in static and dynamic networks，阈值是不是重叠阈值，但使用如下：
If the ratio is greater than (or equal to) a given threshold, the merge is applied and the node label updated.
基本上这个值决定了节点是否进一步合并成更大的社区，并不等同于重叠节点的数量。
此外，不要将“标签”与“节点的标签”混淆（如 nx.relabel_nodes(G, labels)). The "labels" referred are actually correlated with the Label Propagation Algorithm which is used by ANGEL。
至于改变此阈值的影响：
[...] Increasing the threshold, we obtain a higher number of communities since lower quality merges cannot take place.
[根据@J 的评论。 M.阿诺德]
从 ANGEL's github repository 可以看出，当 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
我一直在寻找可以用来创建具有重叠顶点的子图的包。
根据我在 Networkx 和 metis 中的理解，可以将图形划分为两个或多个部分。但是我找不到如何分割成具有重叠节点的子图。
关于支持重叠顶点分区的库的建议将非常有用。
编辑：我尝试了 CDLIB 中的 angel 算法，将原始图划分为具有 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 个节点的重叠大小。但是，从 documentation available for angel
:param threshold: merging threshold in [0,1].
我不确定如何将 4 个重叠转换为必须在边界 [0, 1] 之间设置的值。建议将非常有帮助。
你可以看看CDLIB:
他们有大量适用于networkX的社区发现算法，包括一些overlapping communities algorithms。
- 旁注:
return 类型的函数称为Node Clustering起初可能有点混乱所以这里是 the methods applicable to it, usually you simply want to convert to a Python dictionary.
具体关于angel algorithm in CDLIB：
根据ANGEL: efficient, and effective, node-centric community discovery in static and dynamic networks，阈值是不是重叠阈值，但使用如下：
If the ratio is greater than (or equal to) a given threshold, the merge is applied and the node label updated.
基本上这个值决定了节点是否进一步合并成更大的社区，并不等同于重叠节点的数量。
此外，不要将“标签”与“节点的标签”混淆（如
nx.relabel_nodes(G, labels)). The "labels" referred are actually correlated with the Label Propagation Algorithm which is used by ANGEL。
至于改变此阈值的影响：
[...] Increasing the threshold, we obtain a higher number of communities since lower quality merges cannot take place.
[根据@J 的评论。 M.阿诺德]
从 ANGEL's github repository 可以看出，当 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