python - 如何在简单函数 : (Finding Triangles in network) 上使用 Cythonize/allow numba.jit

Question

背景故事:

我一直在寻找一种高性能的方法来查找网络中低于给定维度的派系(例如，所有 k<=3 的 k-派系都是节点、边和三角形)。由于这个低维团(k<=3 或 k<=4)的例子经常出现，我只好求助于寻找高性能的三角形查找方法。

Networkx 非常慢；然而，networkit 有一个性能更高的解决方案，带有 Cython 后端。

不幸的是，networkit 没有用于列出所有 <= 给定维度的派系的算法。他们有一个 MaximalCliques 算法，这是不同的，不幸的是，它只是以没有特定顺序(据我所知)运行 所有可能的 cliques 维度。它也只计算 个三角形，但不列出构成每个三角形的节点。因此，我现在正在编写自己的函数来实现一种相当有效的方法。

问题:

我有下面的函数 nk_triangles；但是，它很难轻易干扰到 numba 或 Cython。因此，我想看看是否有人在这些领域拥有更多专业知识，可以将其推向更快的速度。

我制作了一段简单但完全可行的代码片段，其中包含感兴趣的功能:

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.read()
    G = nk.readGraph(f.name, nk.Format.METIS)

#@numba.jit
def nk_triangles(g):
    # Source:
    # https://cs.stanford.edu/~rishig/courses/ref/l1.pdf
    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 后端代码)。大网络中三角形的数量为455,062。

Answer 1

这是您的代码的 numpy 版本，您的大图大约需要 1 分钟。

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(big_graph_url) as r:
        f.write(r.read())
    f.read()
    G = nk.readGraph(f.name, nk.Format.METIS)

nodes = np.array(tuple(G.iterNodes()))
adjacency_matrix = nk.algebraic.adjacencyMatrix(G, matrixType='sparse').astype('bool')
degrees = np.sum(adjacency_matrix, axis=0)
degrees = np.array(degrees).reshape(-1)



def get_triangles(node, neighbors):
    buffer = neighbors[np.argwhere(triangle_condition(*np.meshgrid(neighbors, neighbors)))]
    triangles = np.empty((buffer.shape[0], buffer.shape[1]+1), dtype='int')
    triangles[:,0] = node
    triangles[:,1:] = buffer
    return triangles

def triangle_condition(v,w):
    upper = np.tri(*v.shape,-1,dtype='bool').T
    upper[np.where(upper)] = adjacency_matrix[v[upper],w[upper]]
    return upper

def nk_triangles():
    triangles = list()
    for node in nodes:
        ndeg = degrees[node]
        neighbors = nodes[adjacency_matrix[node].toarray().reshape(-1)]
        neighbor_degs = degrees[neighbors]
        neighbors = neighbors[(ndeg < neighbor_degs) | ((ndeg == neighbor_degs) & (node < neighbors))]
        if len(neighbors) >= 2:
            triangles.append(get_triangles(node, neighbors))
    return triangles

tris = np.concatenate(nk_triangles())
print('triangles:', len(tris))

给我

triangles: 455062
CPU times: user 50.6 s, sys: 375 ms, total: 51 s
Wall time: 52 s