Une Approche par Séparation et Évaluation pour les Problèmes de Sous-Graphes Denses de Faible Diamètre Maximum

Informations Fondamentales

• ID de l'article : 2511.03157
• Titre : A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
• Auteurs : 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)
• Classification : cs.DS (Structures de Données et Algorithmes)
• Date de publication : 6 novembre 2025 (arXiv v2)
• Lien de l'article : https://arxiv.org/abs/2511.03157v2

Résumé

Cet article étudie le problème du sous-graphe f(·)-dense de faible diamètre maximum (MfDS). Un graphe f(·)-dense est un graphe possédant n sommets et au moins f(n) arêtes, où f(·) est une fonction bien définie. Ce concept englobe plusieurs modèles de relaxation de clique, notamment les quasi-cliques γ, les cliques défectueuses de degré k et les cliques denses. Cependant, les graphes f(·)-denses peuvent ne pas être connexes ou être faiblement connexes. Pour résoudre ce problème, cet article étudie la recherche du sous-graphe f(·)-dense maximum avec un diamètre ne dépassant pas 2. Spécifiquement, un algorithme de séparation et évaluation basé sur la décomposition est proposé pour résoudre optimalement ce problème. La caractéristique clé de l'algorithme est la décomposition du graphe en n sous-graphes plus petits, permettant une recherche indépendante dans chaque sous-graphe. L'article introduit également des stratégies de décomposition telles que l'ordonnancement par dégénérescence et l'ordonnancement par dégénérescence à deux sauts, ainsi qu'un algorithme de séparation et évaluation avec des bornes d'ordonnancement novatrices. Les résultats expérimentaux sur 139 graphes réels montrent que l'algorithme surpasse les solveurs MIP et les méthodes de séparation et évaluation pures, résolvant optimalement presque deux fois plus d'instances en une heure.

Contexte et Motivation de la Recherche

1. Problème à Résoudre

L'identification de sous-graphes densément connectés (cohesive subgraph) est une tâche centrale en analyse de réseaux, avec des applications en découverte de communautés, identification de complexes protéiques, analyse de réseaux financiers, etc. Le modèle classique de clique exige une arête entre toutes les paires de sommets, mais cette exigence est trop stricte, particulièrement dans les applications pratiques avec bruit et erreurs. Plusieurs modèles de relaxation de clique ont donc émergé :

• Quasi-cliques γ : un sous-graphe induit de n sommets possédant au moins γ(n choose 2) arêtes
• Cliques défectueuses s : possédant au moins (n choose 2) - s arêtes
• s-plex moyen : possédant au moins n(n-s)/2 arêtes

Ces modèles peuvent être unifiés comme graphes f(·)-denses : un graphe de n sommets possédant au moins f(n) arêtes.

2. Importance du Problème

Les modèles existants de graphes f(·)-denses présentent un défaut grave : ils peuvent ne pas être connexes ou avoir une connectivité très faible. L'article illustre cela par deux exemples à la Figure 1 :

• G1 : une clique de 200 sommets plus un chemin de 10 sommets, nécessitant 10 sauts de v1 à v210
• G2 : une clique de 200 sommets plus 10 sommets isolés, sans chemin entre v1 et v210

Ces deux graphes satisfont l'exigence de densité f(n)=0.9(n choose 2), mais ne représentent clairement pas des communautés densément connectées.

3. Limitations des Méthodes Existantes

• Méthodes MIP : bien que des modèles de programmation linéaire en nombres entiers existent pour des fonctions f(·) spécifiques (comme GF3), ils sont inefficaces sur les graphes de grande taille et manquent de modèles MIP pour les contraintes de faible diamètre
• Méthodes de séparation et évaluation : des algorithmes existent pour des problèmes spécifiques (comme la clique défectueuse maximale, la quasi-clique maximale γ), mais manquent d'un cadre de résolution générique pour les graphes f(·)-denses
• Contraintes de connectivité : Santos et al. (2024) proposent des contraintes de connectivité basées sur les arbres couvrants, mais les contraintes de diamètre garantissent mieux la connectivité serrée

