Мера сходства между графиками с использованием NetworkX - PullRequest
Новая
       79

Мера сходства между графиками с использованием NetworkX

3 голосов
/ 25 апреля 2020

У меня два графика A и B . Они могут быть изоморфными c, совершенно разными или иметь некоторые сходства (несколько узлов одинаковы или несколько узлов имеют одинаковые ребра).

Я хочу увидеть / проверить насколько различны / аналогичные эти графики . networkx.is_isomorphi c () - это способ. Тем не менее, это не говорит больше, чем просто правда или ложь.

Например, функция разности (A, B) возвращает новый граф, содержащий ребра, которые существуют в A, но не в B; но оно должно иметь одинаковое количество узлов.

Мои графики, A и B, не имеют одинаковое количество узлов. И могут иметь несколько сотен узлов. Таким образом, алгоритмы будут наилучшими, если не NP-Hard (Подобно функции graph_edit_distance (), которая является NP Hard).

1 Ответ

2 голосов
/ 25 апреля 2020

Не уверен, что это именно то, что вы ищете, но, надеюсь, вам может пригодиться что-то из этого. Давайте возьмем следующие графики G и H, например: 

l1 = [['A','C'], ['A', 'D'], ['I','F'], ['K', 'E'], ['D', 'A'], ['A', 'B'], ['C', 'D']]
l2 = [['A','B'], ['Q', 'D'], ['J','F'], ['A', 'E'], ['D', 'F'], ['X','A']]

G = nx.from_edgelist(l1)
H = nx.from_edgelist(l2)

G.nodes()
# NodeView(('A', 'C', 'D', 'I', 'F', 'K', 'E', 'B'))
H.nodes()
# NodeView(('A', 'B', 'Q', 'D', 'J', 'F', 'E', 'X'))

Чтобы получить сходство мера , вы, вероятно, могли бы придумать какое-то пользовательское определение сходства или Разница, учитывая пересечение объединения ребер. Возможно, расстояние Джакарта может быть хорошим кандидатом: 

def jaccard_similarity(g, h):
    i = set(g).intersection(h)
    return round(len(i) / (len(g) + len(h) - len(i)),3)

jaccard_similarity(G.edges(), H.edges())
# 0.091

Что, вероятно, также полезно здесь, - это придумать визуализацию, которая дает представление о том, насколько похожи и отличаются оба графика. Мы могли бы начать с использования compose, что даст нам простое объединение наборов узлов и наборов ребер: 

GH = nx.compose(G,H)
GH.nodes()
# NodeView(('A', 'C', 'D', 'I', 'F', 'K', 'E', 'B', 'Q', 'J', 'X'))

И итерации по ребрам и узлам составленного графа, и присвойте им цвет в зависимости от того, к какому графику они относятся (включая оба графика одновременно) Это также может быть расширено до добавления некоторого атрибута , указывающего, к какому графу он тоже относится: 

# set edge colors
edge_colors = dict()
for edge in GH.edges():
    if G.has_edge(*edge):
        if H.has_edge(*edge):
            edge_colors[edge] = 'magenta'
            continue
        edge_colors[edge] = 'lightgreen'
    elif H.has_edge(*edge):
        edge_colors[edge] = 'lightblue'

# set node colors
G_nodes = set(G.nodes())
H_nodes = set(H.nodes())
node_colors = []
for node in GH.nodes():
    if node in G_nodes:
        if node in H_nodes:
            node_colors.append('magenta')
            continue
        node_colors.append('lightgreen')
    if node in H_nodes:
        node_colors.append('lightblue')

Так что здесь пересекающиеся узлы и ребра будут иметь цвет magenta, В противном случае они будут зелеными или синими , если они принадлежат G или H Graph соответственно.

Теперь мы можем построить график, используя приведенный выше словарь / список цветов ребер и узлов соответственно. Это должно дать довольно хороший способ увидеть как пересекающиеся и непересекающиеся узлы / ребра на обоих графиках: 

pos = nx.spring_layout(GH, scale=20)
nx.draw(GH, pos, 
        nodelist=GH.nodes(),
        node_color=node_colors,
        edgelist=edge_colors.keys(), 
        edge_color=edge_colors.values(),
        node_size=800,
        width=8,alpha=0.5,
        with_labels=True)

enter image description here

...