Un Approccio Branch-and-Bound per Problemi di Sottografi Densi a Basso Diametro Massimale

Informazioni Fondamentali

• ID Articolo: 2511.03157
• Titolo: A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
• Autori: Yi Zhou (University of Electronic Science and Technology of China), Chunyu Luo (University of Electronic Science and Technology of China), Zhengren Wang (Peking University), Zhang-Hua Fu (Shenzhen Institute of Artificial Intelligence and Robotics for Society, CUHK Shenzhen)
• Classificazione: cs.DS (Strutture Dati e Algoritmi)
• Data di Pubblicazione: 6 novembre 2025 (arXiv v2)
• Link Articolo: https://arxiv.org/abs/2511.03157v2

Riassunto

Questo articolo affronta il problema del massimo sottografo f(·)-denso a basso diametro (MfDS). Un grafo f(·)-denso è un grafo con n vertici e almeno f(n) archi, dove f(·) è una funzione ben definita. Questo concetto comprende vari modelli di rilassamento della clique come quasi-clique γ, clique difettose k e clique dense. Tuttavia, i grafi f(·)-densi potrebbero non essere connessi o debolmente connessi. Per affrontare questo problema, l'articolo studia la ricerca del massimo sottografo f(·)-denso con diametro non superiore a 2. Nello specifico, viene proposto un algoritmo branch-and-bound basato sulla decomposizione per risolvere il problema in modo ottimale. La caratteristica chiave dell'algoritmo è la decomposizione del grafo in n sottografi più piccoli, consentendo la ricerca indipendente in ciascun sottografo. L'articolo introduce inoltre strategie di decomposizione come l'ordinamento per degenerazione e l'ordinamento per degenerazione a due salti, insieme a un algoritmo branch-and-bound con nuovi limiti superiori ordinati. I risultati sperimentali su 139 grafi reali dimostrano che l'algoritmo supera i risolutori MIP e i metodi branch-and-bound puri, risolvendo in modo ottimale quasi il doppio delle istanze entro un'ora.

Contesto di Ricerca e Motivazione

1. Problema da Risolvere

Nell'analisi delle reti, l'identificazione di sottografi strettamente connessi (cohesive subgraph) è un compito centrale, con applicazioni nella scoperta di comunità, identificazione di complessi proteici, analisi di reti finanziarie e altri campi. Il modello classico di clique richiede archi tra tutte le coppie di vertici, ma questo requisito è troppo rigoroso, specialmente nelle applicazioni pratiche con rumore e errori. Di conseguenza, sono emersi vari modelli di rilassamento della clique, come:

• Quasi-clique γ: sottografo indotto di n vertici con almeno γ(n choose 2) archi
• Clique difettosa s: con almeno (n choose 2) - s archi
• s-plex medio: con almeno n(n-s)/2 archi

Questi modelli possono essere unificati come grafi f(·)-densi: un grafo con n vertici ha almeno f(n) archi.

2. Importanza del Problema

I modelli di grafo f(·)-denso esistenti presentano un difetto grave: potrebbero non essere connessi o avere connettività debole. L'articolo illustra questo attraverso due esempi nella Figura 1:

• G1: una clique di 200 vertici più un percorso di 10 vertici, dove da v1 a v210 sono necessari 10 salti
• G2: una clique di 200 vertici più 10 vertici isolati, dove non esiste percorso tra v1 e v210

Entrambi i grafi soddisfano il requisito di densità f(n)=0.9(n choose 2), ma chiaramente non rappresentano comunità strettamente connesse.

3. Limitazioni dei Metodi Esistenti

• Metodo MIP: sebbene esistano modelli di programmazione lineare intera per funzioni f(·) specifiche (come GF3), sono inefficienti per grafi di grandi dimensioni e mancano modelli MIP per vincoli di basso diametro
• Metodo Branch-and-Bound: esistono algoritmi per problemi specifici (come massima clique difettosa, massima quasi-clique γ), ma manca un framework generale per risolvere grafi f(·)-densi
• Vincoli di Connettività: Santos et al. (2024) propongono vincoli di connettività basati su alberi di copertura, ma i vincoli di diametro garantiscono meglio la connettività stretta

