Подход ветвей и границ для задач поиска максимальных плотных подграфов с малым диаметром

Основная информация

• ID статьи: 2511.03157
• Название: A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
• Авторы: Yi Zhou (Университет электронной науки и технологии Китая), Chunyu Luo (Университет электронной науки и технологии Китая), Zhengren Wang (Пекинский университет), Zhang-Hua Fu (Шэньчжэньский институт искусственного интеллекта и робототехники для общества, CUHK Shenzhen)
• Классификация: cs.DS (Структуры данных и алгоритмы)
• Дата публикации: 6 ноября 2025 г. (arXiv v2)
• Ссылка на статью: https://arxiv.org/abs/2511.03157v2

Аннотация

В данной работе исследуется задача поиска максимального подграфа с низким диаметром и свойством f(·)-плотности (MfDS). f(·)-плотный граф — это граф с n вершинами и не менее f(n) рёбер, где f(·) — некоторая определённая функция. Это понятие охватывает различные модели релаксации клик, включая γ-квазиклики, k-дефектные клики и плотные клики. Однако f(·)-плотные графы могут быть несвязными или слабо связными. Для решения этой проблемы в работе исследуется поиск максимального f(·)-плотного подграфа с диаметром не более 2. Предложен алгоритм ветвей и границ на основе декомпозиции графа для оптимального решения задачи. Ключевой особенностью алгоритма является разложение графа на n меньших подграфов, позволяющее проводить независимый поиск в каждом подграфе. В работе также введены стратегии декомпозиции, такие как упорядочение по вырожденности и упорядочение по двухшаговой вырожденности, а также алгоритм ветвей и границ с новыми верхними границами на основе упорядочения. Экспериментальные результаты на 139 реальных графах показывают, что предложенный алгоритм превосходит решатели MIP и чистые методы ветвей и границ, оптимально решая почти в два раза больше экземпляров в течение одного часа.

Исследовательский контекст и мотивация

1. Решаемая проблема

В анализе сетей выявление плотно связанных подграфов (cohesive subgraph) является центральной задачей с приложениями в обнаружении сообществ, идентификации белковых комплексов, анализе финансовых сетей и других областях. Классическая модель клики требует наличия рёбер между всеми парами вершин, что является слишком строгим требованием, особенно в практических приложениях с шумом и ошибками. Поэтому были предложены различные модели релаксации клик:

• γ-квазиклика: индуцированный подграф на n вершинах содержит не менее γ(n choose 2) рёбер
• s-дефектная клика: содержит не менее (n choose 2) - s рёбер
• средняя s-plex: содержит не менее n(n-s)/2 рёбер

Эти модели могут быть объединены в единую концепцию f(·)-плотного графа: граф с n вершинами содержит не менее f(n) рёбер.

2. Важность проблемы

Существующие модели f(·)-плотных графов имеют серьёзный недостаток: они могут быть несвязными или иметь слабую связность. Авторы демонстрируют это на примере двух графов (рис. 1):

• G1: клика из 200 вершин плюс путь из 10 вершин, где расстояние от v1 до v210 составляет 10 шагов
• G2: клика из 200 вершин плюс 10 изолированных вершин, между v1 и v210 нет пути

Оба графа удовлетворяют требованию плотности f(n)=0.9(n choose 2), но явно не являются плотно связанными сообществами.

3. Ограничения существующих методов

• Методы MIP: хотя существуют модели смешанного целочисленного программирования для конкретных функций f(·) (например, GF3), они неэффективны для больших графов и не включают ограничения на малый диаметр
• Методы ветвей и границ: существуют алгоритмы для конкретных задач (максимальная s-дефектная клика, максимальная γ-квазиклика), но отсутствует универсальная схема решения для f(·)-плотных графов
• Ограничения связности: Santos et al. (2024) предложили ограничения связности на основе остовного дерева, но ограничения на диаметр лучше гарантируют плотную связность

4. Исследовательская мотивация

В работе вводится концепция f(·)-плотного графа с низким диаметром: требуется, чтобы граф был связным, содержал не менее f(n) рёбер и имел диаметр не более 2. Ограничение диаметра 2 (называемое 2-club) гарантирует, что кратчайший путь между любыми двумя вершинами не превышает 2, обеспечивая сильную связность. Целью работы является разработка эффективных точных алгоритмов для решения этой NP-трудной задачи.

