代码之家 › 专栏 › 技术社区 › Chris T.

有向图的最大强连通分量

connected-components subgraph networkx python

3

Chris T. · 技术社区 · 7 年前

Networkx .MultiDiGraph() 对象由总共82927个定向电子邮件数据构建。在当前阶段,我试图从 .多向图() 对象及其对应的子图。可以访问文本数据 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...

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个节点组成。

[更新] 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 验证。

如果您使用输出 G 将给出一个具有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 图形类。

2 回复 | 直到 7 年前

1

4

Joel 7 年前

错误的根本原因是 nx.from_pandas_dataframe 默认情况下,创建无向图。所以 email 是一个无向图。然后创建有向图时,每条边仅在一个方向上显示。

nx。from_pandas_数据帧 create_using = DiGraph

所有强连接组件都有一个节点。

max(nx.strongly_connected_components(G), key=len) 它找到长度最长的节点集并返回。在您的例子中,它们的长度都是1,因此它返回其中一个(我相信是哪个networkx碰巧放入的) nx.strongly_connected_components(G) 首先)。但它正在返回设置 ,而不是长 . 所以 {92}

碰巧 nx。强连通分量(G) 通过决胜局。

例子:

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

2

1

Eric Duminil 7 年前

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

strongly connected component 在图中(即,除了孤立顶点)。

如果按长度对这些组件进行排序,则会得到一个单顶点的randon组件,因为所有组件的长度都相同( 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}