4. Motivazione della Ricerca

Questo articolo introduce il concetto di grafo f(·)-denso a basso diametro: richiede che il grafo sia connesso, abbia almeno f(n) archi e diametro non superiore a 2. Il vincolo di diametro 2 (denominato 2-club) assicura che il percorso più breve tra due vertici qualsiasi non superi 2, garantendo forte connettività. L'articolo mira a progettare algoritmi esatti efficienti per risolvere questo problema NP-hard.

Contributi Principali

1. Formalizzazione del Problema:
   • Prima definizione sistematica di grafi f(·)-densi e loro proprietà ereditarie
   • Formalizzazione del problema del massimo sottografo f(·)-denso a basso diametro (MfDS)
   • Fornitura di modello di programmazione lineare intera MIP-fD
2. Framework Algoritmico:
   • Proposta di framework di preprocessing basato sulla decomposizione del grafo che decompone il grafo di input in n sottografi più piccoli
   • Introduzione di due strategie di decomposizione: ordinamento per degenerazione e ordinamento per degenerazione a due salti
   • Progettazione di algoritmo branch-and-bound con nuovi limiti superiori ordinati
   • Fornitura di analisi della complessità nel caso peggiore per componenti e algoritmo complessivo
3. Verifica Sperimentale:
   • Test su 139 grafi reali con due funzioni f(·) (quasi-clique γ e clique difettosa s)
   • Dimostrazione che il framework di decomposizione migliora significativamente le prestazioni, risolvendo il doppio delle istanze rispetto al branch-and-bound puro in un'ora
   • Dimostrazione che il metodo dei limiti superiori ordinati riduce significativamente la dimensione dell'albero di ricerca

Spiegazione Dettagliata del Metodo

Definizione del Compito

Input:

• Grafo semplice non orientato G=(V,E)
• Funzione di densità f: ℤ≥0 → ℝ, soddisfacente f(i) ≤ (i choose 2)
• Oracle di calcolo per f(·) (tempo costante)

Output: Massimo insieme di vertici S⊆V tale che:

1. |E(S)| ≥ f(|S|) (proprietà f(·)-denso)
2. diam(GS) ≤ 2 (vincolo di basso diametro)

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

Complessità: NP-hard, W1-hard, difficile da approssimare in tempo polinomiale (poiché la massima clique è un caso speciale)

Framework Algoritmico Principale

1. Framework di Decomposizione Complessivo (Algoritmo 1)

Lemma Chiave (Lemma 3): Dato un ordinamento arbitrario di vertici π=⟨v1,...,vn⟩ del grafo G, per ogni vertice vi, definiamo:

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

Se S_i è il massimo sottografo f(·)-denso a basso diametro in Gi contenente vi, allora: **ωf(G) = max(|S_1|,...,|S*_n|)**

Flusso dell'Algoritmo:

1. Ottenere soluzione iniziale S con algoritmo euristico (limite inferiore)
2. Determinare ordine dei vertici π con algoritmo di ordinamento
3. Per ogni vi in π:
   - Costruire sottografo Gi = G[Vi]
   - Risolvere con ExactSearch(Gi, f(·), {vi}, N^(2)_G(vi), lb)
4. Restituire massima soluzione tra tutti i sottoproblemi

Complessità Temporale: O(Theur(G) + Torder(G) + poly(αG)2^αG)

• αG = max(|V1|,...,|Vn|): dimensione massima del sottografo
• La chiave è minimizzare αG per controllare la parte esponenziale

2. Algoritmo Euristico Efficiente (Algoritmo 2)

Basato su ordinamento per degenerazione:

• Definizione: un ordinamento k-degenere è un ordinamento di vertici ⟨v1,...,vn⟩ dove ogni vi ha grado ≤ k nel sottografo indotto {vi,...,vn}
• Calcolo: algoritmo peel, tempo O(|V|+|E|), eliminazione ripetuta del vertice di grado minimo
• Grado di degenerazione dG: valore minimo di k

Flusso Euristico:

1. Calcolare ordinamento per degenerazione ⟨v1,...,vn⟩
2. Per ogni vi:
   - Si ← {vi} ∪ {NG(vi) ∩ {vi+1,...,vn}}
   - Gi ← G[Si] (diametro ≤ 2)
   - While |Ei| < f(|Si|):
       Eliminare vertice di grado minimo in Gi
   - Aggiornare soluzione ottimale S*
3. Restituire S*

Complessità Temporale: O(|E| + |V|d²G)

• Nei grafi reali dG << |V| (es. ca-dblp-2010: dG=74, |V|=226413)

3. Strategie di Ordinamento dei Vertici

Opzione 1: Ordinamento per Degenerazione

• Vantaggio: tempo O(|V|+|E|)
• Limite: αG ≤ min(dG·ΔG, |V|)
• Dimostrazione: |Vi| = 1 + |NG(vi)∩{vi+1,...,vn}| + |N^(2)_G(vi)\NG(vi)∩{vi+1,...,vn}| ≤ 1 + dG + dG·ΔG

Opzione 2: Ordinamento per Degenerazione a Due Salti (Algoritmo 3)

• Definizione: un ordinamento k-degenere a due salti dove ogni vi ha al massimo k vicini a due salti in {vi,...,vn}
• Calcolo: simile a peel, eliminazione ripetuta del vertice con minimo |N^(2)_G(v)|
• Complessità Temporale: O(|V||E|·min(tdG, ΔG))
• Limite: αG ≤ tdG
• Vantaggio: tdG è solitamente molto minore di dG·ΔG (es. ca-dblp-2010: tdG=238 vs dG·ΔG=17612)

Algoritmo Branch-and-Bound (Algoritmo 4)

Struttura Principale

BranchBound(G, S, C, lb):
  Input: grafo G, soluzione corrente S, insieme candidato C, limite inferiore lb
  
  1. Se G[S] è soluzione fattibile e |S|>lb: aggiornare lb e soluzione ottimale
  
  2. Se f(·) è ereditaria e |E(S)|<f(|S|): potatura e ritorno
  
  3. UB ← SortBound(G, f(·), S, C)  // calcolare limite superiore
  
  4. Se UB ≤ lb: potatura e ritorno
  
  5. Se f(·) è ereditaria: applicare regole di riduzione (Lemma 5)
  
  6. Selezionare casualmente u∈C
  
  7. Se soddisfa condizioni di Lemma 4: ricorsione solo su ramo S∪{u}
     Altrimenti: ricorsione su entrambi rami S∪{u} e S

Regole di Riduzione (Lemma 4 & 5)

Lemma 4 (Riduzione Universale): Se u∈C soddisfa:

1. |NG(u)| = |V|-1, oppure
2. |NG(u)| = |V|-2 e GS∪{u} è fattibile

Allora esiste soluzione ottimale contenente u → ricerca solo ramo contenente u

Lemma 5 (Riduzione per Funzioni Ereditarie): Se f(·) è ereditaria:

1. Se |E(S)| < f(|S|), allora nessuna soluzione fattibile contiene S
2. Se v∈C tale che |E(S∪{v})| < f(|S|+1), allora nessuna soluzione fattibile contiene v

Algoritmo di Limite Superiore Ordinato (Algoritmo 5)

Limite Superiore Semplice (Sezione 4.6.1)

Per v∈C, definiamo wS(v) = |S\N(v)| (numero di vertici in S non adiacenti a v)