4. Motivation de la Recherche

Cet article introduit le concept de graphes f(·)-denses de faible diamètre : exigeant que le graphe soit connexe, possède au moins f(n) arêtes, et ait un diamètre ne dépassant pas 2. La contrainte de diamètre 2 (appelée 2-club) garantit que le chemin le plus court entre deux sommets quelconques ne dépasse pas 2, assurant une forte connectivité. L'article vise à concevoir des algorithmes exacts efficaces pour résoudre ce problème NP-difficile.

Contributions Principales

1. Formalisation du Problème :
   • Première définition systématique des graphes f(·)-denses et de leurs propriétés héréditaires
   • Formalisation du problème du sous-graphe f(·)-dense de faible diamètre maximum (MfDS)
   • Fourniture d'un modèle de programmation linéaire en nombres entiers MIP-fD
2. Cadre Algorithmique :
   • Proposition d'un cadre de prétraitement basé sur la décomposition de graphe, décomposant le graphe d'entrée en n sous-graphes plus petits
   • Introduction de deux stratégies de décomposition : l'ordonnancement par dégénérescence et l'ordonnancement par dégénérescence à deux sauts
   • Conception d'un algorithme de séparation et évaluation avec des bornes d'ordonnancement novatrices
   • Fourniture d'une analyse de complexité au pire cas pour chaque composant et l'algorithme global
3. Vérification Expérimentale :
   • Test sur 139 graphes réels avec deux fonctions f(·) (quasi-cliques γ et cliques défectueuses s)
   • Démonstration que le cadre de décomposition améliore significativement les performances, résolvant deux fois plus d'instances en une heure que la séparation et évaluation pure
   • Démonstration que la méthode de borne d'ordonnancement réduit considérablement la taille de l'arbre de recherche

Explication Détaillée de la Méthode

Définition de la Tâche

Entrée :

• Graphe simple non orienté G=(V,E)
• Fonction de densité f: ℤ≥0 → ℝ, satisfaisant f(i) ≤ (i choose 2)
• Oracle de calcul pour f(·) (temps constant)

Sortie : ensemble de sommets maximal S⊆V, tel que :

1. |E(S)| ≥ f(|S|) (propriété f(·)-dense)
2. diam(GS) ≤ 2 (contrainte de faible diamètre)

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

Complexité : NP-difficile, W1-difficile, difficile à approximer en temps polynomial (car la clique maximale en est un cas particulier)

Cadre Algorithmique Principal

1. Cadre de Décomposition Global (Algorithme 1)

Lemme Clé (Lemme 3) : Étant donné un ordonnancement arbitraire π=⟨v1,...,vn⟩ des sommets du graphe G, pour chaque sommet vi, définissons :

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

Si S_i est le sous-graphe f(·)-dense de faible diamètre maximal contenant vi dans Gi, alors : **ωf(G) = max(|S_1|,...,|S*_n|)**

Flux de l'Algorithme :

1. Obtenir une solution initiale S avec un algorithme heuristique (borne inférieure)
2. Déterminer l'ordre des sommets π avec un algorithme d'ordonnancement
3. Pour chaque vi dans π :
   - Construire le sous-graphe Gi = G[Vi]
   - Résoudre avec ExactSearch(Gi, f(·), {vi}, N^(2)_G(vi), lb)
4. Retourner la solution maximale de tous les sous-problèmes

Complexité Temporelle : O(Theur(G) + Torder(G) + poly(αG)2^αG)

• αG = max(|V1|,...,|Vn|) : taille maximale du sous-graphe
• L'objectif clé est de minimiser αG pour contrôler la partie exponentielle

2. Algorithme Heuristique Efficace (Algorithme 2)

Basé sur l'ordonnancement par dégénérescence :