Основные вклады

1. Формализация проблемы:
   • Впервые систематически определены f(·)-плотные графы и их наследственные свойства
   • Формализована задача поиска максимального подграфа с низким диаметром и свойством f(·)-плотности (MfDS)
   • Предоставлена модель смешанного целочисленного линейного программирования MIP-fD
2. Алгоритмическая схема:
   • Предложена схема предварительной обработки на основе декомпозиции графа, разлагающая входной граф на n меньших подграфов
   • Введены две стратегии декомпозиции: упорядочение по вырожденности (degeneracy ordering) и упорядочение по двухшаговой вырожденности (two-hop degeneracy ordering)
   • Разработан алгоритм ветвей и границ с новыми верхними границами на основе упорядочения
   • Предоставлен анализ сложности в наихудшем случае для всех компонентов и общего алгоритма
3. Экспериментальная верификация:
   • Тестирование на 139 реальных графах с двумя типами функций f(·) (γ-квазиклики и s-дефектные клики)
   • Демонстрация того, что схема декомпозиции значительно улучшает производительность, решая в два раза больше экземпляров за час по сравнению с чистым методом ветвей и границ
   • Показано, что метод верхних границ на основе упорядочения значительно сокращает размер дерева поиска

Детальное описание методов

Определение задачи

Входные данные:

• Неориентированный простой граф G=(V,E)
• Функция плотности f: ℤ≥0 → ℝ, удовлетворяющая f(i) ≤ (i choose 2)
• Оракул для вычисления f(·) (константное время)

Выходные данные: максимальное множество вершин S⊆V такое, что:

1. |E(S)| ≥ f(|S|) (свойство f(·)-плотности)
2. diam(GS) ≤ 2 (ограничение на малый диаметр)

Цель: ωf(G) = max{|S| : S⊆V, |E(S)|≥f(|S|), diam(GS)≤2}

Сложность: NP-трудная, W1-трудная, трудно аппроксимируется за полиномиальное время (так как максимальная клика является частным случаем)

Основная схема алгоритма

1. Общая схема декомпозиции (Algorithm 1)

Ключевая лемма (Lemma 3): Для любого упорядочения вершин графа G π=⟨v1,...,vn⟩ определим для каждой вершины vi:

• Vi = {vi} ∪ {N^(2)_G(vi) ∩ {vi+1,...,vn}}
• Gi = GVi

Если S_i — максимальный подграф с низким диаметром и свойством f(·)-плотности в Gi, содержащий vi, то: **ωf(G) = max(|S_1|,...,|S*_n|)**

Поток алгоритма:

1. Получить начальное решение S с помощью эвристического алгоритма (нижняя граница)
2. Определить порядок вершин π с помощью алгоритма упорядочения
3. Для каждого vi в π:
   - Построить подграф Gi = G[Vi]
   - Решить ExactSearch(Gi, f(·), {vi}, N^(2)_G(vi), lb)
4. Вернуть максимальное решение из всех подзадач

Временная сложность: O(Theur(G) + Torder(G) + poly(αG)2^αG)

• αG = max(|V1|,...,|Vn|): максимальный размер подграфа
• Ключевым является минимизация αG для контроля экспоненциальной части

2. Эффективный эвристический алгоритм (Algorithm 2)

Основан на упорядочении по вырожденности (degeneracy ordering):

• Определение: k-вырожденное упорядочение — это упорядочение вершин ⟨v1,...,vn⟩, такое что каждая вершина vi имеет степень ≤ k в индуцированном подграфе {vi,...,vn}
• Вычисление: использование алгоритма peel, O(|V|+|E|) времени, повторное удаление вершин с минимальной степенью
• Вырожденность dG: минимальное значение k

Эвристический поток:

1. Вычислить упорядочение по вырожденности ⟨v1,...,vn⟩
2. Для каждого vi:
   - Si ← {vi} ∪ {NG(vi) ∩ {vi+1,...,vn}}
   - Gi ← G[Si] (диаметр ≤ 2)
   - While |Ei| < f(|Si|):
       Удалить вершину с минимальной степенью из Gi
   - Обновить оптимальное решение S*
3. Вернуть S*

Временная сложность: O(|E| + |V|d²G)

• В реальных графах dG << |V| (например, ca-dblp-2010: dG=74, |V|=226413)

3. Стратегии упорядочения вершин