1. Ordinare C in ordine non decrescente di wS(v) ottenendo ⟨v1,...,v|C|⟩
2. Trovare massimo k tale che wS(Sk) + |E(S)| ≤ gf(|S|+k), dove gf(n)=(n choose 2)-f(n)
3. Restituire |S|+k

Correttezza (Lemma 6): wS(S') + |E(S)| sottostima |E(S∪S')|

Limite Superiore Ordinato Migliorato (SortBound)

Idea Principale:

1. Il limite semplice ignora gli archi tra S e C
2. Il limite semplice non considera il vincolo a due salti

Flusso dell'Algoritmo:

1. Partizionare C in χ insiemi indipendenti Π1,...,Πχ con algoritmo greedy
   (minimizzare χ ≈ problema di colorazione grafo, greedy O(|C|³))

2. Per ogni Πi:
   a. Ordinare Πi per wS(v)
   b. Partizionare ulteriormente Πi in Rσ, dove vertici in Rσ hanno distanza >2
   c. Da ogni Rσ selezionare vertice con wS(·) minimo aggiungere a C'
   d. Calcolare w'S(uj) = wS(uj) + j - 1

3. Ordinare C' per w'S(·), trovare massimo k tale che |E(S)| + w'S(Sk) ≤ gf(|S|+k)

4. Restituire |S|+k

Complessità Temporale: O(|C|³ + |S||C|)

Correttezza (Teorema 3):

• Ogni insieme indipendente Πi può contribuire al massimo s'i vertici
• Ogni Rσ può contribuire al massimo 1 vertice per il vincolo a due salti
• |E(S*)| ≥ |E(S)| + Σw'S(v^(ij)m) ≥ |E(S)| + Σ^{|S'|} w'S(vj)

Vantaggi:

• Considera la struttura di insieme indipendente (riduce sovrastima degli archi)
• Considera il vincolo a due salti (al massimo 1 vertice per Rσ)
• Più veloce del rilassamento LP, limiti comparabili

Configurazione Sperimentale

Dataset

• Fonte: Network Data Repository
• Scala: 139 grafi non orientati reali
• Intervallo: fino a 5.87×10⁷ vertici, 1.06×10⁸ archi
• Domini: reti sociali, reti biologiche, reti di collaborazione, reti stradali, ecc.

Configurazione Funzione f(·)

1. Quasi-clique γ: f(i) = γ(i choose 2), γ ∈ {0.99, 0.95, 0.90, 0.85}
   • Funzione non ereditaria
2. Clique difettosa s: f(i) = (i choose 2) - s, s ∈ {1, 3}
   • Funzione ereditaria

Algoritmi di Confronto

1. Deg-BnB: ordinamento per degenerazione + branch-and-bound
2. TwoDeg-BnB: ordinamento per degenerazione a due salti + branch-and-bound
3. BnB: branch-and-bound puro (senza decomposizione)
4. MIP: risolutore Gurobi + modello MIP-fD
5. Deg-MIP: decomposizione per degenerazione + risoluzione MIP sottoproblemi
6. TwoDeg-MIP: decomposizione per degenerazione a due salti + risoluzione MIP sottoproblemi

Ambiente Sperimentale

• CPU: Intel Xeon Platinum 8360Y @ 2.40GHz
• Sistema: Ubuntu 22.04
• Compilazione: g++ 9.3.0 con -Ofast
• Limite Temporale: 3600 secondi (1 ora)
• Codice: https://github.com/cy-Luo000/MDSL

Metriche di Valutazione

• Numero di istanze risolte in diversi intervalli temporali
• Tempo di esecuzione per grafi specifici
• Stretta dei limiti superiori (differenza dalla soluzione ottimale)
• Numero di nodi nell'albero di ricerca

Risultati Sperimentali

Risultati Principali

1. Prestazioni Complessive (Figure 4 & 5)

Quasi-clique γ (γ=0.99, 0.95):

