Решение задачи поиска минимальных остовных деревьев ( mst minimum spanning tree) является распространенной задачей в различных областях исследований: распознавание различных объектов, компьютерное зрение, анализ и построение сетей

from collections import deque
import networkx as nx
s = nx.Graph()
s.add_nodes_from(names)
dq = deque(dist)
len_x = len(names)
for x in xrange(len_x - 1):
for y in xrange(x + 1, len_x):
s.add_edge(names[x], names[y], weight=dq.popleft())
В переменной s содержится исходный граф нашего набора данных. Следующим шагом построим минимальное покрывающее дерево полученного графа и отобразим гистограмму весов рёбер в нём (дабы выбрать пороговый уровень веса).

import matplotlib.pyplot as plt
mst = nx.minimum_spanning_tree(s)
plt.hist([edge[2]['weight'] for edge in mst.edges_iter(data=True)], 100, color='red', alpha=0.3)

Теперь создадим ещё один граф, включающий все вершины нашего исходного набора, но добавим в него только те рёбра, которые являлись частью остовного дерева и весили меньше порогового уровня в 0.05 (выбран чисто эмпирически по гистограмме).

r = nx.Graph()
r.add_nodes_from(names)
edges = [edge for edge in mst.edges_iter(data=True) if edge[2]['weight'] <= 0.05]
r.add_edges_from(edges)
Как вы могли заметить, в отличии от классического алгоритма MST, я предпочёл отрезать рёбра не по количеству кластеров, а по пороговому уровню, как в иерархическом алгоритме. Это позволило снизить влияние на результат кластеризации качество предварительной подготовки данных.

Что же, осталось лишь отобразить результат. Для этого в NetworkX также есть встроенные средства, а именно функция draw_graphviz. Интерес для нас представляет само остовное дерево и полученный граф кластеров.

def graph_draw(g):
"""Draw graph"""
plt.figure()
nx.draw_graphviz(g, with_labels=False, node_size=3, prog='neato') 
graph_draw(mst)
graph_draw(r)
plt.show()

Минимальное остовное дерево графа

Результат кластеризации