社区所有版块导航
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 年前 • 2415 次点击  

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