• TwoDeg-BnB e Deg-BnB superano completamente altri algoritmi in tutti gli intervalli temporali
• In 1 ora, TwoDeg-BnB risolve circa 100 istanze, BnB solo 50
• MIP praticamente non risolve alcuna istanza

Quasi-clique γ (γ=0.90, 0.85):

• Dopo 1000 secondi, TwoDeg-MIP e Deg-MIP hanno prestazioni comparabili ai metodi branch-and-bound
• Il framework di decomposizione migliora significativamente le prestazioni MIP

Clique difettosa s (s=1, 3):

• TwoDeg-BnB e Deg-BnB risolvono circa 110 istanze
• BnB puro circa 60 istanze
• La proprietà ereditaria fornisce maggiori vantaggi ai metodi branch-and-bound

Scoperta Chiave: Il framework di decomposizione raddoppia il numero di istanze risolte

2. Risultati Dettagliati su Grafi di Grandi Dimensioni (Tabelle 1 & 2)

Casi Significativi (γ=0.99):

• web-uk-2005 (129,632 vertici): TwoDeg-BnB 634 secondi, MIP timeout
• inf-road-usa (23,947,347 vertici): TwoDeg-BnB 70 secondi, altri metodi timeout
• scc_infect-dublin: Deg-BnB 0.54 secondi, TwoDeg-BnB timeout (scelta ordinamento influenza)

Effetto di Accelerazione:

• TwoDeg-BnB è 2-3 ordini di grandezza più veloce di BnB (es. web-indochina-2004: 0.25 secondi vs timeout)
• 39 istanze risolte da TwoDeg-BnB o Deg-BnB ma non da BnB
• Decomposizione+MIP talvolta superiore a algoritmi combinatori puri (es. web-sk-2005)

Clique Difettosa (Tabella 2):

• La proprietà ereditaria fornisce più potature
• scc_infect-dublin (s=1): TwoDeg-BnB 0.83 secondi vs Deg-MIP timeout
• rec-amazon: TwoDeg-BnB 0.08 secondi vs BnB 264 secondi

Esperimenti di Ablazione

Analisi Efficacia Limite Superiore (Tabelle 3 & 4)

Confronto Stretta Limite:

Rilassamento LP > SortBound > Limite Semplice

Casi Specifici (γ=0.95):

• ca-CondMat:
  • Ottimale: 28
  • LP: 29, Semplice: 280, SortBound: 142
  • SortBound raggiunge equilibrio tra stretta e scalabilità
• inf-roadNet-CA:
  • Ottimale: 4
  • LP: non calcolabile, Semplice: 13, SortBound: 5
  • LP fallisce su grafi grandi

Impatto Dimensione Albero di Ricerca:

• inf-roadNet-CA (γ=0.95):
  • TwoDeg-BnB: 5 secondi, 10 nodi
  • TwoDeg-BnB/ub (senza SortBound): 10 secondi, 14,138,820 nodi
  • Riduzione albero di ricerca 6 ordini di grandezza
• ca-MathSciNet (s=3):
  • TwoDeg-BnB: 7.62 secondi, 80 nodi
  • TwoDeg-BnB/ub: 1228 secondi, 256,325,020 nodi
  • Accelerazione 100 volte

Scoperta Chiave: SortBound mantiene stretta limite mentre scala a grafi con milioni di vertici

Relazione tra αG e Tempo di Esecuzione (Figure 6 & 7)

Osservazioni:

• Circa metà delle istanze hanno αG ≤ 1000 (molto minore di |V|)
• Tempo di esecuzione correlato positivamente con αG
• Ordinamento per degenerazione a due salti solitamente produce αG più piccolo

Casi Tipici:

• ca-dblp-2010: |V|=226,413, dG=74, tdG=238, dG·ΔG=17,612
  • Vantaggio evidente ordinamento degenerazione a due salti

Verifica: Supporta il principio di progettazione di minimizzare αG

Analisi di Casi

Esempio Effetto Decomposizione Grafo