Вариант 1: Упорядочение по вырожденности

• Преимущества: O(|V|+|E|) времени
• Граница: αG ≤ min(dG·ΔG, |V|)
• Доказательство: |Vi| = 1 + |NG(vi)∩{vi+1,...,vn}| + |N^(2)_G(vi)\NG(vi)∩{vi+1,...,vn}| ≤ 1 + dG + dG·ΔG

Вариант 2: Упорядочение по двухшаговой вырожденности (Algorithm 3)

• Определение: k-двухшаговое вырожденное упорядочение — упорядочение, такое что каждая вершина vi имеет не более k двухшаговых соседей в {vi,...,vn}
• Вычисление: аналогично peel, повторное удаление вершин с минимальным |N^(2)_G(v)|
• Временная сложность: O(|V||E|·min(tdG, ΔG))
• Граница: αG ≤ tdG
• Преимущества: tdG обычно намного меньше dG·ΔG (например, ca-dblp-2010: tdG=238 vs dG·ΔG=17612)

Алгоритм ветвей и границ (Algorithm 4)

Основная структура

BranchBound(G, S, C, lb):
  Входные данные: граф G, текущее решение S, множество кандидатов C, нижняя граница lb
  
  1. Если G[S] — допустимое решение и |S|>lb: обновить lb и оптимальное решение
  
  2. Если f(·) наследственна и |E(S)|<f(|S|): отсечение, возврат
  
  3. UB ← SortBound(G, f(·), S, C)  // вычисление верхней границы
  
  4. Если UB ≤ lb: отсечение, возврат
  
  5. Если f(·) наследственна: применить правила сокращения (Lemma 5)
  
  6. Случайно выбрать u∈C
  
  7. Если выполнены условия Lemma 4: рекурсивно обработать только ветвь S∪{u}
     Иначе: рекурсивно обработать обе ветви S∪{u} и S

Правила сокращения (Lemma 4 & 5)

Lemma 4 (Универсальное сокращение): Если u∈C удовлетворяет:

1. |NG(u)| = |V|-1, или
2. |NG(u)| = |V|-2 и GS∪{u} допустимо

То существует оптимальное решение, содержащее u → нужно искать только в ветви, содержащей u

Lemma 5 (Сокращение для наследственных функций): Если f(·) наследственна:

1. Если |E(S)| < f(|S|), то не существует допустимого решения, содержащего S
2. Если v∈C такая, что |E(S∪{v})| < f(|S|+1), то не существует допустимого решения, содержащего v

Алгоритм верхней границы на основе упорядочения (Algorithm 5)

Простая верхняя граница (Section 4.6.1)

Для v∈C определим wS(v) = |S\N(v)| (количество вершин в S, не являющихся соседями v)

1. Упорядочить C по неубыванию wS(v), получив ⟨v1,...,v|C|⟩
2. Найти максимальное k такое, что wS(Sk) + |E(S)| ≤ gf(|S|+k), где gf(n)=(n choose 2)-f(n)
3. Вернуть |S|+k

Корректность (Lemma 6): wS(S') + |E(S)| недооценивает |E(S∪S')|

Улучшенная верхняя граница на основе упорядочения (SortBound)

Основная идея:

1. Простая верхняя граница игнорирует рёбра между S и C
2. Простая верхняя граница не учитывает ограничение на двухшаговый диаметр

Поток алгоритма:

1. Использовать жадный алгоритм для разбиения C на χ независимых множеств Π1,...,Πχ
   (минимизация χ ≈ задача раскраски графа, жадный алгоритм O(|C|³))

2. Для каждого Πi:
   a. Упорядочить Πi по wS(v)
   b. Дополнительно разбить Πi на несколько Rσ, такие что любые две вершины в Rσ находятся на расстоянии >2
   c. Из каждого Rσ выбрать вершину с минимальным wS(·) и добавить в C'
   d. Вычислить w'S(uj) = wS(uj) + j - 1

3. Упорядочить C' по w'S(·), найти максимальное k такое что |E(S)| + w'S(Sk) ≤ gf(|S|+k)

4. Вернуть |S|+k

Временная сложность: O(|C|³ + |S||C|)

Корректность (Theorem 3):

• Из каждого независимого множества Πi можно выбрать не более s'i вершин
• Из каждого Rσ можно выбрать не более 1 вершины из-за ограничения на двухшаговый диаметр
• |E(S*)| ≥ |E(S)| + Σw'S(v^(ij)m) ≥ |E(S)| + Σ^{|S'|} w'S(vj)

