Блог

Предыстория:

Я искал высокоэффективный способ поиска кликов в сети, которые находятся ниже заданного измерения (например, все k-клики с k В качестве примера низкоразмерных клик (k<=3 или k

Networkx невероятно медленный; однако networkit имеет гораздо более эффективное решение с бэкэндом Cython.

К сожалению, в networkit нет алгоритма для перечисления всех кликов У них есть алгоритм 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, вызывающие внутренний код C в networkit и itertools). Количество треугольников в большой сети составляет 455 062.

Вот простая версия вашего кода, которая занимает ~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) amp; (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