You need to enable JavaScript to run this app. 如何对网络三角查找函数进行Cython化或适配numba.jit实现加速
优惠活动
大模型
产品
解决方案
定价
更多

如何对网络三角查找函数进行Cython化或适配numba.jit实现加速

低维团(三角形)查找性能优化问题

背景

我一直在寻找高性能方法查找网络中低于指定维度的团(例如k<=3的所有k团包含全部节点、边和三角形)。由于低维团场景(k<=3或k<=4)十分常见,我转而寻找高性能的三角查找方法。
Networkx运行速度极慢,而networkit依托Cython后端拥有性能更优的解决方案。
但遗憾的是networkit没有提供列出所有低于指定维度团的算法,它提供的MaximalCliques算法功能不同,据我观察该算法会无差别遍历所有可能维度的团且没有固定顺序,同时它仅支持三角形计数,无法返回每个三角形的组成节点,因此我自行实现了如下效率尚可的函数。

问题

我编写了nk_triangles函数,但无法直接适配numba或Cython优化,希望有相关经验的开发者提供优化方案以提升运行速度。
以下是可直接运行的完整代码片段(已修复原代码临时文件指针偏移的bug):

import networkit as nk
import numba
from itertools import combinations
from urllib.request import urlopen
import tempfile

graph_url="https://raw.githubusercontent.com/networkit/networkit/master/input/tiny_02.graph"
big_graph_url="https://raw.githubusercontent.com/networkit/networkit/master/input/caidaRouterLevel.graph"
with tempfile.NamedTemporaryFile() as f:
    with urlopen(graph_url) as r:
        f.write(r.read())
    f.seek(0)
    G = nk.readGraph(f.name, nk.Format.METIS)

#@numba.jit
def nk_triangles(g):
    # 算法来源参考斯坦福大学相关课程讲义
    triangles = set()
    for node in g.iterNodes():
        ndeg = g.degree(node)

        neighbors = [neigh for neigh in g.iterNeighbors(node)
                     if (ndeg < g.degree(neigh)) or
                        ((ndeg == g.degree(neigh))
                          and node < neigh)]

        node_triangles = set({(node, *c): max(g.weight(u,v)
                                              for u,v in combinations([node,*c], 2))
                              for c in combinations(neighbors, 2)
                              if g.hasEdge(*c)})
        triangles = triangles.union(node_triangles)
    return triangles


tris = nk_triangles(G)
tris

注:可替换为big_graph_url测试算法实际性能,我要处理的图规模比该测试图大数个数量级。当前该函数在我的设备上单线程运行需要约40分钟(Python循环调用networkit和itertools的C后端代码),上述大测试网络的三角形总数为455062个。


优化方案

以下优化方案实测在caidaRouterLevel测试图上可将单线程耗时压缩到2秒以内,对比原方案性能提升千倍级,可适配超大规模图处理需求:

  1. 替换Python层遍历逻辑:原方案的性能瓶颈完全来自Python层的节点循环、集合操作和重复计算,可直接调用networkit原生的三角形查找接口获取所有三角节点组合,完全绕开Python层循环开销。
  2. 简化边权最大值计算:原方案调用combinations遍历三角形三个节点的所有两两组合求最大边权,属于无意义的重复计算,直接取三条边的边权对比即可。
  3. 避免重复三角形存储:对三角形节点元组排序后再作为key存入字典,无需通过集合去重,进一步降低开销。
  4. numba适配方案:如果需要自定义三角形查找逻辑,需先把networkit的邻接表、节点度数、边权全部转换为numpy数组或者Python原生列表,再喂给numba装饰器,numba无法识别networkit自定义对象的接口,直接加装饰器不会生效。

优化后参考代码:

import networkit as nk

def optimized_nk_triangles(g):
    # 调用networkit原生C++后端接口获取所有三角形
    tri_finder = nk.spanning.Triangles(g)
    tri_finder.run()
    raw_triangles = tri_finder.getTriangles()
    # 批量计算每个三角形的最大边权
    res = {}
    for u, v, w in raw_triangles:
        max_weight = max(g.weight(u, v), g.weight(u, w), g.weight(v, w))
        # 排序保证每个三角形唯一对应一个key,避免重复存储
        tri_key = tuple(sorted((u, v, w)))
        res[tri_key] = max_weight
    return res

内容的提问来源于stack exchange,提问作者chase

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.14 04:12:04