Как я могу кластеризовать граф в Python?

Question

Пусть G граф. Итак, G - это набор узлов и набор ссылок. Мне нужно найти быстрый способ разбить график. График, над которым я сейчас работаю, имеет только 120 * 160 узлов, но вскоре я могу заняться аналогичной проблемой, в другом контексте (не медицина, а разработка веб-сайтов), с миллионами узлов.

Итак, я сохранил все ссылки в матрице графиков:

M=numpy.mat(numpy.zeros((len(data.keys()),len(data.keys()))))

Теперь M держит 1 в позиции s, t, если узел s связан с узлом t. Я уверен, что M симметричен M [s, t] = M [t, s], и каждый узел связан с самим собой M [s, s] = 1.

Если я хорошо помню, если я умножу M на M, результаты - это матрица, представляющая граф, который соединяет вершины, которые достигаются через два шага.

Так что я продолжаю умножать M на себя, пока количество нулей в матрице больше не уменьшится. Теперь у меня есть список подключенных компонентов. И теперь мне нужно кластеризовать эту матрицу.

До сих пор я довольно доволен алгоритмом. Я думаю, что это легко, элегантно и достаточно быстро. У меня проблемы с этой частью.

По сути, мне нужно разбить этот график на связанные компоненты.

Я могу пройти через все узлы и посмотреть, к чему они подключены.

Но как насчет сортировки матрицы, переупорядочивания линий? Но я не знаю, возможно ли это сделать.

Ниже приведен код:

def findzeros(M):
    nZeros=0
    for t in M.flat:
        if not t:
            nZeros+=1
    return nZeros

M=numpy.mat(numpy.zeros((len(data.keys()),len(data.keys()))))    
for s in data.keys():
    MatrixCells[s,s]=1
    for t in data.keys():
        if t<s:
            if (scipy.corrcoef(data[t],data[s])[0,1])>threashold:
                M[s,t]=1
                M[t,s]=1

nZeros=findzeros(M)
M2=M*M
nZeros2=findzeros(M2)

while (nZeros-nZeros2):
    nZeros=nZeros2
    M=M2
    M2=M*M
    nZeros2=findzeros(M2)

---

Edit:

Было предложено использовать разложение SVD. Вот простой пример задачи на графике 5х5. Мы будем использовать это, поскольку с квадратной матрицей 19200x19200 не так легко увидеть кластеры.

import numpy
import scipy

M=numpy.mat(numpy.zeros((5,5)))

M[1,3]=1
M[3,1]=1
M[1,1]=1
M[2,2]=1
M[3,3]=1
M[4,4]=1
M[0,0]=1

print M

u,s,vh = numpy.linalg.linalg.svd(M)
print u
print s
print vh

По существу, здесь есть 4 кластера: (0), (1,3), (2), (4) Но я до сих пор не понимаю, как svn может помочь в этом контексте.

Answer 1

Почему бы не использовать реальную библиотеку графов, такую ​​как Python-Graph ? Он имеет функцию для определения подключенных компонентов (хотя пример не приводится). Я полагаю, что выделенная библиотека будет работать быстрее, чем любой специальный графовый код, который вы приготовили.

РЕДАКТИРОВАТЬ: NetworkX кажется, что это может быть лучшим выбором, чем Python-Graph; его документация (здесь для функции подключенных компонентов) определенно есть.

Answer 2

В SciPy вы можете использовать разреженных матриц . Также отметим, что существуют более эффективные способы умножения матрицы на себя. В любом случае, то, что вы пытаетесь сделать, может быть выполнено декомпозицией SVD.

Введение с полезными ссылками .

Answer 3

Также есть graph_tool и networkit , которые имеют эффективные подпрограммы для подключенных компонентов и оба эффективно хранят сеть. Если вы собираетесь работать с миллионами узлов, networkx, вероятно, будет недостаточно (это чистый python afaik). Оба эти инструмента написаны на C ++, поэтому могут выполнять анализ больших графов с приемлемым временем выполнения.