• Définition : un ordonnancement k-dégénéré est un ordonnancement de sommets ⟨v1,...,vn⟩ tel que chaque vi a un degré ≤ k dans le sous-graphe induit par {vi,...,vn}
• Calcul : utiliser l'algorithme peel, O(|V|+|E|) temps, en supprimant répétitivement le sommet de degré minimal
• Degré de dégénérescence dG : la valeur k minimale

Flux Heuristique :

1. Calculer l'ordonnancement par dégénérescence ⟨v1,...,vn⟩
2. Pour chaque vi :
   - Si ← {vi} ∪ {NG(vi) ∩ {vi+1,...,vn}}
   - Gi ← G[Si] (diamètre ≤ 2)
   - Tant que |Ei| < f(|Si|) :
       Supprimer le sommet de degré minimal dans Gi
   - Mettre à jour la solution optimale S*
3. Retourner S*

Complexité Temporelle : O(|E| + |V|d²G)

• Dans les graphes réels dG << |V| (par exemple ca-dblp-2010 : dG=74, |V|=226413)

3. Stratégies d'Ordonnancement des Sommets

Option 1 : Ordonnancement par Dégénérescence

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

Option 2 : Ordonnancement par Dégénérescence à Deux Sauts (Algorithme 3)

• Définition : un ordonnancement k-dégénéré à deux sauts tel que chaque vi possède au maximum k voisins à deux sauts dans {vi,...,vn}
• Calcul : similaire à peel, en supprimant répétitivement le sommet avec le minimum |N^(2)_G(v)|
• Complexité Temporelle : O(|V||E|·min(tdG, ΔG))
• Borne : αG ≤ tdG
• Avantage : tdG est généralement bien inférieur à dG·ΔG (par exemple ca-dblp-2010 : tdG=238 vs dG·ΔG=17612)

Algorithme de Séparation et Évaluation (Algorithme 4)

Structure Principale

BranchBound(G, S, C, lb):
  Entrée : graphe G, solution courante S, ensemble candidat C, borne inférieure lb
  
  1. Si G[S] est une solution réalisable et |S|>lb : mettre à jour lb et la solution optimale
  
  2. Si f(·) est héréditaire et |E(S)|<f(|S|) : élaguer et retourner
  
  3. UB ← SortBound(G, f(·), S, C)  // Calculer la borne supérieure
  
  4. Si UB ≤ lb : élaguer et retourner
  
  5. Si f(·) est héréditaire : appliquer les règles de réduction (Lemme 5)
  
  6. Sélectionner aléatoirement u∈C
  
  7. Si les conditions du Lemme 4 sont satisfaites : récursion uniquement sur la branche S∪{u}
     Sinon : récursion sur les deux branches S∪{u} et S

Règles de Réduction (Lemme 4 & 5)

Lemme 4 (Réduction Générique) : si u∈C satisfait :

1. |NG(u)| = |V|-1, ou
2. |NG(u)| = |V|-2 et GS∪{u} est réalisable

alors il existe une solution optimale contenant u → il suffit de chercher la branche contenant u

Lemme 5 (Réduction pour Fonctions Héréditaires) : si f(·) est héréditaire :

1. Si |E(S)| < f(|S|), alors aucune solution réalisable ne contient S
2. Si v∈C tel que |E(S∪{v})| < f(|S|+1), alors aucune solution réalisable ne contient v

Algorithme de Borne d'Ordonnancement (Algorithme 5)

Borne Simple (Section 4.6.1)

Pour v∈C, définissons wS(v) = |S\N(v)| (nombre de sommets dans S non adjacents à v)

1. Ordonner C en ordre non décroissant de wS(v) pour obtenir ⟨v1,...,v|C|⟩
2. Trouver le maximum k tel que wS(Sk) + |E(S)| ≤ gf(|S|+k), où gf(n)=(n choose 2)-f(n)
3. Retourner |S|+k

Correction (Lemme 6) : wS(S') + |E(S)| sous-estime |E(S∪S')|

Borne d'Ordonnancement Améliorée (SortBound)