Per web-indochina-2004 (|V|=11,358, |E|=47,606):

• Grado di Degenerazione: dG=49
• Grado Degenerazione Due Salti: tdG=199
• Dopo Decomposizione: αG=199 (ordinamento due salti) vs αG≈2450 (ordinamento degenerazione)
• Prestazioni: TwoDeg-BnB 0.25 secondi vs Deg-BnB 0.18 secondi vs BnB 12.10 secondi

Esempio Algoritmo Limite Superiore (Figure 2 & 3)

Input: 10 vertici, S={v1,v2}, C={v3,...,v10}

Passaggi:

1. Partizionare in insiemi indipendenti: Π1={v3,v5,v7,v9}, Π2={v4,v6,v8,v10}
2. Calcolare wS: wS(v3)=0, wS(v5)=1, wS(v7)=2...
3. Partizionare ulteriormente per distanza: R¹₁={v3,v7}, R²₁={v5,v9}, R¹₂={v8,v4}, R²₂={v10,v6}
4. Selezionare minimo wS: C'={v3,v5,v8,v10}
5. Calcolare w'S: w'S(v3)=0, w'S(v8)=0, w'S(v5)=2, w'S(v10)=2

Risultato:

• f(i)=0.8(i choose 2): limite superiore=4
• f(i)=(i choose 2)-4: limite superiore=5

Lavori Correlati

1. Modelli di Rilassamento della Clique

• Quasi-clique γ (Abello et al. 2002): NP-hard per γ∈(0,1]
  • Metodo MIP (Pattillo et al. 2013a)
  • Branch-and-bound (Mahdavi Pajouh et al. 2014, Ribeiro & Riveaux 2019)
• Clique difettosa s (Yu et al. 2006): NP-hard per s≥1
  • Vincolo basso diametro (Luo et al. 2024): O(nc·1.2ⁿ)
  • Branch-and-bound (Chen et al. 2021b, Gao et al. 2022, Chang 2023)
• s-plex medio (Veremyev et al. 2016)

2. Grafi f(·)-Densi Generici

• Veremyev et al. 2016:
  • Propone più modelli MIP (GF3 ottimale)
  • Non considera vincoli di basso diametro
• Risultati di Complessità (Asahiro et al. 2002):
  • NP-hard quando f(n)=Θ(n^(1+ε)) o f(n)=n+Ω(n^ε)
  • Polinomiale quando f(n)=n+c

3. Problema 2-club

• Definizione: sottografo con diametro ≤ 2
• Metodo MIP (Pajouh et al. 2016, Lu et al. 2022)
• Branch-and-bound (Hartung et al. 2012, Komusiewicz et al. 2019)
• Contributo Articolo: Prima combinazione di 2-club con vincolo f(·)-denso

4. Vincoli di Connettività

• Santos et al. 2024: quasi-clique γ connessa basata su albero di copertura
• Vantaggio Articolo: vincolo di diametro più forte della semplice connettività

5. Tecniche di Decomposizione Grafo

• Ordinamento per Degenerazione (Matula & Beck 1983): O(|V|+|E|)
• Degenerazione Due Salti (Wünsche 2021): primo uso per k-plex e k-club
• Innovazione Articolo: applicazione sistematica a grafi f(·)-densi generici

Conclusioni e Discussione

Conclusioni Principali

1. Contributi Teorici:
   • Framework teorico sistematizzato per grafi f(·)-densi
   • Dimostrazione di condizioni necessarie e sufficienti per proprietà ereditaria
   • Analisi di correttezza e complessità del framework di decomposizione
2. Contributi Algoritmici:
   • Framework di decomposizione che divide il problema in n sottoproblemi indipendenti
   • Ordinamento per degenerazione a due salti che controlla efficacemente la dimensione dei sottografi
   • Limite superiore ordinato che raggiunge equilibrio tra stretta e efficienza
