Блог

У меня есть большой график (миллионы узлов/ребер, никаких параллельных ребер или петель) в моей базе данных neo4j, где узлы представляют людей, а ребра представляют дружбу. Я хочу найти все максимальные клики (рассматривая ребра как неориентированные) по крайней мере k с узлами.

Максимальная клика-это клика, которую нельзя расширить, включив еще одну смежную вершину, то есть она не является подмножеством большей клики

Я заглянул в научную библиотеку графических данных neo4j, но смог найти только алгоритм для треугольных клик. Кроме apoc.algo.cliques того, в apoc v3.5, похоже, есть процедура, но она была отмечена как незавершенная работа. Я не нашел никакого алгоритма клики в последних версиях apoc.

Есть ли какой-нибудь запрос на шифр или плагин neo4j, который мог бы мне помочь? Есть ли другой способ подойти к этому?

Есть ли другой способ подойти к этому?

Я бы написал свой собственный код. Поскольку я предпочитаю C , я придумал это:

 void cPathFinder::cliques()
{
    // working copy on input graph
    auto work = myGraph;

    // store for maximal clique collection
    std::vector<std::vector<int>> vclique;

    while (1)
    {
        std::vector<int> clique;

        while (work.nodeCount())
        {
            if (!clique.size())
            {
                // start by moving an arbitrary node to the clique from the work graph
                auto nit = work.nodes().begin();
                clique.push_back(nit->first);
                work.removeNode(nit->first);
                continue;
            }
            bool found = false;

            // loop over nodes remaining in work graph
            for (auto amp;u : work.nodes())
            {
                // loop over nodes in clique
                for (int v : clique)
                {
                    if (work.includes_link(v, u.first) ||
                        work.includes_link(u.first, v))
                    {
                        // found node in work that is connected to clique nodes.
                        // move it to clique
                        clique.push_back(u.first);
                        work.removeNode(u.first);
                        found = true;
                        break;
                    }
                }
                if (found)
                    break;  // found a node to add to clique
            }
            if (!found)
                break;      // no more nodes can be added, the clique is maximal
        }

        if (!clique.size())
            break;          // did not find a clique

        // add to collection of maximal cliques
        vclique.push_back(clique);
    }

    // Display results
    for (auto amp;c : vclique)
    {
        std::cout << "clique: ";
        for (int n : c)
            std::cout << myGraph.name(n) << " ";
        std::cout << "n";
    }
}
 

Для этого ввода

 l 1 5
l 1 3
l 2 8
l 2 6
l 3 1
l 3 7
l 4 8
l 4 6
l 5 1
l 5 7
l 6 4
l 6 2
l 7 3
l 7 5
l 8 2
l 8 2
 

Я получаю этот вывод

clique: 5 1 3 7 clique: 8 2 6 4

Чтобы проверить это, вот что graphViz производит с теми же входными данными

Полный код вы можете найти здесь.