R: Найти клики специальных размеров эффективно использовать igraph

Question

У меня есть большой граф (100000 узлов) и я хочу, чтобы найти его клики размера 5. Я использую эту команду для этой цели:

cliques(graph, min=5, max=5) 

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

adjacent.triangles (graph) # takes about 30s 
cliques(graph, min=3, max=3) # takes more than an hour 

Ищу команду как adjacent.triangles найти кликой с размером 5 эффективно.

Благодаря

Answer 1

Существует огромная разница между adjacent.triangles() и cliques(). adjacent.triangles() необходимо только треугольники, а cliques() необходимо магазин все они. Это может легко объяснить разницу во времени, если есть много треугольников. (Еще один фактор заключается в том, что алгоритм в cliques() был общим и не ограничен треугольниками - это может быть так, что adjacent.triangles() содержит некоторые оптимизации, поскольку мы знаем, что нас интересуют только треугольники).

Для чего это стоит cliques()не найти все максимальные клики; он начинается с 2-кликов (т. е. ребер), а затем объединяет их в 3-клики, 4-клики и т. д., пока не достигнет указанного вами максимального размера. Но опять же, если у вас на вашем графике много 3-кликов, это может легко стать узким местом, поскольку в алгоритме есть одна точка, где все 3-клики должны быть сохранены (даже если вас это не интересует), поскольку нам нужно, чтобы они нашли 4-клики.

Вы, вероятно, лучше всего с maximal.cliques(), чтобы получить приблизительное представление о том, насколько велики максимальные клики на вашем графике. Идея здесь в том, что у вас максимальная клика размером k, то все ее подмножества размером 5 - это 5 кликов. Это означает, что достаточно найти максимальные клики, сохранить те, которые имеют размер не менее 5, а затем перечислить все их подмножества размером 5. Но тогда у вас другая проблема, так как некоторые клики могут учитываться более одного раза.

Update: Я проверил исходный код для adjacent.triangles и в основном все это делает, что он перебирает все вершины, и для каждой вершины v он перечисляет все (U, W) пары его соседей и проверяет, подключены ли u и w. Если это так, то существует треугольник, смежный по вершине v. Это O (й) операции, если у вас есть п вершин и средняя степень d, но не обобщать группы вершин произвольного размера (так как вам нужно будет жёстко K - 1 вложенных для циклов в код для группы размером k).