如何在Python中高效计算无向图的三元组统计信息

Question

我正在为我的无向网络计算三元组普查，方法如下。

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库，也可以接受使用其他库和语言的答案。

如常，如果需要，我很乐意提供更多细节。

- EmJ

---

你能给出“三元组统计”是什么的清晰定义吗？ - Joel

@Joel 谢谢您的评论。我已经更新了我的问题。如果您有任何建议，请告诉我。非常感谢 :) - EmJ

你能提供一个包含1000个节点的数组吗？ - Jainil Patel

@JainilPatel 谢谢您的评论。我的数据与此非常相似：g = nx.generators.fast_gnp_random_graph(1000, 0.1, seed=42)。 - EmJ

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 triads的数量，那么这就足够了：

#(1 triads) = e * (n -2) - #(2 triads) - #(3 triads)

#(0 triads) = {n \choose 3} - #(3 triads) - #(2 triads) - #(1 triads)

解释：

1 triads是所有连接节点+1个未连接节点，因此我们通过计算连接节点+1个其他节点的数量，并减去其他节点连接的情况（2和3三元组）来获取数量。

0 triads仅是节点的所有组合减去其他triads。

如果您需要实际列出triads，则基本上没有什么办法，因为无论您做什么，列出0 triads的时间复杂度都是O(n^3)，当图变得更大时会使程序崩溃。

上述用于2 + 3 triads的算法的时间复杂度为O(e * max(# neighbors))，其他部分的时间复杂度为O(e + n)，用于计算节点和边的数量。比显式地列出0 triads需要的O(n^3)好得多。列出1 triads仍然可以在O(e * n)内完成。

- kutschkem

---

非常感谢您的出色回答。我仍在阅读您的帖子，如果我有不理解的地方，我会留下评论。再次非常感谢 :) - EmJ

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几乎完全相同。但现在我们要在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：“如果您想要一个纯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)

- Lomtrur

---

哇，这太棒了。非常感谢您的出色回答。我仍在阅读您的帖子。如果我遇到任何问题，我会留下评论的。再次感谢 :) - EmJ

你好，我已经用我的实际数据集运行了你的代码，这大约花费了我1.5天的时间。但是，相对于我原来运行需要数天的程序，它依然很快 :）我在思考如果只考虑交易普查类别“3”和“2”，是否可以进一步缩短我的时间。如果您有任何建议，请告诉我，因为我想接受您的答案。期待您的回复，再次非常感谢 :) - EmJ

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)

我认为使用列表比字典插入更快，因为字典会呈指数增长，需要更多时间。"最初的回答"

- Jainil Patel

Answer 4

1. 当你尝试将所有组合转换为列表时，你的程序很可能会崩溃：print(len(list(combinations(G.nodes, 3))))。永远不要这样做，因为combinations返回一个消耗少量内存的迭代器，但是列表可以轻松地消耗掉几十亿字节的内存。

2. 如果您有稀疏图，更合理的做法是在连通组件中查找三元组：nx.connected_components(G)

3. Networkx有一个三元组子模块，但看起来它不适合您。我已经修改了networkx.algorithms.triads代码以返回三元组，而不是它们的数量。您可以在这里找到它。请注意，它使用的是DiGraphs。如果您想要将其与无向图一起使用，您应该先将其转换为有向图。

- vurmux