Крупнейшие сильно связные компоненты ориентированного графа

Question

Я работаю над Networkx.MultiDiGraph() Объект построен из 82927 направленных данных электронной почты. На данном этапе я пытаюсь получить самые большие сильно связанные компоненты из .MultiDiGraph() объект и соответствующий ему подграф. Доступ к текстовым данным можно получить здесь. Вот мой рабочий код:

import networkx as nx
import pandas as pd
import matplotlib.pyplot as plt
email_df = pd.read_csv('email_network.txt', delimiter = '->')
edge_groups = email_df.groupby(["#Sender", "Recipient"], as_index=False).count().rename(columns={"time":"weight"})
email = nx.from_pandas_dataframe(edge_groups, '#Sender', 'Recipient', edge_attr = 'weight')
G = nx.MultiDiGraph()
G.add_edges_from(email.edges(data=True))

# G is a .MultiDiGraph object
# using .strongly_connected_components() to get the part of G that has the most nodes
# using list comprehension
number_of_nodes = [len(n) for n in sorted(nx.strongly_connected_components(G))]
number_of_nodes

# 'number_of_nodes' return a list of [1, 1, 1,...,1] of length 167 (which is the exact number of nodes in the network)

# using the recommended method in networkx documentation

largest = max(nx.strongly_connected_components(G), key=len)
largest

# 'largest' returns {92}, not sure what this means... 

Как я отмечал в приведенном выше блоке кода, метод понимания списка возвращает список [1, 1, 1,..., 1] длиной 167 (который является общим числом узлов в моих данных), тогда как max(nx.strongly_connected_components(G), key=len) возвращенный {92} Я не уверен, что это значит.

Похоже, что-то не так с моим кодом, и я мог пропустить несколько ключевых шагов при обработке данных. Может ли кто-нибудь захотеть взглянуть и просветить меня в этом?

Спасибо.

Примечание: пересмотренный код (слава Эрику и Джоэлу)

import networkx as nx
import pandas as pd
import matplotlib.pyplot as plt
email_df = pd.read_csv('email_network.txt', delimiter = ' ')
edge_groups = email_df.groupby(["#Sender", "Recipient"], as_index=False).count().rename(columns={"time":"weight"})
# per @Joel's comment, adding 'create_using = nx.DiGraph()'     
email = nx.from_pandas_dataframe(edge_groups, '#Sender', 'Recipient', edge_attr = 'weight', create_using = nx.DiGraph())
# adding this 'directed' edge list to .MultiDiGraph() object

G = nx.MultiDiGraph()
G.add_edges_from(email.edges(data=True))

Теперь мы рассмотрим самый большой сильно связанный компонент (с точки зрения количества узлов) в этой сети.

In [1]: largest = max(nx.strongly_connected_components(G), key=len)
In [2]: len(largest)
Out [2]: 126

Самый большой сильно связанный компонент состоит из 126 узлов.

[Обновления] После дальнейших проб и ошибок я обнаружил, что нужно использовать create_using = .MultiDiGraph() (вместо .DiGraph()) при загрузке данных на networkx в противном случае, даже если вы получите правильное количество узлов для вашего MultiDiGraph и его слабо / сильно связанные подграфы, вы все равно можете ошибиться в количестве ребер! Это отразится на тебе .strongly_connected_subgraphs() выходы.

Для моего случая здесь, я буду рекомендовать другим использовать эту однострочную

import networkx as nx
import pandas as pd
import matplotlib.pyplot as plt
G = nx.read_edgelist(path="email_network.txt", data=[('time', int)], create_using=nx.MultiDiGraph(), nodetype=str)

И мы можем реализовать .strongly_connected_components(G) а также strongly_connected_subgraphs проверять.

Если вы используете networkx выход G из первого блока кода, max(nx.strongly_connected_components(G), key=len) выдаст вывод с 126 узлами и 52хх-то ребрами, но если вы примените однострочник, который я перечислил выше, вы получите:

In [1]: largest = max(nx.strongly_connected_components(G), key=len)
In [2]: G_sc = max(nx.strongly_connected_subgraphs(G), key=len)

In [3]: nx.number_of_nodes(G_sc) 
Out [3]: 126
In [4]: nx.number_of_nodes(G_sc) 
Out [4]: 82130

Вы получите одинаковое количество узлов с обоими методами, но разное количество ребер из-за разных механизмов подсчета, связанных с разными networkx графовые классы.

Answer 1

Основная причина вашей ошибки заключается в том, что nx.from_pandas_dataframe по умолчанию создается неориентированный граф. Так email неориентированный граф. Когда вы создаете ориентированный граф, каждое ребро появляется только в одном направлении.

Чтобы исправить это используйте nx.from_pandas_dataframe с аргументом create_using = DiGraph

---

старые комментарии, относящиеся к полученному вами результату

Все ваши сильно связанные компоненты имеют один узел.

Когда вы делаете max(nx.strongly_connected_components(G), key=len) он находит множество узлов, которое имеет наибольшую длину, и возвращает его. В вашем случае все они имеют длину 1, поэтому он возвращает один из них (я полагаю, какой-либо случайный случай с сетью x nx.strongly_connected_components(G) первый). Но он возвращает набор, а не длину. Так {92} это набор узлов, которые он возвращает.

Бывает что {92} был выбран как самый длинный компонент длины 1 в nx.strongly_connected_components(G) на тай-брейке.

Пример:

max([{1}, {3}, {5}], key = len)
> {1}

Answer 2

[1, 1, 1,...,1] of length 167 (which is the exact number of nodes in the network)

Это означает, что в вашем графе практически нет сильно связанного компонента (кроме одиночных вершин, то есть).

Если вы отсортируете эти компоненты по длине, вы получите случайный компонент одной вершины, поскольку все компоненты имеют одинаковую длину (1). В вашем примере {92}, которая могла бы быть любой другой вершиной.

Импорт выглядит корректно, и на самом деле нет сильно связанного компонента, это означает, что никто никогда не отвечал на письма.

Чтобы проверить, не проблема ли pandas, MultiDiGraph или ваш импорт, я написал:

G = nx.DiGraph()

with open('email_network.txt') as f:
    for line in f:
        n1, n2, time = line.split()
        if n1.isdigit():
            G.add_edge(int(n1),int(n2))

Это не изменило результат.

Просто добавив ребро с G.add_edge(2,1) создает большой сильно связанный компонент, хотя:

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 126, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 115, 117, 118, 119, 120, 121, 122, 123, 124, 128, 129, 134, 149, 151}