Как эффективно рассчитать перепись триады в неориентированном графе в питоне

Question

Я вычисляю triad census следующим образом для моего undirected network.

import networkx as nx
G = nx.Graph()
G.add_edges_from(
    [('A', 'B'), ('A', 'C'), ('D', 'B'), ('E', 'C'), ('E', 'F'),
     ('B', 'H'), ('B', 'G'), ('B', 'F'), ('C', 'G')])

from itertools import combinations
#print(len(list(combinations(G.nodes, 3))))

triad_class = {}
for nodes in combinations(G.nodes, 3):
    n_edges = G.subgraph(nodes).number_of_edges()
    triad_class.setdefault(n_edges, []).append(nodes)
print(triad_class)

Отлично работает с небольшими сетями. Тем не менее, теперь у меня есть большая сеть с примерно 4000-8000 узлов. Когда я пытаюсь запустить свой существующий код с сетью из 1000 узлов, это занимает несколько дней. Есть ли более эффективный способ сделать это?

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

Я также рад получить приблизительные ответы без расчета каждой комбинации.

Пример переписи триады:

Перепись триад делит триады (3 узла) на четыре категории, показанные на рисунке ниже.

Например, рассмотрим сеть ниже.

Перепись триады четырех классов:

{3: [('A', 'B', 'C')], 
2: [('A', 'B', 'D'), ('B', 'C', 'D'), ('B', 'D', 'E')], 
1: [('A', 'B', 'E'), ('A', 'B', 'F'), ('A', 'B', 'G'), ('A', 'C', 'D'), ('A', 'C', 'E'), ('A', 'C', 'F'), ('A', 'C', 'G'), ('A', 'D', 'E'), ('A', 'F', 'G'), ('B', 'C', 'E'), ('B', 'C', 'F'), ('B', 'C', 'G'), ('B', 'D', 'F'), ('B', 'D', 'G'), ('B', 'F', 'G'), ('C', 'D', 'E'), ('C', 'F', 'G'), ('D', 'E', 'F'), ('D', 'E', 'G'), ('D', 'F', 'G'), ('E', 'F', 'G')], 
0: [('A', 'D', 'F'), ('A', 'D', 'G'), ('A', 'E', 'F'), ('A', 'E', 'G'), ('B', 'E', 'F'), ('B', 'E', 'G'), ('C', 'D', 'F'), ('C', 'D', 'G'), ('C', 'E', 'F'), ('C', 'E', 'G')]}

Я с удовольствием предоставлю более подробную информацию, если это необходимо.

EDIT:

Мне удалось разрешить memory error, прокомментировав строку #print(len(list(combinations(G.nodes, 3)))), как предложено в ответе. Тем не менее, моя программа по-прежнему работает медленно и занимает несколько дней, даже если сеть состоит из 1000 узлов. Я ищу более эффективный способ сделать это в Python.

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

Как всегда, я с радостью предоставлю более подробную информацию по мере необходимости.

Answer 1

Давайте проверим числа.Пусть n будет числом вершин, e числом ребер.

0 триады в O ( n ^ 3)

1 триада в O ( e * n )

2 + 3 триада в O ( e )

Чтобы получить 2 + 3 триады:

For every node a:
   For every neighbor of a b:
      For every neighbor of b c:
        if a and c are connected, [a b c] is a 3 triad
        else [a b c] is a 2 triad
   remove a from list of nodes (to avoid duplicate triads)

Следующий шаг зависит от цели.Если вам просто нужно количество триад 1 и 0, то этого достаточно:

Объяснение:

1 триада - это все подключенные узлы + 1 неподключенный узел, поэтому мы получаем число, вычисляя количество подключенных узлов + 1 другой узел, и вычитаем случаи, когда подключен другой узел (2 и 3 триады)

0 триады - это просто все комбинации узлов за вычетом других триад.

Если вам действительно нужно перечислить триады, вам не повезло, потому что независимо от того, что вы делаете, список 0 триад находится в O(n ^ 3) и убьет вас, как только графики станут больше.

