我正在为我的triad census计算undirected network

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个节点的网络运行我现有的代码时,需要几天时间才能运行。有没有更有效的方法?
我目前的网络基本上是稀疏的。也就是说,节点之间的连接很少。在这种情况下,我可以离开未连接的节点,然后先进行计算,然后再将未连接的节点添加到输出中吗?
我也很高兴在不计算每一个组合的情况下得到近似答案。
三合会人口普查实例:
Triad人口普查将Triad(3个节点)划分为下图所示的四个类别。
python - 如何在python中有效地计算无向图中的三元组人口普查-LMLPHP
例如,考虑下面的网络。
python - 如何在python中有效地计算无向图中的三元组人口普查-LMLPHP
这四类人口普查包括:
{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')]}

如果需要,我很乐意提供更多细节。
编辑:
我可以通过评论回答中建议的行来解决memory error。但是,我的程序仍然很慢,即使有1000个节点的网络,也需要几天时间才能运行。我正在寻找一种在Python中实现这一点的更有效的方法。
我不仅限于#print(len(list(combinations(G.nodes, 3))))而且乐于接受使用其他库和语言的答案。
像往常一样,我很乐意根据需要提供更多细节。

最佳答案

这个想法很简单:我不用直接处理图,而是使用邻接矩阵。我认为这会更有效率,而且我似乎是对的。
python - 如何在python中有效地计算无向图中的三元组人口普查-LMLPHP
在邻接矩阵中,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 which will return a dictionary of dictionaries format that can be addressed as a sparse matrix.”
字典结构中有最多嵌套的字典。请注意,嵌套字典是空的,因此检查其中是否存在键等同于检查上面所述的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)

关于python - 如何在python中有效地计算无向图中的三元组人口普查,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/56537560/

10-11 22:57
查看更多