3

背景故事：

我一直在寻找一种高性能的方法来查找网络中低于给定维度的团（例如，所有 k<=3 的 k 团都是节点、边和三角形）。由于这个低维团（k<=3 或 k<=4）的例子经常是这种情况，我已经求助于简单地寻找高性能的三角形查找方法。

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

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

问题：

我有以下功能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。

4

1 回答 1

4

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

%%time

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
于 2021-07-04T03:14:20.640 回答