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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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