Idée Principale :

1. La borne simple ignore les arêtes entre S et C
2. La borne simple ne considère pas la contrainte à deux sauts

Flux de l'Algorithme :

1. Partitionner C en χ ensembles indépendants Π1,...,Πχ avec un algorithme glouton
   (minimiser χ ≈ problème de coloration de graphe, glouton en O(|C|³))

2. Pour chaque Πi :
   a. Ordonner Πi par wS(v)
   b. Partitionner davantage Πi en plusieurs Rσ, tel que la distance entre deux sommets quelconques dans Rσ > 2
   c. Sélectionner le sommet avec le minimum wS(·) de chaque Rσ et l'ajouter à C'
   d. Calculer w'S(uj) = wS(uj) + j - 1

3. Ordonner C' par w'S(·), trouver le maximum k tel que |E(S)| + w'S(Sk) ≤ gf(|S|+k)

4. Retourner |S|+k

Complexité Temporelle : O(|C|³ + |S||C|)

Correction (Théorème 3) :

• Chaque ensemble indépendant Πi peut contribuer au maximum s'i sommets
• Chaque Rσ peut contribuer au maximum 1 sommet en raison de la contrainte à deux sauts
• |E(S*)| ≥ |E(S)| + Σw'S(v^(ij)m) ≥ |E(S)| + Σ^{|S'|} w'S(vj)

Avantages :

• Considère la structure d'ensemble indépendant (réduit la surestimation des arêtes)
• Considère la contrainte à deux sauts (au maximum 1 sommet par Rσ)
• Plus rapide que la relaxation LP, avec des bornes proches

Configuration Expérimentale

Ensemble de Données

• Source : Network Data Repository
• Échelle : 139 graphes non orientés réels
• Plage : jusqu'à 5.87×10⁷ sommets, 1.06×10⁸ arêtes
• Domaines : réseaux sociaux, réseaux biologiques, réseaux de collaboration, réseaux routiers, etc.

Configuration des Fonctions f(·)

1. Quasi-cliques γ : f(i) = γ(i choose 2), γ ∈ {0.99, 0.95, 0.90, 0.85}
   • Fonction non héréditaire
2. Cliques défectueuses s : f(i) = (i choose 2) - s, s ∈ {1, 3}
   • Fonction héréditaire

Algorithmes de Comparaison

1. Deg-BnB : ordonnancement par dégénérescence + séparation et évaluation
2. TwoDeg-BnB : ordonnancement par dégénérescence à deux sauts + séparation et évaluation
3. BnB : séparation et évaluation pure (sans décomposition)
4. MIP : solveur Gurobi + modèle MIP-fD
5. Deg-MIP : décomposition par ordonnancement par dégénérescence + résolution MIP des sous-problèmes
6. TwoDeg-MIP : décomposition par ordonnancement par dégénérescence à deux sauts + résolution MIP des sous-problèmes

Environnement Expérimental

• CPU : Intel Xeon Platinum 8360Y @ 2.40GHz
• Système : Ubuntu 22.04
• Compilation : g++ 9.3.0 avec -Ofast
• Limite de Temps : 3600 secondes (1 heure)
• Code : https://github.com/cy-Luo000/MDSL

Métriques d'Évaluation

• Nombre d'instances résolues à différents points temporels
• Temps d'exécution pour des graphes spécifiques
• Serrage de la borne supérieure (écart par rapport à la solution optimale)
• Nombre de nœuds de l'arbre de recherche

Résultats Expérimentaux

Résultats Principaux

1. Performance Globale (Figures 4 & 5)

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

• TwoDeg-BnB et Deg-BnB surpassent complètement tous les autres algorithmes à tous les points temporels
• En 1 heure, TwoDeg-BnB résout environ 100 instances, BnB seulement 50
• MIP ne peut pratiquement résoudre aucune instance

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

• Après 1000 secondes, TwoDeg-MIP et Deg-MIP ont des performances comparables aux méthodes de séparation et évaluation
• Le cadre de décomposition améliore significativement les performances de MIP

