Каков наилучший способ подсчета кликов размера k в неориентированном графе с использованием networkx в python?

Question

Я удивлен, что у networkx, похоже, нет встроенной функции для этого, но, возможно, я упускаю какой-то умный способ сделать это, используя встроенные алгоритмы?

Answer 1

Вы можете использовать одну из этих встроенных функций: enumerate_all_cliques или find_cliques , чтобы получить все k-клики в неориентированном графе.

Разница между этими функциями заключается в том, что enumerate_all_cliques превышает все возможные клики, а find_cliques охватывает только максимальный клик. В конце мы увидим, как это влияет на время выполнения.

Вариант 1 с использованием enumerate_all_cliques:

import networkx as nx

def enumerate_all_cliques_size_k(G, k):
    i = 0
    for clique in nx.enumerate_all_cliques(G):
        if len(clique) == k:
            i += 1
        elif len(clique) > k:
            return i
    return i

Вариант 2 с использованием find_cliques:

import networkx as nx
import itertools

def find_cliques_size_k(G, k):
    i = 0
    for clique in nx.find_cliques(G):
        if len(clique) == k:
            i += 1
        elif len(clique) > k:
            i += len(list(itertools.combinations(clique, k)))
    return i

Первый вариант более прямой, но его время выполнения проблематично, так как мы перебираем все возможные подмножества максимальных кликов, даже если максимальный размер клики меньше k. Мы видим, что enumerate_all_cliques_size_k занимает в 10 раз больше времени на полном графике размером 20:

G = nx.complete_graph(20)


@timing
def test_enumerate_all_cliques_size_k(G,k):
    print(enumerate_all_cliques_size_k(G, k))

@timing
def test_find_cliques_size_k(G, k):
    print(find_cliques_size_k(G, k))

test_enumerate_all_cliques_size_k(G,5)
test_find_cliques_size_k(G,5)

# --------------------Result-----------------------

15504
test_enumerate_all_cliques_size_k function took 616.645 ms
15504
test_find_cliques_size_k function took 56.967 ms

Answer 2

Добро пожаловать в SO.

Исходя из этой ссылки , я думаю, что в настоящее время не существует какой-либо функции для этого. Если вы хотите использовать nx функции, вы можете сделать что-то вроде этого:

def count_k_cliques(G, k):
    k_cliques_count = 0
    for clique in nx.enumerate_all_cliques(G): 
        if len(clique) > k: 
            break 
        elif len(clique) == k: 
            k_cliques_count += 1
    return k_cliques_count

Редактировать: Я рекомендую рассмотреть вариант 2 в Ответ Михала