Преимущества:

• Учитывает структуру независимых множеств (снижает переоценку количества рёбер)
• Учитывает ограничение на двухшаговый диаметр (из каждого Rσ не более 1 вершины)
• Быстрее чем LP-релаксация, границы близки

Экспериментальная установка

Набор данных

• Источник: Network Data Repository
• Масштаб: 139 реальных неориентированных графов
• Диапазон: до 5.87×10⁷ вершин, 1.06×10⁸ рёбер
• Области: социальные сети, биологические сети, сети сотрудничества, дорожные сети и т.д.

Конфигурация функций f(·)

1. γ-квазиклика: f(i) = γ(i choose 2), γ ∈ {0.99, 0.95, 0.90, 0.85}
   • Ненаследственная функция
2. s-дефектная клика: f(i) = (i choose 2) - s, s ∈ {1, 3}
   • Наследственная функция

Сравниваемые алгоритмы

1. Deg-BnB: упорядочение по вырожденности + ветви и границы
2. TwoDeg-BnB: упорядочение по двухшаговой вырожденности + ветви и границы
3. BnB: чистые ветви и границы (без декомпозиции)
4. MIP: решатель Gurobi + модель MIP-fD
5. Deg-MIP: декомпозиция по вырожденности + решение подзадач MIP
6. TwoDeg-MIP: декомпозиция по двухшаговой вырожденности + решение подзадач MIP

Экспериментальная среда

• CPU: Intel Xeon Platinum 8360Y @ 2.40GHz
• Система: Ubuntu 22.04
• Компиляция: g++ 9.3.0 с флагом -Ofast
• Ограничение времени: 3600 секунд (1 час)
• Код: https://github.com/cy-Luo000/MDSL

Метрики оценки

• Количество решённых экземпляров в разные моменты времени
• Время выполнения на конкретных графах
• Плотность верхней границы (разница с оптимальным решением)
• Количество узлов в дереве поиска

Экспериментальные результаты

Основные результаты

1. Общая производительность (Figure 4 & 5)

γ-квазиклика (γ=0.99, 0.95):

• TwoDeg-BnB и Deg-BnB полностью превосходят другие алгоритмы во все временные периоды
• За 1 час TwoDeg-BnB решает около 100 экземпляров, BnB только 50
• MIP практически не может решить ни один экземпляр

γ-квазиклика (γ=0.90, 0.85):

• После 1000 секунд TwoDeg-MIP и Deg-MIP показывают производительность, близкую к методам ветвей и границ
• Схема декомпозиции значительно улучшает производительность MIP

s-дефектная клика (s=1, 3):

• TwoDeg-BnB и Deg-BnB решают около 110 экземпляров
• Чистый BnB решает около 60 экземпляров
• Наследственное свойство даёт большее преимущество методам ветвей и границ

Ключевое открытие: схема декомпозиции удваивает количество решённых экземпляров

2. Детальные результаты на больших графах (Table 1 & 2)

Значительные случаи (γ=0.99):

• web-uk-2005 (129,632 вершины): TwoDeg-BnB 634 сек, MIP превышает лимит времени
• inf-road-usa (23,947,347 вершин): TwoDeg-BnB 70 сек, другие методы превышают лимит времени
• scc_infect-dublin: Deg-BnB 0.54 сек, TwoDeg-BnB превышает лимит (выбор упорядочения влияет)

Эффект ускорения:

• TwoDeg-BnB быстрее BnB в 2-3 порядка величины (например, web-indochina-2004: 0.25 сек vs превышение лимита)
• 39 экземпляров решены TwoDeg-BnB или Deg-BnB, но не BnB
• Декомпозиция+MIP иногда превосходит чистый комбинаторный алгоритм (например, web-sk-2005)

s-дефектная клика (Table 2):

• Наследственное свойство обеспечивает больше сокращений
• scc_infect-dublin (s=1): TwoDeg-BnB 0.83 сек vs Deg-MIP превышает лимит
• rec-amazon: TwoDeg-BnB 0.08 сек vs BnB 264 сек

Абляционные исследования

Анализ эффективности верхней границы (Table 3 & 4)

Сравнение плотности верхней границы:

LP-релаксация > SortBound > Простая граница