Как указывает Фил, у вашего метода будет ужасно большое время вычислений для больших графиков (мы говорим дни, недели, месяцы ...), а для представления графа из миллиона узлов потребуется что-то вроде миллиона гигабайт памяти!

Answer 4

Поиск оптимального разбиения графа - сложная задача для NP, поэтому, каким бы ни был алгоритм, он будет приближенным или эвристическим. Не удивительно, что разные алгоритмы кластеризации дают (дико) разные результаты.

Реализация Python алгоритма модульности Ньюмана: Модульность

Также: MCL , MCODE , CFinder , NeMo , clusterONE

Answer 5

Как уже отмечали другие, нет необходимости изобретать велосипед. Много мыслей было уделено оптимальным методам кластеризации. Здесь - одна из известных программ кластеризации.

Answer 6

Вот некоторая наивная реализация, которая находит подключенные компоненты, используя поиск в глубину , я написал некоторое время назад. Хотя это очень просто, оно хорошо масштабируется до десяти тысяч вершин и ребер ...

import sys
from operator import gt, lt

class Graph(object):
    def __init__(self):
        self.nodes = set()
        self.edges = {}
        self.cluster_lookup = {}
        self.no_link = {}

    def add_edge(self, n1, n2, w):
        self.nodes.add(n1)
        self.nodes.add(n2)
        self.edges.setdefault(n1, {}).update({n2: w})
        self.edges.setdefault(n2, {}).update({n1: w})

    def connected_components(self, threshold=0.9, op=lt):
        nodes = set(self.nodes)
        components, visited = [], set()
        while len(nodes) > 0:
            connected, visited = self.dfs(nodes.pop(), visited, threshold, op)
            connected = set(connected)
            for node in connected:
                if node in nodes:
                    nodes.remove(node)

            subgraph = Graph()
            subgraph.nodes = connected
            subgraph.no_link = self.no_link
            for s in subgraph.nodes:
                for k, v in self.edges.get(s, {}).iteritems():
                    if k in subgraph.nodes:
                        subgraph.edges.setdefault(s, {}).update({k: v})
                if s in self.cluster_lookup:
                    subgraph.cluster_lookup[s] = self.cluster_lookup[s]

            components.append(subgraph)
        return components

    def dfs(self, v, visited, threshold, op=lt, first=None):
        aux = [v]
        visited.add(v)
        if first is None:
            first = v
        for i in (n for n, w in self.edges.get(v, {}).iteritems()
                  if op(w, threshold) and n not in visited):
            x, y = self.dfs(i, visited, threshold, op, first)
            aux.extend(x)
            visited = visited.union(y)
        return aux, visited

def main(args):
    graph = Graph()
    # first component
    graph.add_edge(0, 1, 1.0)
    graph.add_edge(1, 2, 1.0)
    graph.add_edge(2, 0, 1.0)

    # second component
    graph.add_edge(3, 4, 1.0)
    graph.add_edge(4, 5, 1.0)
    graph.add_edge(5, 3, 1.0)

    first, second = graph.connected_components(op=gt)
    print first.nodes
    print second.nodes

if __name__ == '__main__':
    main(sys.argv)

Answer 7

Алгоритм SVD здесь неприменим, но в противном случае Фил Н верен.

Answer 8

Похоже, есть библиотека PyMetis , которая разделит ваш график для вас, учитывая список ссылок. Достаточно легко извлечь список ссылок из вашего графика, передав ему исходный список связанных узлов (а не получаемый из матрицы).

Повторное выполнение M '= MM не будет эффективным для больших порядков M. Полное умножение матриц для матриц порядка N будет стоить N умножений и N-1 сложений на элемент, из которых N ² , то есть O (N ³ ) операций. Если вы масштабируете это до «миллионов узлов», это будет O (10 ¹⁸ ) операций на умножение матрицы на матрицу, из которых вы хотите сделать несколько.

Короче говоря, вы не хотите делать это таким образом. Предложение SVD от Vartec будет единственным подходящим выбором. Лучше всего использовать PyMetis, а не пытаться заново изобретать разбиение на графы.