3. Verifica Sperimentale:
   • Raddoppia il numero di istanze risolte su 139 grafi reali
   • Scalabile a grafi con decine di milioni di vertici
   • Limite superiore ordinato riduce albero di ricerca di 6 ordini di grandezza

Limitazioni

1. Limitazioni Algoritmiche:
   • Ancora algoritmo tempo esponenziale (O(2^αG))
   • Per grafi densi αG potrebbe avvicinarsi a |V|
   • Difficile predire a priori quale strategia di ordinamento sia migliore
2. Limitazioni Modello:
   • Vincolo diametro=2 potrebbe essere troppo rigoroso
   • Non considera pesi su vertici o archi
   • f(·) deve soddisfare condizioni specifiche per proprietà ereditaria
3. Limitazioni Sperimentali:
   • Test solo su due funzioni f(·)
   • Mancano confronti diretti con tutti i lavori correlati
   • Mancano test su grafi ultra-grandi (miliardi di vertici)

Direzioni Future

1. Estensioni Algoritmiche:
   • Parallelizzazione del framework di decomposizione (sottografi indipendenti parallelizzabili)
   • Estensione ad altri vincoli di diametro (k-club, k≥3)
   • Combinazione con altri vincoli strutturali (connettività di vertici)
2. Approfondimento Teorico:
   • Analisi proprietà ereditaria per più funzioni f(·)
   • Ricerca di complessità parametrizzata
   • Progettazione di algoritmi di approssimazione
3. Estensioni Applicative:
   • Algoritmi incrementali per grafi dinamici
   • Estensione a grafi pesati
   • Modelli specifici per domini (es. reti biologiche)

Valutazione Approfondita

Punti di Forza

1. Rigore Teorico:
   • Dimostrazioni matematiche complete (Appendice A)
   • Analisi di complessità chiara
   • Condizioni necessarie e sufficienti per proprietà ereditaria (Lemma 1 & 2)
2. Innovazione Algoritmica:
   • Framework di Decomposizione: Lemma 3 decompone ingegnosamente il problema globale in problemi locali
   • Ordinamento Degenerazione Due Salti: strategia di ordinamento innovativa per vincoli di diametro
   • Limite Superiore Ordinato: progettazione sofisticata con partizionamento annidato (insiemi indipendenti + vincoli di distanza)
3. Completezza Sperimentale:
   • 139 grafi reali, 6 algoritmi, 2 classi di funzioni f(·)
   • Esperimenti di ablazione dettagliati (Tabelle 3 & 4)
   • Analisi visuale (Figure 6 & 7)
   • Codice open source garantisce riproducibilità
4. Valore Pratico:
   • Scalabile a decine di milioni di vertici
   • Ordini di grandezza più veloce di MIP
   • Framework generico applicabile a vari modelli di rilassamento della clique
5. Chiarezza Esposizione:
   • Motivazione introduttiva chiara (Figura 1 intuitiva)
   • Pseudocodice algoritmi dettagliato
   • Dimostrazioni teoremi complete

Insufficienze

1. Scelta Strategia Ordinamento:
   • Manca guida teorica su quando usare degenerazione vs degenerazione due salti
   • Tabella 1 mostra talvolta Deg-BnB più veloce (es. scc_infect-dublin)
   • Suggerimento: progettare strategia adattiva o fornire euristica di selezione
2. Complessità Algoritmo Limite Superiore:
   • O(|C|³) potrebbe diventare collo di bottiglia
   • Colorazione greedy non ottimale
   • Direzione miglioramento: algoritmi colorazione più veloci o rilassamento ottimalità
3. Confronto Sperimentale:
   • Manca confronto con metodo albero di copertura di Santos et al. 2024
   • Mancano confronti con algoritmi ottimali per problemi specifici (es. algoritmo Chang 2023 per clique difettosa k)
   • Modello MIP potrebbe avere spazio di miglioramento (es. aggiunta di disuguaglianze valide)