Конкретные случаи (γ=0.95):

• ca-CondMat:
  • Оптимум: 28
  • LP: 29, Простая: 280, SortBound: 142
  • SortBound достигает баланса между плотностью и масштабируемостью
• inf-roadNet-CA:
  • Оптимум: 4
  • LP: невозможно вычислить, Простая: 13, SortBound: 5
  • LP неработоспособна на больших графах

Влияние размера дерева поиска:

• inf-roadNet-CA (γ=0.95):
  • TwoDeg-BnB: 5 сек, 10 узлов
  • TwoDeg-BnB/ub (без SortBound): 10 сек, 14,138,820 узлов
  • Сокращение дерева поиска на 6 порядков величины
• ca-MathSciNet (s=3):
  • TwoDeg-BnB: 7.62 сек, 80 узлов
  • TwoDeg-BnB/ub: 1228 сек, 256,325,020 узлов
  • Ускорение в 100 раз

Ключевое открытие: SortBound сохраняет плотность границы при масштабировании до графов с миллионами вершин

Связь αG и времени выполнения (Figure 6 & 7)

Наблюдения:

• Около половины экземпляров имеют αG ≤ 1000 (намного меньше |V|)
• Время выполнения положительно коррелирует с αG
• Упорядочение по двухшаговой вырожденности обычно даёт меньший αG

Типичные случаи:

• ca-dblp-2010: |V|=226,413, dG=74, tdG=238, dG·ΔG=17,612
  • Явное преимущество упорядочения по двухшаговой вырожденности

Верификация: поддерживает идею минимизации αG

Анализ конкретных случаев

Пример эффекта декомпозиции графа

На примере web-indochina-2004 (|V|=11,358, |E|=47,606):

• Вырожденность: dG=49
• Двухшаговая вырожденность: tdG=199
• После декомпозиции: αG=199 (двухшаговое упорядочение) vs αG≈2450 (упорядочение по вырожденности)
• Производительность: TwoDeg-BnB 0.25 сек vs Deg-BnB 0.18 сек vs BnB 12.10 сек

Пример алгоритма верхней границы (Figure 2 & 3)

Входные данные: 10 вершин, S={v1,v2}, C={v3,...,v10}

Шаги:

1. Разбиение на независимые множества: Π1={v3,v5,v7,v9}, Π2={v4,v6,v8,v10}
2. Вычисление wS: wS(v3)=0, wS(v5)=1, wS(v7)=2...
3. Дополнительное разбиение по расстоянию: R¹₁={v3,v7}, R²₁={v5,v9}, R¹₂={v8,v4}, R²₂={v10,v6}
4. Выбор минимального wS: C'={v3,v5,v8,v10}
5. Вычисление w'S: w'S(v3)=0, w'S(v8)=0, w'S(v5)=2, w'S(v10)=2

Результаты:

• f(i)=0.8(i choose 2): верхняя граница=4
• f(i)=(i choose 2)-4: верхняя граница=5

Связанные работы

1. Модели релаксации клик

• γ-квазиклика (Abello et al. 2002): NP-трудна для γ∈(0,1]
  • Методы MIP (Pattillo et al. 2013a)
  • Ветви и границы (Mahdavi Pajouh et al. 2014, Ribeiro & Riveaux 2019)
• s-дефектная клика (Yu et al. 2006): NP-трудна для s≥1
  • Ограничение на малый диаметр (Luo et al. 2024): O(nc·1.2ⁿ)
  • Ветви и границы (Chen et al. 2021b, Gao et al. 2022, Chang 2023)
• Средняя s-plex (Veremyev et al. 2016)

2. Универсальные f(·)-плотные графы

• Veremyev et al. 2016:
  • Предложены несколько моделей MIP (GF3 оптимальна)
  • Не учитывают ограничения на малый диаметр
• Результаты сложности (Asahiro et al. 2002):
  • NP-трудна при f(n)=Θ(n^(1+ε)) или f(n)=n+Ω(n^ε)
  • Полиномиально разрешима при f(n)=n+c

3. Задача 2-club

• Определение: подграф с диаметром ≤2
• Методы MIP (Pajouh et al. 2016, Lu et al. 2022)
• Ветви и границы (Hartung et al. 2012, Komusiewicz et al. 2019)
• Вклад работы: первое объединение 2-club с ограничением f(·)-плотности

4. Ограничения связности

