社区所有版块导航
Python
python开源   Django   Python   DjangoApp   pycharm  
DATA
docker   Elasticsearch  
aigc
aigc   chatgpt  
WEB开发
linux   MongoDB   Redis   DATABASE   NGINX   其他Web框架   web工具   zookeeper   tornado   NoSql   Bootstrap   js   peewee   Git   bottle   IE   MQ   Jquery  
机器学习
机器学习算法  
Python88.com
反馈   公告   社区推广  
产品
短视频  
印度
印度  
Py学习  »  Python

如何在python中高效计算无向图中的空间坐标系统计量

EmJ • 7 年前 • 2416 次点击  

我在计算 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)

它在小型网络中运行良好。但是,现在我有一个更大的网络,大约有4个节点。当我尝试用1000个节点的网络运行我现有的代码时,运行需要几天时间。有没有更有效的方法?

我现在的网络基本上是稀疏的。也就是说,节点之间的连接很少。在这种情况下,我可以离开未连接的节点,先进行计算,然后再将未连接的节点添加到输出中吗?

我也很高兴得到近似答案而不计算每一个组合。

三合会普查实例:

Triad Census正在将Triad(3个节点)划分为下图所示的四个类别。

Four classes of triad census

例如,考虑下面的网络。

enter image description here

四个阶级的三合会人口普查是;

{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 通过注释行 #print(len(list(combinations(G.nodes, 3)))) 如答案所示。但是,我的程序仍然很慢,即使有1000个节点的网络也需要几天才能运行。我正在寻找一种更有效的方法在python中实现这一点。

我不限于 networkx 也乐于接受使用其他库和语言的答案。

一如既往,我很乐意提供更多的细节需要。

Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/48156
文章 [ 4 ]  |  最新文章 7 年前
Jainil Patel
Reply   •   1 楼
Jainil Patel    7 年前
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)

我认为使用list比使用dictionary要快,因为dictionary呈指数级增长,需要更多的时间。

vurmux
Reply   •   2 楼
vurmux    7 年前
  1. 当您试图将所有组合转换为列表时,您的程序很可能会崩溃: print(len(list(combinations(G.nodes, 3)))) 是的。永远不要做因为 combinations 返回一个迭代器,该迭代器消耗少量内存,但list很容易占用千兆字节的内存。

  2. 如果有稀疏图,则在 connected components 以下内容: nx.connected_components(G)

  3. NetworkX有 triads 子模块,但看起来不适合你。我已经修改了networkx.algorithms.triads代码以返回triads,而不是它们的计数。你可以找到它 here 是的。注意它使用有向图。如果要将它与无向图一起使用,应该先将它们转换为有向图。

kutschkem
Reply   •   3 楼
kutschkem    7 年前

让我们核对一下号码。让 n个 是顶点的数目, E类 边的数目。

0个三元组在o中( n个 ^三)

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 triads) = e * (n -2) - #(2 triads) - #(3 triads)

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

说明:

1个三元组都是连通节点+1个非连通节点,因此我们通过计算连通节点+1个其他节点的个数得到这个数,并减去其他节点连通的情况(2和3个三元组)

0空间坐标轴只是节点的所有组合减去其他空间坐标轴。

如果你真的需要列出三元组,那你就太不走运了,因为不管你做什么,列出0个三元组都是在o(n^3)中的,一旦图变大,你就死定了。

上述2+3空间坐标的算法为o(e*max(neighbors)),其他部分为o(e+n),用于计算节点和边。比o(n^3)要好得多,o(n^3)需要明确列出0个三元组。列出1个triad仍然可以在o(e*n)中完成。

Lomtrur
Reply   •   4 楼
Lomtrur    7 年前

这个想法很简单:我使用邻接矩阵而不是直接处理图。我觉得这样会更有效率,而且似乎我是对的。

Adjacency matrix for example

在邻接矩阵中,a 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列中有A 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 字典(=行),最多 米 字典嵌套在里面。注意,嵌套字典是空的,因此检查它们中的密钥的存在等价于检查上述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)