4. Analisi Scalabilità:
   • Discussione insufficiente per casi αG>10,000
   • Prestazioni su grafi densi non sufficientemente testate
   • Analisi consumo memoria mancante
5. Spazi Teorici:
   • Manca analisi rapporto di approssimazione
   • Complessità parametrizzata (es. con αG come parametro) non discussa
   • Complessità caso medio non analizzata

Impatto

1. Contributo Accademico:
   • Framework teorico unificato per vari modelli di rilassamento della clique
   • Tecniche di decomposizione trasferibili ad altri problemi di estrazione di sottografi
   • Alto valore citazionale (combina problema NP-hard, decomposizione grafo, branch-and-bound)
2. Valore Pratico:
   • Applicazione diretta in scoperta comunità, bioinformatica, ecc.
   • Codice open source facilita trasferimento tecnologico
   • Può servire come baseline per altri algoritmi
3. Riproducibilità:
   • Descrizione algoritmi dettagliata
   • Codice open source (https://github.com/cy-Luo000/MDSL)
   • Dataset pubblici (Network Data Repository)
   • Configurazione sperimentale esplicita
4. Limitazioni:
   • Applicazione industriale richiede ulteriore ottimizzazione (es. parallelizzazione)
   • Algoritmi personalizzati per f(·) specifiche potrebbero essere superiori
   • Necessita validazione da esperti di dominio per applicabilità pratica

Scenari Applicabili

Scenari Consigliati:

1. Analisi Reti Sociali: ricerca comunità strettamente connesse (diametro ≤ 2 garantisce comunicazione veloce)
2. Reti Biologiche: identificazione complessi proteici (consente pochi archi mancanti)
3. Reti di Collaborazione: identificazione team di ricerca nucleari
4. Grafi Scala Media: |V|<10⁶, αG<5000 prestazioni ottimali

Scenari Non Consigliati:

1. Grafi Densi Ultra-Grandi: αG vicino a |V| causa esplosione esponenziale
2. Applicazioni Real-Time: caso peggiore ancora tempo esponenziale
3. Scenari Soluzione Approssimata Sufficiente: costo algoritmo esatto elevato

Suggerimenti Miglioramento:

1. Combinare con algoritmi euristici per soluzione approssimata veloce
2. Parallelizzare per grafi ultra-grandi
3. Progettare algoritmi specializzati per f(·) specifiche

Bibliografia

Lavori Correlati Principali

1. Veremyev et al. (2016): "Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs" - Propone modello MIP GF3
2. Luo et al. (2024): "A faster branching algorithm for the maximum k-defective clique problem" - ECAI 2024, algoritmo O(nc·1.2ⁿ)
3. Chang (2023): "Efficient maximum k-defective clique computation with improved time complexity" - PACMMOD, branch-and-bound migliorato
4. Santos et al. (2024): "Ensuring connectedness for the maximum quasi-clique and densest k-subgraph problems" - Vincoli connettività basati su albero di copertura
5. Wünsche (2021): "Mind the gap when searching for relaxed cliques" - Primo ordinamento degenerazione due salti

Fondamenti Teorici

6. Matula & Beck (1983): "Smallest-last ordering and clustering and graph coloring algorithms" - Lavoro classico ordinamento degenerazione
7. Asahiro et al. (2002): "Complexity of finding dense subgraphs" - Risultati complessità grafi f(·)-densi
8. Downey & Fellows (2012): "Parameterized complexity" - Teoria W1-hardness

Valutazione Complessiva: Questo è un articolo eccellente con rigore teorico, innovazione algoritmica e esperimenti completi. Il framework di decomposizione e il metodo di limite superiore ordinato hanno elevata generalità e valore pratico. Il principale contributo risiede nell'unificazione di vari modelli di rilassamento della clique e nella fornitura di algoritmi efficienti per la risoluzione. Consigliato per l'accettazione, con significativo contributo ai campi degli algoritmi su grafi e analisi di reti.