Агрегирование максимальных клик в реальных графах, Сабьясачи Басу

Описание: Аннотация: Перечисление максимальных клик — фундаментальная задача поиска графов, но её полезность часто ограничена вычислительной сложностью и высокой избыточностью результатов. Для решения этих проблем мы предлагаем $\rho$-плотные агрегаторы — новый подход, который лаконично описывает структуру максимальных клик. Вместо перечисления всех клик мы идентифицируем небольшую совокупность кластеров с плотностью ребер не менее $\rho$, которые в совокупности содержат каждую максимальную клику.

В отличие от перечисления максимальных клик, мы доказываем, что для всех $\rho 1$ каждый граф допускает $\rho$-плотный агрегатор субэкспоненциального размера, $n^{O (\log 1/\rho n)}$, и предлагаем алгоритм, достигающий этой границы. Для графов с ограниченной вырожденностью, типичной характеристикой реальных сетей, наш алгоритм работает почти за линейное время и производит агрегаторы почти линейного размера. Мы также устанавливаем соответствующую нижнюю границу размера агрегатора, доказывая, что наши результаты по существу являются точными. В эмпирической оценке на реальных сетях мы демонстрируем значительные практические преимущества использования агрегаторов: наш алгоритм стабильно быстрее, чем современный алгоритм перечисления клик, со средним ускорением более чем в 6 раз при ρ = 0,1 (и более чем в 300 раз в крайнем случае), при этом обеспечивая гораздо более лаконичное структурное резюме.

Ссылка на доклад: https://www.csa.iisc.ac.in/theorysemi...