Cliques défectueuses s (s=1, 3) :

• TwoDeg-BnB et Deg-BnB résolvent environ 110 instances
• BnB pur résout environ 60 instances
• La propriété héréditaire avantage davantage les méthodes de séparation et évaluation

Découverte Clé : le cadre de décomposition double le nombre d'instances résolues

2. Résultats Détaillés pour Graphes de Grande Taille (Tableaux 1 & 2)

Cas Remarquables (γ=0.99) :

• web-uk-2005 (129,632 sommets) : TwoDeg-BnB 634 secondes, MIP dépassement de délai
• inf-road-usa (23,947,347 sommets) : TwoDeg-BnB 70 secondes, autres méthodes dépassement de délai
• scc_infect-dublin : Deg-BnB 0.54 secondes, TwoDeg-BnB dépassement de délai (le choix d'ordonnancement affecte)

Effet d'Accélération :

• TwoDeg-BnB est 2-3 ordres de grandeur plus rapide que BnB (par exemple web-indochina-2004 : 0.25 secondes vs dépassement de délai)
• 39 instances résolues par TwoDeg-BnB ou Deg-BnB mais échouées par BnB
• La décomposition + MIP surpasse parfois l'algorithme combinatoire pur (par exemple web-sk-2005)

Cliques Défectueuses (Tableau 2) :

• La propriété héréditaire apporte plus d'élagage
• scc_infect-dublin (s=1) : TwoDeg-BnB 0.83 secondes vs Deg-MIP dépassement de délai
• rec-amazon : TwoDeg-BnB 0.08 secondes vs BnB 264 secondes

Expériences d'Ablation

Analyse de l'Efficacité des Bornes (Tableaux 3 & 4)

Comparaison du Serrage des Bornes :

Relaxation LP > SortBound > Borne Simple

Cas Spécifiques (γ=0.95) :

• ca-CondMat :
  • Optimal : 28
  • LP : 29, Simple : 280, SortBound : 142
  • SortBound atteint un équilibre entre serrage et scalabilité
• inf-roadNet-CA :
  • Optimal : 4
  • LP : impossible à calculer, Simple : 13, SortBound : 5
  • LP échoue sur les grands graphes

Impact sur la Taille de l'Arbre de Recherche :

• inf-roadNet-CA (γ=0.95) :
  • TwoDeg-BnB : 5 secondes, 10 nœuds
  • TwoDeg-BnB/ub (sans SortBound) : 10 secondes, 14,138,820 nœuds
  • Réduction de l'arbre de recherche de 6 ordres de grandeur
• ca-MathSciNet (s=3) :
  • TwoDeg-BnB : 7.62 secondes, 80 nœuds
  • TwoDeg-BnB/ub : 1228 secondes, 256,325,020 nœuds
  • Accélération de 100 fois

Découverte Clé : SortBound maintient le serrage tout en étant scalable jusqu'aux graphes de millions de sommets

Relation entre αG et Temps d'Exécution (Figures 6 & 7)

Observations :

• Près de la moitié des instances ont αG ≤ 1000 (bien inférieur à |V|)
• Le temps d'exécution est positivement corrélé à αG
• L'ordonnancement par dégénérescence à deux sauts produit généralement un αG plus petit

Cas Typique :

• ca-dblp-2010 : |V|=226,413, dG=74, tdG=238, dG·ΔG=17,612
  • L'avantage de l'ordonnancement par dégénérescence à deux sauts est évident

Validation : soutient l'idée de conception de minimiser αG

Analyse de Cas

Exemple d'Effet de Décomposition de Graphe

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

• Degré de dégénérescence : dG=49
• Degré de dégénérescence à deux sauts : tdG=199
• Après décomposition : αG=199 (ordonnancement à deux sauts) vs αG≈2450 (ordonnancement par dégénérescence)
• Performance : TwoDeg-BnB 0.25 secondes vs Deg-BnB 0.18 secondes vs BnB 12.10 secondes

Exemple d'Algorithme de Borne (Figures 2 & 3)

Entrée : 10 sommets, S={v1,v2}, C={v3,...,v10}

Étapes :

1. Partitionner en ensembles indépendants : Π1={v3,v5,v7,v9}, Π2={v4,v6,v8,v10}
2. Calculer wS : wS(v3)=0, wS(v5)=1, wS(v7)=2...
3. Partitionner davantage par distance : R¹₁={v3,v7}, R²₁={v5,v9}, R¹₂={v8,v4}, R²₂={v10,v6}
4. Sélectionner le minimum wS : C'={v3,v5,v8,v10}
5. Calculer w'S : w'S(v3)=0, w'S(v8)=0, w'S(v5)=2, w'S(v10)=2

Résultat :

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

Travaux Connexes

1. Modèles de Relaxation de Clique

• Quasi-cliques γ (Abello et al. 2002) : NP-difficile pour γ∈(0,1]
  • Méthodes MIP (Pattillo et al. 2013a)
  • Séparation et évaluation (Mahdavi Pajouh et al. 2014, Ribeiro & Riveaux 2019)
• Cliques défectueuses s (Yu et al. 2006) : NP-difficile pour s≥1
  • Contrainte de faible diamètre (Luo et al. 2024) : O(nc·1.2ⁿ)
  • Séparation et évaluation (Chen et al. 2021b, Gao et al. 2022, Chang 2023)
• s-plex moyen (Veremyev et al. 2016)

2. Graphes f(·)-denses Génériques

• Veremyev et al. 2016 :
  • Proposent plusieurs modèles MIP (GF3 optimal)
  • Ne considèrent pas les contraintes de faible diamètre
• Résultats de Complexité (Asahiro et al. 2002) :
  • NP-difficile quand f(n)=Θ(n^(1+ε)) ou f(n)=n+Ω(n^ε)
  • Polynomial quand f(n)=n+c

3. Problème de 2-club

• Définition : sous-graphe avec diamètre ≤ 2
• Méthodes MIP (Pajouh et al. 2016, Lu et al. 2022)
• Séparation et évaluation (Hartung et al. 2012, Komusiewicz et al. 2019)
• Contribution de cet Article : première combinaison de 2-club avec contrainte f(·)-dense

4. Contraintes de Connectivité

• Santos et al. 2024 : quasi-cliques γ connexes basées sur arbres couvrants
• Avantage de cet Article : la contrainte de diamètre est plus forte que la simple connectivité

5. Techniques de Décomposition de Graphe

• Ordonnancement par Dégénérescence (Matula & Beck 1983) : O(|V|+|E|)
• Dégénérescence à Deux Sauts (Wünsche 2021) : première utilisation pour k-plex et k-club
• Innovation de cet Article : application systématique aux graphes f(·)-denses génériques

Conclusion et Discussion

Conclusions Principales

1. Contributions Théoriques :
   • Cadre théorique systématisé pour les graphes f(·)-denses
   • Preuve des conditions nécessaires et suffisantes pour la propriété héréditaire
   • Analyse de correction et de complexité pour le cadre de décomposition
2. Contributions Algorithmiques :
   • Cadre de décomposition décomposant le problème en n sous-problèmes indépendants
   • Ordonnancement par dégénérescence à deux sauts contrôlant efficacement la taille des sous-graphes
   • Borne d'ordonnancement atteignant un équilibre entre serrage et efficacité
3. Vérification Expérimentale :
   • Nombre d'instances résolues doublé sur 139 graphes réels
   • Scalabilité jusqu'aux graphes de dizaines de millions de sommets
   • Borne d'ordonnancement réduisant l'arbre de recherche de 6 ordres de grandeur

Limitations

1. Limitations Algorithmiques :
   • Toujours un algorithme en temps exponentiel (O(2^αG))
   • Pour les graphes denses, αG peut approcher |V|
   • Difficile de prédire à l'avance quelle stratégie d'ordonnancement est meilleure
2. Limitations du Modèle :
   • La contrainte de diamètre=2 peut être trop stricte
   • Ne considère pas les poids de sommets ou d'arêtes
   • f(·) doit satisfaire des conditions spécifiques pour avoir la propriété héréditaire
3. Limitations Expérimentales :
   • Seulement deux fonctions f(·) testées
   • Pas de comparaison directe avec tous les travaux connexes
   • Manque de tests sur les graphes ultra-massifs (centaines de millions de sommets)

Directions Futures

1. Extensions Algorithmiques :
   • Parallélisation du cadre de décomposition (sous-graphes indépendants peuvent être traités en parallèle)
   • Extension à d'autres contraintes de diamètre (k-club, k≥3)
   • Combinaison avec d'autres contraintes structurelles (connectivité de sommets)
2. Approfondissement Théorique :
   • Analyse de la propriété héréditaire pour plus de fonctions f(·)
   • Étude de la complexité paramétrée
   • Conception d'algorithmes d'approximation
3. Extensions d'Application :
   • Algorithmes incrémentaux pour graphes dynamiques
   • Extension aux graphes pondérés
   • Modèles spécifiques au domaine (par exemple réseaux biologiques)

Évaluation Approfondie

Points Forts

1. Rigueur Théorique :
   • Preuves mathématiques complètes (Annexe A)
   • Analyse de complexité claire
   • Conditions nécessaires et suffisantes pour la propriété héréditaire (Lemmes 1 & 2)
2. Innovation Algorithmique :
   • Cadre de Décomposition : le Lemme 3 décompose élégamment le problème global en problèmes locaux
   • Ordonnancement par Dégénérescence à Deux Sauts : stratégie d'ordonnancement innovante adaptée aux contraintes de diamètre
   • Borne d'Ordonnancement : conception sophistiquée avec partitionnement imbriqué (ensembles indépendants + contraintes de distance)
3. Complétude Expérimentale :
   • 139 graphes réels, 6 algorithmes, 2 classes de fonctions f(·)
   • Expériences d'ablation détaillées (Tableaux 3 & 4)
   • Analyse de visualisation (Figures 6 & 7)
   • Code open-source garantissant la reproductibilité
4. Valeur Pratique :
   • Scalabilité jusqu'aux dizaines de millions de sommets
   • Plusieurs ordres de grandeur plus rapide que MIP
   • Cadre générique applicable à plusieurs modèles de relaxation de clique
5. Clarté de Rédaction :
   • Motivation claire dans l'introduction (Figure 1 intuitive)
   • Pseudocode algorithmique détaillé
   • Preuves de théorèmes complètes

Insuffisances

1. Choix de Stratégie d'Ordonnancement :
   • Manque de guidance théorique sur quand utiliser dégénérescence vs dégénérescence à deux sauts
   • Le Tableau 1 montre que parfois Deg-BnB est plus rapide (par exemple scc_infect-dublin)
   • Suggestion : concevoir une stratégie adaptative ou fournir une heuristique de sélection
2. Complexité de l'Algorithme de Borne :
   • O(|C|³) peut devenir un goulot d'étranglement
   • La coloration gloutonne n'est pas optimale
   • Direction d'amélioration : utiliser des algorithmes de coloration plus rapides ou relâcher l'optimalité
3. Comparaison Expérimentale :
   • Pas de comparaison avec la méthode d'arbre couvrant de Santos et al. 2024
   • Manque de comparaison avec les algorithmes optimaux pour des problèmes spécifiques (par exemple l'algorithme de Chang 2023 pour les cliques défectueuses)
   • Le modèle MIP pourrait avoir de l'espace pour amélioration (par exemple ajouter des inégalités valides)
4. Analyse de Scalabilité :
   • Discussion insuffisante pour les cas où αG>10,000
   • Performance sur graphes denses insuffisamment testée
   • Analyse de consommation mémoire manquante
5. Vides Théoriques :
   • Pas d'analyse du ratio d'approximation
   • Complexité paramétrée (par exemple avec αG comme paramètre) non discutée
   • Complexité en cas moyen non analysée

Impact

1. Contribution Académique :
   • Cadre théorique unifiant plusieurs modèles de relaxation de clique
   • Techniques de décomposition transférables à d'autres problèmes d'extraction de sous-graphes
   • Valeur de citation élevée (combinaison de problèmes NP-difficiles, décomposition de graphe, séparation et évaluation)
2. Valeur Pratique :
   • Application directe en découverte de communautés, bioinformatique, etc.
   • Code open-source facilitant le transfert technologique
   • Peut servir de baseline pour d'autres algorithmes
3. Reproductibilité :
   • Description d'algorithmes détaillée
   • Code open-source (https://github.com/cy-Luo000/MDSL)
   • Ensemble de données public (Network Data Repository)
   • Configuration expérimentale claire
4. Limitations :
   • Les applications industrielles nécessitent une optimisation supplémentaire (par exemple parallélisation)
   • Les algorithmes dédiés pour des f(·) spécifiques peuvent être plus performants
   • Nécessite une validation supplémentaire par des experts du domaine

Scénarios Applicables

Scénarios Recommandés :

1. Analyse de Réseaux Sociaux : identification de communautés densément connectées (diamètre ≤ 2 garantit une communication rapide)
2. Réseaux Biologiques : identification de complexes protéiques (permet quelques arêtes manquantes)
3. Réseaux de Collaboration : identification d'équipes de recherche principales
4. Graphes de Taille Moyenne : |V|<10⁶, αG<5000 pour performance optimale

Scénarios Non Recommandés :

1. Graphes Ultra-Denses de Grande Taille : αG approchant |V| causant explosion exponentielle
2. Applications Temps Réel : le pire cas nécessite toujours un temps exponentiel
3. Scénarios où l'Approximation Suffit : le coût des algorithmes exacts est élevé

Suggestions d'Amélioration :

1. Combiner avec des algorithmes heuristiques pour fournir rapidement des solutions approchées
2. Paralléliser le traitement des graphes ultra-massifs
3. Concevoir des algorithmes spécialisés pour des f(·) spécifiques

Références

Travaux Connexes Principaux

1. Veremyev et al. (2016) : "Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs" - Propose le modèle MIP GF3
2. Luo et al. (2024) : "A faster branching algorithm for the maximum k-defective clique problem" - ECAI 2024, algorithme O(nc·1.2ⁿ)
3. Chang (2023) : "Efficient maximum k-defective clique computation with improved time complexity" - PACMMOD, séparation et évaluation améliorée
4. Santos et al. (2024) : "Ensuring connectedness for the maximum quasi-clique and densest k-subgraph problems" - Contraintes de connectivité par arbre couvrant
5. Wünsche (2021) : "Mind the gap when searching for relaxed cliques" - Première proposition d'ordonnancement par dégénérescence à deux sauts

Fondements Théoriques

6. Matula & Beck (1983) : "Smallest-last ordering and clustering and graph coloring algorithms" - Travail classique sur l'ordonnancement par dégénérescence
7. Asahiro et al. (2002) : "Complexity of finding dense subgraphs" - Résultats de complexité pour graphes f(·)-denses
8. Downey & Fellows (2012) : "Parameterized complexity" - Théorie de la W1-difficulté

Évaluation Globale : Ceci est un excellent article avec une rigueur théorique, une innovation algorithmique et une vérification expérimentale complètes. Le cadre de décomposition et la méthode de borne d'ordonnancement possèdent une généralité et une valeur pratique élevées. Les contributions principales résident dans l'unification de plusieurs modèles de relaxation de clique et la fourniture d'algorithmes de résolution efficaces. Recommandation : acceptation, avec des contributions importantes aux domaines des algorithmes de graphe et de l'analyse de réseaux.