2025-11-12T01:55:30.485107

A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems

Zhou, Luo, Wang et al.
A graph with $n$ vertices is an $f(\cdot)$-dense graph if it has at least $f(n)$ edges, $f(\cdot)$ being a well-defined function. The notion $f(\cdot)$-dense graph encompasses various clique models like $γ$-quasi cliques, $k$-defective cliques, and dense cliques, arising in cohesive subgraph extraction applications. However, the $f(\cdot)$-dense graph may be disconnected or weakly connected. To conquer this, we study the problem of finding the largest $f(\cdot)$-dense subgraph with a diameter of at most two in the paper. Specifically, we present a decomposition-based branch-and-bound algorithm to optimally solve this problem. The key feature of the algorithm is a decomposition framework that breaks the graph into $n$ smaller subgraphs, allowing independent searches in each subgraph. We also introduce decomposition strategies including degeneracy and two-hop degeneracy orderings, alongside a branch-and-bound algorithm with a novel sorting-based upper bound to solve each subproblem. Worst-case complexity for each component is provided. Empirical results on 139 real-world graphs under two $f(\cdot)$ functions show our algorithm outperforms the MIP solver and pure branch-and-bound, solving nearly twice as many instances optimally within one hour.
academic

अधिकतम निम्न-व्यास सघन उपग्राफ समस्याओं के लिए एक शाखा-और-सीमा दृष्टिकोण

मूल जानकारी

  • पेपर 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 शेनझेन)
  • वर्गीकरण: cs.DS (डेटा संरचनाएं और एल्गोरिदम)
  • प्रकाशन तिथि: 6 नवंबर 2025 (arXiv v2)
  • पेपर लिंक: https://arxiv.org/abs/2511.03157v2

सारांश

यह पेपर अधिकतम निम्न-व्यास f(·)-सघन उपग्राफ समस्या (MfDS) का अध्ययन करता है। f(·)-सघन ग्राफ एक ऐसा ग्राफ है जिसमें n शीर्ष हैं और कम से कम f(n) किनारे हैं, जहां f(·) एक सुपरिभाषित फलन है। यह अवधारणा γ-अर्ध-समूह, k-त्रुटिपूर्ण समूह और सघन समूह जैसे कई समूह शिथिलीकरण मॉडल को शामिल करती है। हालांकि, f(·)-सघन ग्राफ असंयुक्त या कमजोर रूप से संयुक्त हो सकते हैं। इस समस्या को हल करने के लिए, यह पेपर व्यास 2 से अधिक न होने वाले अधिकतम f(·)-सघन उपग्राफ खोजने का अध्ययन करता है। विशेष रूप से, एक विघटन-आधारित शाखा-और-सीमा एल्गोरिदम प्रस्तावित किया गया है जो इस समस्या को इष्टतम रूप से हल करता है। एल्गोरिदम की मुख्य विशेषता ग्राफ को n छोटे उपग्राफ में विघटित करना है, जो प्रत्येक उपग्राफ में स्वतंत्र खोज की अनुमति देता है। पेपर विघटन रणनीतियों जैसे अपघटन क्रमण और दो-हॉप अपघटन क्रमण, साथ ही नवीन क्रमण ऊपरी सीमा के साथ शाखा-और-सीमा एल्गोरिदम भी प्रस्तुत करता है। 139 वास्तविक ग्राफ पर प्रायोगिक परिणाम दर्शाते हैं कि यह एल्गोरिदम MIP सॉल्वर और शुद्ध शाखा-और-सीमा विधियों से बेहतर है, एक घंटे में इष्टतम रूप से हल किए गए उदाहरणों की संख्या लगभग दोगुनी है।

अनुसंधान पृष्ठभूमि और प्रेरणा

1. समस्या को हल करने के लिए

