Построить дендрограмму сообществ, найденных алгоритмом NetworkX Girvan-Newman

Question

Алгоритм Гирвана-Ньюмана для обнаружения сообществ в сетях:

обнаруживает сообщества путем постепенного удаления ребер из исходного графика. Алгоритм удаляет «самый ценный» край, традиционно край с наивысшей межцентровостью, на каждом шаге. Когда график разбивается на части, тесно связанная структура сообщества становится доступной, и результат может быть изображен в виде дендрограммы.

В NetworkX реализация возвращает итератор для наборов наборов. Первый кортеж - это первый срез, состоящий из 2 сообществ, второй кортеж - это второй срез, состоящий из 3 сообществ, и т. Д. c., До последнего кортежа с n наборами для n отдельных узлов (листья дендрограммы).

import networkx as nx

G = nx.path_graph(10)
comp = nx.community.girvan_newman(G)
list(comp)

[({0, 1, 2, 3, 4}, {5, 6, 7, 8, 9}), ({0, 1}, {2, 3, 4} , {5, 6, 7, 8, 9}), ({0, 1}, {2, 3, 4}, {5, 6}, {8, 9, 7}), ({0, 1} , {2}, {3, 4}, {5, 6}, {8, 9, 7}), ({0, 1}, {2}, {3, 4}, {5, 6}, { 7}, {8, 9}), ({0}, {1}, {2}, {3, 4}, {5, 6}, {7}, {8, 9}), ({0} , {1}, {2}, {3}, {4}, {5, 6}, {7}, {8, 9}), ({0}, {1}, {2}, {3} , {4}, {5}, {6}, {7}, {8, 9}), ({0}, {1}, {2}, {3}, {4}, {5}, { 6}, {7}, {8}, {9})]

Вопрос: как построить эту дендрограмму?

Я смотрел на scipy.cluster.hierarchy.dendrogram но она ожидает "матрицу связей", которую я предполагаю, такую ​​как созданная scipy.cluster.hierarchy.linkage, но я не уверен, как бы я преобразовал этот список кортежей в эту "связь matrix ".

Поэтому я спрашиваю, как нарисовать эту дендрограмму, с / без помощи SciPy's dendrogram.

Answer 1

После @ItamarMushkin я последовал ответу @ mdml с небольшими изменениями и получил то, что хотел. На высоком уровне я превращаю вывод итератора Girvan-Newman в NetworkX в другой DiGraph(), который я, в конце концов, хочу рассматривать как дендограмму. Затем я строю Z, матрицу связи, которую я ввожу в scipy.cluster.hierarchy.dendrogram, в форме списка ребер, который включает фактическую высоту для каждого слияния дендограмм.

Две модификации, которые мне пришлось внести в ответ @ mdml:

1. Не так важно: я сортирую тьюпл-ключи узлов, входящих в index
2. Более важно: я добавляю функцию get_merge_height, которая дает каждому слиянию свою уникальную высоту согласно порядку вывода Гирвана-Ньюмана удаления ребер. В противном случае все слияния двух узлов будут иметь одинаковую высоту в дендрограмме, все слияния на следующем уровне слияния двух узлов, а другой будет одинаковой высоты, и т. Д. c.

I понимаю, что здесь могут быть некоторые избыточные итерации, я еще не думал об оптимизации.

import networkx as nx
from itertools import chain, combinations
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram

# get simulated Graph() and Girvan-Newman communities list
G = nx.path_graph(10)
communities = list(nx.community.girvan_newman(G))

# building initial dict of node_id to each possible subset:
node_id = 0
init_node2community_dict = {node_id: communities[0][0].union(communities[0][1])}
for comm in communities:
    for subset in list(comm):
        if subset not in init_node2community_dict.values():
            node_id += 1
            init_node2community_dict[node_id] = subset

# turning this dictionary to the desired format in @mdml's answer
node_id_to_children = {e: [] for e in init_node2community_dict.keys()}
for node_id1, node_id2 in combinations(init_node2community_dict.keys(), 2):
    for node_id_parent, group in init_node2community_dict.items():
        if len(init_node2community_dict[node_id1].intersection(init_node2community_dict[node_id2])) == 0 and group == init_node2community_dict[node_id1].union(init_node2community_dict[node_id2]):
            node_id_to_children[node_id_parent].append(node_id1)
            node_id_to_children[node_id_parent].append(node_id2)

# also recording node_labels dict for the correct label for dendrogram leaves
node_labels = dict()
for node_id, group in init_node2community_dict.items():
    if len(group) == 1:
        node_labels[node_id] = list(group)[0]
    else:
        node_labels[node_id] = ''

# also needing a subset to rank dict to later know within all k-length merges which came first
subset_rank_dict = dict()
rank = 0
for e in communities[::-1]:
    for p in list(e):
        if tuple(p) not in subset_rank_dict:
            subset_rank_dict[tuple(sorted(p))] = rank
            rank += 1
subset_rank_dict[tuple(sorted(chain.from_iterable(communities[-1])))] = rank

# my function to get a merge height so that it is unique (probably not that efficient)
def get_merge_height(sub):
    sub_tuple = tuple(sorted([node_labels[i] for i in sub]))
    n = len(sub_tuple)
    other_same_len_merges = {k: v for k, v in subset_rank_dict.items() if len(k) == n}
    min_rank, max_rank = min(other_same_len_merges.values()), max(other_same_len_merges.values())
    range = (max_rank-min_rank) if max_rank > min_rank else 1
    return float(len(sub)) + 0.8 * (subset_rank_dict[sub_tuple] - min_rank) / range

# finally using @mdml's magic, slightly modified:
G           = nx.DiGraph(node_id_to_children)
nodes       = G.nodes()
leaves      = set( n for n in nodes if G.out_degree(n) == 0 )
inner_nodes = [ n for n in nodes if G.out_degree(n) > 0 ]

# Compute the size of each subtree
subtree = dict( (n, [n]) for n in leaves )
for u in inner_nodes:
    children = set()
    node_list = list(node_id_to_children[u])
    while len(node_list) > 0:
        v = node_list.pop(0)
        children.add( v )
        node_list += node_id_to_children[v]
    subtree[u] = sorted(children & leaves)

inner_nodes.sort(key=lambda n: len(subtree[n])) # <-- order inner nodes ascending by subtree size, root is last

# Construct the linkage matrix
leaves = sorted(leaves)
index  = dict( (tuple([n]), i) for i, n in enumerate(leaves) )
Z = []
k = len(leaves)
for i, n in enumerate(inner_nodes):
    children = node_id_to_children[n]
    x = children[0]
    for y in children[1:]:
        z = tuple(sorted(subtree[x] + subtree[y]))
        i, j = index[tuple(sorted(subtree[x]))], index[tuple(sorted(subtree[y]))]
        Z.append([i, j, get_merge_height(subtree[n]), len(z)]) # <-- float is required by the dendrogram function
        index[z] = k
        subtree[z] = list(z)
        x = z
        k += 1

# dendrogram
plt.figure()
dendrogram(Z, labels=[node_labels[node_id] for node_id in leaves])
plt.savefig('dendrogram.png')