• Santos et al. 2024: ограничения связности на основе остовного дерева для γ-квазиклик
• Преимущество работы: ограничение на диаметр сильнее простой связности

5. Техники декомпозиции графа

• Упорядочение по вырожденности (Matula & Beck 1983): O(|V|+|E|)
• Двухшаговая вырожденность (Wünsche 2021): впервые применена к k-plex и k-club
• Инновация работы: систематическое применение к универсальным f(·)-плотным графам

Заключение и обсуждение

Основные выводы

1. Теоретические вклады:
   • Систематизирована теоретическая схема f(·)-плотных графов
   • Доказаны необходимые и достаточные условия наследственного свойства
   • Предоставлены анализ корректности и сложности схемы декомпозиции
2. Алгоритмические вклады:
   • Схема декомпозиции разлагает задачу на n независимых подзадач
   • Упорядочение по двухшаговой вырожденности эффективно контролирует размер подграфов
   • Верхняя граница на основе упорядочения достигает баланса между плотностью и эффективностью
3. Экспериментальная верификация:
   • Количество решённых экземпляров на 139 реальных графах удвоено
   • Масштабируется до графов с десятками миллионов вершин
   • Верхняя граница на основе упорядочения сокращает дерево поиска на 6 порядков величины

Ограничения

1. Ограничения алгоритма:
   • Остаётся экспоненциальным алгоритмом (O(2^αG))
   • Для плотных графов αG может быть близко к |V|
   • Сложно предварительно определить, какая из двух стратегий упорядочения лучше
2. Ограничения модели:
   • Ограничение диаметра=2 может быть слишком строгим
   • Не учитываются веса вершин или рёбер
   • f(·) должна удовлетворять определённым условиям для наследственного свойства
3. Ограничения экспериментов:
   • Тестированы только две функции f(·)
   • Нет прямого сравнения со всеми связанными работами
   • Отсутствуют тесты на сверхбольших графах (сотни миллионов вершин)

Направления будущих исследований

1. Расширение алгоритмов:
   • Параллелизация схемы декомпозиции (подграфы независимы и могут обрабатываться параллельно)
   • Расширение на другие ограничения диаметра (k-club, k≥3)
   • Объединение с другими структурными ограничениями (вершинная связность)
2. Углубление теории:
   • Анализ наследственного свойства для большего числа функций f(·)
   • Исследование параметризованной сложности
   • Разработка алгоритмов аппроксимации
3. Расширение приложений:
   • Инкрементальные алгоритмы для динамических графов
   • Расширение на взвешенные графы
   • Специализированные модели для конкретных областей (биологические сети)

Глубокая оценка

Преимущества

1. Теоретическая строгость:
   • Полные математические доказательства (приложение A)
   • Ясный анализ сложности
   • Необходимые и достаточные условия наследственного свойства (Lemma 1 & 2)
2. Алгоритмическая инновативность:
   • Схема декомпозиции: Lemma 3 элегантно разлагает глобальную задачу на локальные подзадачи
   • Упорядочение по двухшаговой вырожденности: инновационная стратегия упорядочения, специально разработанная для ограничения на диаметр
   • Верхняя граница на основе упорядочения: многоуровневое разбиение (независимые множества + ограничение расстояния) показывает изящный дизайн
3. Полнота экспериментов:
   • 139 реальных графов, 6 алгоритмов, 2 класса функций f(·)
   • Детальные абляционные исследования (Table 3 & 4)
   • Визуальный анализ (Figure 6 & 7)
   • Открытый исходный код обеспечивает воспроизводимость
4. Практическая ценность:
   • Масштабируется до графов с десятками миллионов вершин
   • На несколько порядков быстрее чем MIP
   • Универсальная схема применима к различным моделям релаксации клик
5. Ясность изложения:
   • Чёткая мотивация во введении (Figure 1 интуитивна)
   • Детальные псевдокоды алгоритмов
   • Полные доказательства теорем

Недостатки

1. Выбор стратегии упорядочения:
   • Отсутствует теоретическое руководство о том, когда использовать вырожденность vs двухшаговую вырожденность
   • Table 1 показывает, что иногда Deg-BnB быстрее (например, scc_infect-dublin)
   • Рекомендация: разработать адаптивную стратегию или эвристику выбора
