python - 如何在 python networkX 中添加具有字符串相似度分数的边并找到图形的中心

Question

我正在比较一组单词的字符串相似度。我想出了一个得分很高的对列表(相似对)。我首先需要合并那些有连通性的。例如 [(1,2),(2,4),(7,8)] 合并为 [(1,2,4),(7,8) >]。然后我想为每个组找到最好的代表。所以我正在考虑寻找处于每个组/集群中心的代表。

我可以用 networkX 做吗？如果每条边都有一个分数来衡量节点的相似性，如何找到图的中心？如何将分数添加到边缘？有示例代码吗？

Answer 1

这是我将如何解决这个问题，根据我的理解，这是您正在努力实现的目标。看来您首先要从边缘列表中找到连接的组件。为此，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}]

鉴于我们想要衡量节点/边在给定组件中的代表性，一种选择是查看节点的度数。地点:

The node degree is the number of edges adjacent to the node

所以我们可以做的是迭代连接的组件，并寻找具有最高中心性的节点。这是一种方法:

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}]