社区所有版块导航
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
反馈   公告   社区推广  
产品
短视频  
印度
印度  
私信  •  关注

Lomtrur

Lomtrur 最近创建的主题
Lomtrur 最近回复了
7 年前
回复了 Lomtrur 创建的主题 » 如何在python中高效计算无向图中的空间坐标系统计量

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

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)