如何对网络三角查找函数进行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秒以内,对比原方案性能提升千倍级,可适配超大规模图处理需求:
- 替换Python层遍历逻辑:原方案的性能瓶颈完全来自Python层的节点循环、集合操作和重复计算,可直接调用networkit原生的三角形查找接口获取所有三角节点组合,完全绕开Python层循环开销。
- 简化边权最大值计算:原方案调用
combinations遍历三角形三个节点的所有两两组合求最大边权,属于无意义的重复计算,直接取三条边的边权对比即可。 - 避免重复三角形存储:对三角形节点元组排序后再作为key存入字典,无需通过集合去重,进一步降低开销。
- 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
相关产品推荐
相关产品推荐