नेटवर्क विश्लेषण में, कसकर जुड़े हुए उपग्राफ (cohesive subgraph) की पहचान करना एक मूल कार्य है, जो सामुदायिक खोज, प्रोटीन परिसर पहचान, वित्तीय नेटवर्क विश्लेषण आदि क्षेत्रों में लागू होता है। शास्त्रीय समूह (clique) मॉडल सभी शीर्ष जोड़ों के बीच किनारे की आवश्यकता करता है, लेकिन यह आवश्यकता बहुत कठोर है, विशेष रूप से शोर और त्रुटियों वाले व्यावहारिक अनुप्रयोगों में। इसलिए, कई शिथिलीकृत समूह मॉडल सामने आए हैं, जैसे:

  • γ-अर्ध-समूह: 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) मौजूद हैं, लेकिन बड़े पैमाने के ग्राफ के लिए अक्षम हैं, और निम्न-व्यास बाधा के लिए कोई MIP मॉडल नहीं है
  • शाखा-और-सीमा विधि: विशिष्ट समस्याओं (जैसे अधिकतम 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(·) की गणना oracle (स्थिर समय)

आउटपुट: अधिकतम शीर्ष समुच्चय 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, Gi में vi युक्त अधिकतम निम्न-व्यास f(·)-सघन उपग्राफ है, तो: **ω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 का {vi,...,vn} प्रेरित उपग्राफ में डिग्री ≤ k है
  • गणना: peel एल्गोरिदम का उपयोग करें, O(|V|+|E|) समय, बार-बार न्यूनतम डिग्री शीर्ष हटाएं
  • अपघटन डिग्री dG: न्यूनतम k मान

अनुमानी प्रवाह:

1. अपघटन क्रमण ⟨v1,...,vn⟩ की गणना करें
2. प्रत्येक vi के लिए:
   - Si ← {vi} ∪ {NG(vi) ∩ {vi+1,...,vn}}
   - Gi ← G[Si] (व्यास ≤ 2)
   - जबकि |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 का {vi,...,vn} में दो-हॉप पड़ोसी संख्या ≤ k है
  • गणना: 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. C से यादृच्छिक रूप से u चुनें
  
  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 शिथिलता से तेज, सीमा समीप

प्रायोगिक सेटअप

डेटासेट

  • स्रोत: नेटवर्क डेटा रिपॉजिटरी
  • स्केल: 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 with -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): γ∈(0,1] के लिए NP-कठिन
    • MIP विधि (Pattillo et al. 2013a)
    • शाखा-और-सीमा (Mahdavi Pajouh et al. 2014, Ribeiro & Riveaux 2019)
  • s-त्रुटिपूर्ण समूह (Yu et al. 2006): s≥1 के लिए NP-कठिन
    • निम्न-व्यास बाधा (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):
    • f(n)=Θ(n^(1+ε)) या f(n)=n+Ω(n^ε) होने पर NP-कठिन
    • 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 मॉडल में सुधार की गुंजाइश (जैसे वैध असमानताएं जोड़ना)
  1. स्केलेबिलिटी विश्लेषण:
    • αG>10,000 के मामलों पर चर्चा अपर्याप्त
    • सघन ग्राफ प्रदर्शन पूरी तरह परीक्षित नहीं
    • मेमोरी खपत विश्लेषण की कमी
  2. सैद्धांतिक अंतराल:
    • अनुमानित अनुपात विश्लेषण प्रदान नहीं किया
    • पैरामीटरीकृत जटिलता (जैसे αG को पैरामीटर के रूप में) पर चर्चा नहीं
    • औसत स्थिति जटिलता विश्लेषित नहीं

प्रभाव

  1. शैक्षणिक योगदान:
    • कई समूह शिथिलीकरण मॉडलों के लिए एकीकृत सैद्धांतिक ढांचा
    • विघटन तकनीक अन्य उपग्राफ निष्कर्षण समस्याओं में स्थानांतरणीय
    • उद्धरण मूल्य उच्च (NP-कठिन समस्या, ग्राफ विघटन, शाखा-और-सीमा को जोड़ता है)
  2. व्यावहारिक मूल्य:
    • सामुदायिक खोज, जैव सूचना विज्ञान आदि क्षेत्रों में सीधा अनुप्रयोग
    • खुला स्रोत कोड तकनीक रूपांतरण को बढ़ावा देता है
    • अन्य एल्गोरिदम के लिए baseline के रूप में काम कर सकता है
  3. पुनरुत्पादनीयता:
    • एल्गोरिदम विवरण विस्तृत
    • कोड खुला स्रोत (https://github.com/cy-Luo000/MDSL)
    • डेटासेट सार्वजनिक (नेटवर्क डेटा रिपॉजिटरी)
    • प्रायोगिक सेटअप स्पष्ट
  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" - GF3 MIP मॉडल प्रस्तावित
  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" - पहली बार दो-हॉप अपघटन क्रमण प्रस्तावित

सैद्धांतिक आधार

  1. Matula & Beck (1983): "Smallest-last ordering and clustering and graph coloring algorithms" - अपघटन क्रमण का शास्त्रीय कार्य
  2. Asahiro et al. (2002): "Complexity of finding dense subgraphs" - f(·)-सघन ग्राफ जटिलता परिणाम
  3. Downey & Fellows (2012): "Parameterized complexity" - W1-hardness सिद्धांत

समग्र मूल्यांकन: यह एक सैद्धांतिक रूप से कठोर, एल्गोरिदमिक रूप से नवीन, और प्रायोगिक रूप से व्यापक उत्कृष्ट पेपर है। विघटन ढांचा और क्रमण ऊपरी सीमा विधि उच्च सामान्यता और व्यावहारिक मूल्य रखते हैं। मुख्य योगदान कई समूह शिथिलीकरण मॉडलों को एकीकृत करना और कुशल समाधान एल्गोरिदम प्रदान करना है। स्वीकृति की अनुशंसा की जाती है, ग्राफ एल्गोरिदम और नेटवर्क विश्लेषण क्षेत्र में महत्वपूर्ण योगदान है।