有向图的最大强连通分量
Largest strongly connected components of a directed graph
我正在处理一个 Networkx .MultiDiGraph() 对象，该对象由总共 82927 封定向电子邮件数据构建而成。在当前阶段，我正在尝试从 .MultiDiGraph() 对象及其对应的子图中获取最大的强连通分量。
可以访问文本数据here。
这是我的工作代码：
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...
正如我在上面的代码块中指出的那样，列表理解方法 returns 长度为 167 的 [1, 1, 1,..., 1] 的列表（这是节点的总数在我的数据中），而 max(nx.strongly_connected_components(G), key=len) 返回 {92}，我不确定这意味着什么。
看来我的代码有问题，我可能错过了处理数据的几个关键步骤。谁能看一看并启发我？
谢谢。
注意：修改后的代码（感谢 Eric 和 Joel）
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 个节点组成。
[更新]
经过进一步的试验和错误，我发现在将数据加载到 networkx 时需要使用 create_using = .MultiDiGraph()（而不是 .DiGraph()），否则，即使您为 MultiDiGraph 及其 weakly/strongly 相连的子图，你可能仍然会得到错误的边数！这将反映在您的 .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 个节点和 52xx 边的输出，但是如果您应用一个 -我上面列出的班轮，你会得到：
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 图 类.
相关联的计数机制不同，因此您将使用两种方法获得相同数量的节点，但边数不同
您的错误的根本原因是 nx.from_pandas_dataframe 默认创建一个无向图。所以email是一个无向图。当您随后创建有向图时，每条边仅出现在一个方向上。
要修复它，请使用 nx.from_pandas_dataframe 和参数 create_using = DiGraph
与您得到的输出相关的旧评论
你所有的强连接组件都有一个节点。
当您执行 max(nx.strongly_connected_components(G), key=len) 时，它会找到长度最长的节点集并 returns 它。在你的例子中，它们的长度都是 1，所以它 returns 其中之一（我相信无论哪个 networkx 碰巧首先放入 nx.strongly_connected_components(G) ）。但它返回 set，而不是 length。所以 {92} 是它返回的节点集。
碰巧 {92} 被决胜局选择为 nx.strongly_connected_components(G) 中的 "longest" 长度 1 分量。
示例：
max([{1}, {3}, {5}], key = len)
> {1}
[1, 1, 1,...,1] of length 167 (which is the exact number of nodes in the network)
这意味着你的图中基本上没有 strongly connected component（除了孤立的顶点）。
如果按长度对这些组件进行排序，您会得到一个单一顶点的随机组件，因为所有组件都具有相同的长度 (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}
我正在处理一个 Networkx .MultiDiGraph() 对象，该对象由总共 82927 封定向电子邮件数据构建而成。在当前阶段，我正在尝试从 .MultiDiGraph() 对象及其对应的子图中获取最大的强连通分量。
可以访问文本数据here。
这是我的工作代码：
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...
正如我在上面的代码块中指出的那样，列表理解方法 returns 长度为 167 的 [1, 1, 1,..., 1] 的列表（这是节点的总数在我的数据中），而 max(nx.strongly_connected_components(G), key=len) 返回 {92}，我不确定这意味着什么。
看来我的代码有问题，我可能错过了处理数据的几个关键步骤。谁能看一看并启发我？
谢谢。
注意：修改后的代码（感谢 Eric 和 Joel）
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 个节点组成。
[更新]
经过进一步的试验和错误，我发现在将数据加载到 networkx 时需要使用 create_using = .MultiDiGraph()（而不是 .DiGraph()），否则，即使您为 MultiDiGraph 及其 weakly/strongly 相连的子图，你可能仍然会得到错误的边数！这将反映在您的 .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 个节点和 52xx 边的输出，但是如果您应用一个 -我上面列出的班轮，你会得到：
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 图 类.
您的错误的根本原因是 nx.from_pandas_dataframe 默认创建一个无向图。所以email是一个无向图。当您随后创建有向图时，每条边仅出现在一个方向上。
要修复它，请使用 nx.from_pandas_dataframe 和参数 create_using = DiGraph
与您得到的输出相关的旧评论
你所有的强连接组件都有一个节点。
当您执行 max(nx.strongly_connected_components(G), key=len) 时，它会找到长度最长的节点集并 returns 它。在你的例子中，它们的长度都是 1，所以它 returns 其中之一（我相信无论哪个 networkx 碰巧首先放入 nx.strongly_connected_components(G) ）。但它返回 set，而不是 length。所以 {92} 是它返回的节点集。
碰巧 {92} 被决胜局选择为 nx.strongly_connected_components(G) 中的 "longest" 长度 1 分量。
示例：
max([{1}, {3}, {5}], key = len)
> {1}
[1, 1, 1,...,1] of length 167 (which is the exact number of nodes in the network)
这意味着你的图中基本上没有 strongly connected component（除了孤立的顶点）。
如果按长度对这些组件进行排序，您会得到一个单一顶点的随机组件，因为所有组件都具有相同的长度 (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}