Вышеприведенный алгоритм для 2 + 3 триад находится в O (e * max (# соседей)), остальные части в O (e+ n) для подсчета узлов и ребер.Намного лучше, чем O (n ^ 3), который вам понадобится, чтобы явно перечислить 0 триад.Перечисление 1 триады все еще может быть сделано в O (e * n).

Answer 2

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

В матрице смежности 1 указывает на то, что между двумя есть граньузлы, например, первая строка может читаться как «Существует связь между A и B, а также C»

Оттуда я рассмотрел ваши четыре типа и обнаружил следующее:

• для типа 3 должно быть ребро между N1 и N2, N1 и N3 и между N2 и N3.В матрице смежности мы можем найти это, пройдя по каждой строке (где каждая строка представляет узел и его соединения, это N1) и найдя узлы, к которым он подключен (это будет N2).Затем в строке N2 мы проверяем все подключенные узлы (это N3) и сохраняем те, в которых есть положительная запись в строке N1.Примером этого является «A, B, C», A имеет соединение с B. B имеет соединение с C, а A также имеет соединение с C

• для типа 2он работает почти идентично типу 3. За исключением того, что сейчас мы хотим найти 0 для столбца N3 в строке N1.Примером этого является «A, B, D».A имеет связь с B, B имеет 1 в столбце D, но не имеет.

• для типа 1 мы просто смотрим на строку N2 и находим все столбцы, для которых и строка N1, и строка N2 имеют 0.

• наконец, для типа 0 посмотрите все столбцы в строке N1, для которых запись равна 0, а затем проверьте строки для них и найдите все столбцы, которые также имеют 0.

Этот код должен работать для вас.На 1000 узлов у меня ушло около 7 минут (на машине с процессором i7-8565U), что все еще относительно медленно, но в отличие от нескольких дней, которые вам требуются для запуска вашего решения.Я включил пример из ваших фотографий, чтобы вы могли проверить результаты.Ваш код создает график, который, кстати, отличается от приведенного ниже примера.Примерный граф в коде и матрица смежности ссылаются на изображение, которое вы включили.

В примере с 1000 узлами используется networkx.generators.random_graphs.fast_gnp_random_graph .1000 - это количество узлов, 0,1 - вероятность создания ребра, а начальное число - просто для согласованности.Я установил вероятность создания ребра, потому что вы упомянули, что ваш граф разрежен.

networkx.linalg.graphmatrix.adjacency_matrix : "Если вы хотите получить представление в виде матрицы в чистом Python, попробуйте networkx.convert.to_dict_of_dicts, который будет возвращать формат словаря словарей, который можно адресовать в виде разреженной матрицы. "

Структура словаря имеет M словарей (= строк), в которые вложено до M словарей,Обратите внимание, что вложенные словари пусты, поэтому проверка на наличие ключа в них эквивалентна проверке 1 или 0, как описано выше.

import time

import networkx as nx


def triads(m):
    out = {0: set(), 1: set(), 2: set(), 3: set()}
    nodes = list(m.keys())
    for i, (n1, row) in enumerate(m.items()):
        print(f"--> Row {i + 1} of {len(m.items())} <--")
        # get all the connected nodes = existing keys
        for n2 in row.keys():
            # iterate over row of connected node
            for n3 in m[n2]:
                # n1 exists in this row, all 3 nodes are connected to each other = type 3
                if n3 in row:
                    if len({n1, n2, n3}) == 3:
                        t = tuple(sorted((n1, n2, n3)))
                        out[3].add(t)
                # n2 is connected to n1 and n3 but not n1 to n3 = type 2
                else:
                    if len({n1, n2, n3}) == 3:
                        t = tuple(sorted((n1, n2, n3)))
                        out[2].add(t)
            # n1 and n2 are connected, get all nodes not connected to either = type 1
            for n3 in nodes:
                if n3 not in row and n3 not in m[n2]:
                    if len({n1, n2, n3}) == 3:
                        t = tuple(sorted((n1, n2, n3)))
                        out[1].add(t)
        for j, n2 in enumerate(nodes):
            if n2 not in row:
                # n2 not connected to n1
                for n3 in nodes[j+1:]:
                    if n3 not in row and n3 not in m[n2]:
                        # n3 is not connected to n1 or n2 = type 0
                        if len({n1, n2, n3}) == 3:
                            t = tuple(sorted((n1, n2, n3)))
                            out[0].add(t)
    return out


if __name__ == "__main__":
    g = nx.Graph()
    g.add_edges_from(
        [("E", "D"), ("G", "F"), ("D", "B"), ("B", "A"), ("B", "C"), ("A", "C")]
    )
    _m = nx.convert.to_dict_of_dicts(g)
    _out = triads(_m)
    print(_out)

    start = time.time()
    g = nx.generators.fast_gnp_random_graph(1000, 0.1, seed=42)
    _m = nx.convert.to_dict_of_dicts(g)
    _out = triads(_m)
    end = time.time() - start
    print(end)

Answer 3

import networkx as nx
from time import sleep
from itertools import combinations


G = nx.Graph()
arr=[]
for i in range(1000):
    arr.append(str(i))

for i,j in combinations(arr, 2):
    G.add_edges_from([(i,j)])

#print(len(list(combinations(G.nodes, 3))))
triad_class = [[],[],[],[]]

for nodes in combinations(G.subgraph(arr).nodes, 3):
            n_edges = G.subgraph(nodes).number_of_edges()
            triad_class[n_edges].append(nodes)


print(triad_class)

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

Answer 4

1. Скорее всего, вы программируете сбой при попытке преобразовать все комбинации в список: print(len(list(combinations(G.nodes, 3)))). Никогда не делайте этого, потому что combinations возвращает итератор, который потребляет немного памяти, но список может легко съесть гигабайты памяти.

2. Если у вас разреженный график, более разумно найти триады в связанных компонентах : nx.connected_components(G)

3. В Networkx есть триада подмодуль, но, похоже, он вам не подойдет. Я уже модифицировал код networkx.algorithms.triads, чтобы он возвращал триады, а не их количество. Вы можете найти его здесь . Обратите внимание, что он использует DiGraphs. Если вы хотите использовать его с неориентированными графами, вы должны сначала преобразовать их в направленные.