我在比较一组单词的字符串相似性。我列出了一个得分很高的一对(相似的一对)。我首先需要合并那些有关联的。例如[(1,2),(2,4),(7,8)]合并到[(1,2,4),(7,8)]。然后我想为每个小组找到最好的代表。所以我想找一个在每个组/集群中处于中心位置的代表。
我能用networkx吗?如果每条边都有一个分数来衡量节点的相似性,如何找到图的中心如何把分数加到边上有示例代码吗?

最佳答案

以下是我将如何处理这个问题,从我的理解是,你正在努力实现似乎您首先要从边列表中找到连接的组件。networkX中有一个特定的函数。
让我们考虑以下示例:

l = [(1,2),(1,2),(1,4),(2,4),(2,5),(2,6),(7,8),(9,7),(1,2)]

让我们从上面的列表中构造一个网络为了概括起见,我考虑了重量其中权重是给定边出现的次数:
import networkx as nx
from collections import Counter
from operator import itemgetter

G = nx.Graph()
weighted_edges = [(*i,j) for i,j in Counter(l).items()]
# [(1, 2, 3), (1, 4, 1), (2, 4, 1), (2, 5, 1), (2, 6, 1), (7, 8, 1), (9, 7, 1)]
G.add_weighted_edges_from(weighted_edges)

现在我们可以使用nx.connected_components获取连接组件:
cc = nx.connected_components(G)
print(list(cc))
# [{1, 2, 4, 5, 6}, {7, 8, 9}]

考虑到我们想要获得一个测量给定组件中节点/边的代表性的方法,一个选择是查看节点的degree哪里:
节点度是与节点相邻的边数
所以我们可以做的是遍历连接的组件,并寻找具有最高中心性的节点。有一种方法:
degree_cen = G.degree()
out = []
while True:
    try:
        component = next(cc)
        component_cen = {k: degree_cen[k] for k in component}
        center_node = max(component_cen.items(), key=itemgetter(1))[0]
        out.append({'component':component, 'center_node':center_node})
    except StopIteration:
        break

结果是:
print(out)
# [{'component': {1, 2, 4, 5, 6}, 'center_node': 2},
#  {'component': {7, 8, 9}, 'center_node': 7}]

10-06 05:14
查看更多