Как добавить ребро с оценками сходства строк и найти центр графа в сети PythonX - PullRequest
Новая
       22

Как добавить ребро с оценками сходства строк и найти центр графа в сети PythonX

0 голосов
/ 20 июня 2019

Я сравниваю сходства строк в группе слов. Я придумал список пар с хорошими результатами (аналогичные пары). Сначала мне нужно объединить тех, у кого есть связи. Например, [(1,2),(2,4),(7,8)] сливается с [(1,2,4),(7,8)]. Тогда я хочу найти лучшего представителя для каждой группы. Поэтому я думаю найти представителя, который находится в центре каждой группы / кластера.

Могу ли я сделать это с networkX? Если у каждого ребра есть оценка для измерения сходства узлов, как найти центр графика? Как добавить счет к краю? Есть примеры кодов?

1 Ответ

0 голосов
/ 21 июня 2019

Вот как я бы подошел к этой проблеме, насколько я понял, это то, что вы пытаетесь достичь.Кажется, вы сначала хотите найти подключенные компоненты из списка ребер.Для этого в 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}]
...