2. Сложность алгоритма верхней границы:
   • O(|C|³) может стать узким местом
   • Жадная раскраска неоптимальна
   • Направление улучшения: использовать более быстрые алгоритмы раскраски или ослабить оптимальность
3. Сравнение экспериментов:
   • Нет сравнения с методом остовного дерева Santos et al. 2024
   • Отсутствует сравнение со специализированными алгоритмами (например, алгоритм Chang 2023 для k-дефектной клики)
   • Модель MIP может быть улучшена (например, добавлением действительных неравенств)
4. Анализ масштабируемости:
   • Недостаточное обсуждение случаев αG>10,000
   • Недостаточное тестирование на плотных графах
   • Отсутствует анализ потребления памяти
5. Теоретические пробелы:
   • Не предоставлены результаты по коэффициенту аппроксимации
   • Параметризованная сложность (например, с параметром αG) не обсуждается
   • Анализ среднего случая отсутствует

Влияние

1. Академический вклад:
   • Объединяет различные модели релаксации клик в единую теоретическую схему
   • Техники декомпозиции могут быть перенесены на другие задачи извлечения подграфов
   • Высокая цитируемость (объединяет NP-трудные задачи, декомпозицию графов, ветви и границы)
2. Практическая ценность:
   • Прямое применение в обнаружении сообществ, биоинформатике и других областях
   • Открытый исходный код способствует технологическому переносу
   • Может служить базовым методом для других алгоритмов
3. Воспроизводимость:
   • Алгоритмы описаны детально
   • Исходный код открыт (https://github.com/cy-Luo000/MDSL)
   • Наборы данных общедоступны (Network Data Repository)
   • Параметры экспериментов чётко определены
4. Ограничения:
   • Промышленное применение требует дальнейшей оптимизации (например, параллелизация)
   • Специализированные алгоритмы для конкретных f(·) могут быть более эффективны
   • Требуется проверка практической применимости экспертами в конкретных областях

Рекомендуемые сценарии применения

Рекомендуемые сценарии:

1. Анализ социальных сетей: поиск плотно связанных сообществ (диаметр ≤2 гарантирует быструю коммуникацию)
2. Биологические сети: идентификация белковых комплексов (допускает несколько отсутствующих рёбер)
3. Сети сотрудничества: выявление основных исследовательских групп
4. Графы среднего размера: |V|<10⁶, αG<5000 показывают оптимальную производительность

Не рекомендуемые сценарии:

1. Сверхбольшие плотные графы: αG близко к |V| приводит к экспоненциальному взрыву
2. Приложения реального времени: в худшем случае требуется экспоненциальное время
3. Сценарии, где приемлема приблизительная решение: точный алгоритм имеет высокую стоимость

Рекомендации по улучшению:

1. Объединить с эвристическими алгоритмами для быстрого получения приблизительных решений
2. Параллелизировать обработку больших графов
3. Разработать специализированные алгоритмы для конкретных функций f(·)

Библиография

Ключевые связанные работы

1. Veremyev et al. (2016): "Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs" — предложены модели MIP GF3
2. Luo et al. (2024): "A faster branching algorithm for the maximum k-defective clique problem" — ECAI 2024, алгоритм O(nc·1.2ⁿ)
3. Chang (2023): "Efficient maximum k-defective clique computation with improved time complexity" — PACMMOD, улучшенные ветви и границы
4. Santos et al. (2024): "Ensuring connectedness for the maximum quasi-clique and densest k-subgraph problems" — ограничения связности на основе остовного дерева
5. Wünsche (2021): "Mind the gap when searching for relaxed cliques" — впервые предложено упорядочение по двухшаговой вырожденности

Теоретические основы

6. Matula & Beck (1983): "Smallest-last ordering and clustering and graph coloring algorithms" — классическая работа по упорядочению по вырожденности
7. Asahiro et al. (2002): "Complexity of finding dense subgraphs" — результаты сложности для f(·)-плотных графов
8. Downey & Fellows (2012): "Parameterized complexity" — теория W1-трудности

Общая оценка: Это высококачественная статья с строгой теорией, инновационными алгоритмами и полными экспериментами. Схема декомпозиции и методы верхних границ на основе упорядочения имеют высокую универсальность и практическую ценность. Основной вклад заключается в объединении различных моделей релаксации клик и предоставлении эффективного алгоритма решения. Рекомендуется принятие. Работа имеет важное значение для области алгоритмов на графах и анализа сетей.