python 如何有效地计算无向图中的三元组人口普查
How to efficiently calculate triad census in undirected graph in python
我正在为我的 undirected network 计算 triad census。
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')]}
如果需要，我很乐意提供更多详细信息。
编辑：
我能够按照答案中的建议通过评论行 #print(len(list(combinations(G.nodes, 3)))) 来解决 memory error。但是，我的程序仍然很慢，即使有 1000 个节点的网络也需要几天的时间 运行。我正在 python.
中寻找更有效的方法
我不限于 networkx 并且很乐意接受使用其他库和语言的答案。
一如既往，我很乐意根据需要提供更多详细信息。
当您尝试将所有组合转换为列表时，您的程序很可能会崩溃：print(len(list(combinations(G.nodes, 3))))。永远不要这样做，因为 combinations returns 一个迭代器消耗的内存很少，但是列表很容易吃掉千兆字节的内存。
如果你有稀疏图，在connected components中找到三元组更合理：nx.connected_components(G)
Networkx 有 triads submodule but looks like it will not fit you. I already modified the networkx.algorithms.triads code to return triads, not their count. You can find it here。请注意，它使用有向图。如果你想把它用于无向图，你应该先把它们转换成有向图。
让我们检查一下数字。令 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(# neighbors)) 中，其他部分在 O(e + n) 中用于计算节点和边缘。比 O (n^3) 好得多，您需要明确列出 0 个三元组。列出 1 个三元组仍然可以在 O(e * n) 中完成。
想法很简单：我没有直接处理图形，而是使用邻接矩阵。我以为这样会更有效率，看来我是对的。
在邻接矩阵中，1表示两个节点之间有一条边，例如第一行可以读作"There is a link between A and B as well as C"
从那里我查看了您的四种类型并发现了以下内容：
对于类型 3，N1 和 N2、N1 和 N3 以及 N2 和 N3 之间必须有一条边。在邻接矩阵中，我们可以通过遍历每一行（其中每一行代表一个节点及其连接，这是 N1）并找到它连接到的节点（即 N2）来找到它。然后，在 N2 的行中，我们检查所有连接的节点（这是 N3）并保留那些在 N1 的行中有正条目的节点。例如"A, B, C"，A与B有联系，B与C有联系，A与C也有联系
对于类型 2，它的工作方式几乎与类型 3 相同。除了现在我们要为 N1 行中的 N3 列找到一个 0。 "A, B, D" 就是一个例子。 A 与 B 有联系，B 在 D 列中有一个 1，但 A 没有。
对于类型 1，我们只查看 N2 的行并找到 N1 行和 N2 行都为 0 的所有列。
最后，对于类型 0，查看 N1 行中条目为 0 的所有列，然后检查这些行，并找到所有也有 0 的列。
此代码应该适合您。对于 1000 个节点，我花了大约 7 分钟（在配备 i7-8565U CPU 的机器上），这仍然相对较慢，但与目前 运行 您的解决方案所花费的多天时间相去甚远.我已经包含了您图片中的示例，因此您可以验证结果。您的代码生成的图形与您在下面显示的示例不同。代码中的示例图和邻接矩阵都引用了您包含的图片。
具有 1000 个节点的示例使用 networkx.generators.random_graphs.fast_gnp_random_graph。 1000 是节点数，0.1 是边创建的概率，种子只是为了一致性。我已经设置了边创建的概率，因为你提到你的图是稀疏的。
networkx.linalg.graphmatrix.adjacency_matrix: "If you want a pure Python adjacency matrix representation try networkx.convert.to_dict_of_dicts which will return a dictionary-of-dictionaries format that can be addressed as a sparse matrix."
字典结构有 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)
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)
我认为使用列表比字典插入速度更快，因为字典呈指数增长，需要更多时间。
我正在为我的 undirected network 计算 triad census。
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')]}
如果需要，我很乐意提供更多详细信息。
编辑：
我能够按照答案中的建议通过评论行 #print(len(list(combinations(G.nodes, 3)))) 来解决 memory error。但是，我的程序仍然很慢，即使有 1000 个节点的网络也需要几天的时间 运行。我正在 python.
我不限于 networkx 并且很乐意接受使用其他库和语言的答案。
一如既往，我很乐意根据需要提供更多详细信息。
当您尝试将所有组合转换为列表时，您的程序很可能会崩溃：
print(len(list(combinations(G.nodes, 3))))。永远不要这样做，因为combinationsreturns 一个迭代器消耗的内存很少，但是列表很容易吃掉千兆字节的内存。如果你有稀疏图，在connected components中找到三元组更合理：
nx.connected_components(G)Networkx 有 triads submodule but looks like it will not fit you. I already modified the networkx.algorithms.triads code to return triads, not their count. You can find it here。请注意，它使用有向图。如果你想把它用于无向图，你应该先把它们转换成有向图。
让我们检查一下数字。令 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(# neighbors)) 中，其他部分在 O(e + n) 中用于计算节点和边缘。比 O (n^3) 好得多，您需要明确列出 0 个三元组。列出 1 个三元组仍然可以在 O(e * n) 中完成。
想法很简单：我没有直接处理图形，而是使用邻接矩阵。我以为这样会更有效率，看来我是对的。
在邻接矩阵中，1表示两个节点之间有一条边，例如第一行可以读作"There is a link between A and B as well as C"
从那里我查看了您的四种类型并发现了以下内容：
对于类型 3，N1 和 N2、N1 和 N3 以及 N2 和 N3 之间必须有一条边。在邻接矩阵中，我们可以通过遍历每一行（其中每一行代表一个节点及其连接，这是 N1）并找到它连接到的节点（即 N2）来找到它。然后，在 N2 的行中，我们检查所有连接的节点（这是 N3）并保留那些在 N1 的行中有正条目的节点。例如"A, B, C"，A与B有联系，B与C有联系，A与C也有联系
对于类型 2，它的工作方式几乎与类型 3 相同。除了现在我们要为 N1 行中的 N3 列找到一个 0。 "A, B, D" 就是一个例子。 A 与 B 有联系，B 在 D 列中有一个 1，但 A 没有。
对于类型 1，我们只查看 N2 的行并找到 N1 行和 N2 行都为 0 的所有列。
最后，对于类型 0，查看 N1 行中条目为 0 的所有列，然后检查这些行，并找到所有也有 0 的列。
此代码应该适合您。对于 1000 个节点，我花了大约 7 分钟（在配备 i7-8565U CPU 的机器上），这仍然相对较慢，但与目前 运行 您的解决方案所花费的多天时间相去甚远.我已经包含了您图片中的示例，因此您可以验证结果。您的代码生成的图形与您在下面显示的示例不同。代码中的示例图和邻接矩阵都引用了您包含的图片。
具有 1000 个节点的示例使用 networkx.generators.random_graphs.fast_gnp_random_graph。 1000 是节点数，0.1 是边创建的概率，种子只是为了一致性。我已经设置了边创建的概率，因为你提到你的图是稀疏的。
networkx.linalg.graphmatrix.adjacency_matrix: "If you want a pure Python adjacency matrix representation try networkx.convert.to_dict_of_dicts which will return a dictionary-of-dictionaries format that can be addressed as a sparse matrix."
字典结构有 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)
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)
我认为使用列表比字典插入速度更快，因为字典呈指数增长，需要更多时间。