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
শিরোনাম: সর্বোচ্চ নিম্ন-ব্যাস ঘন উপগ্রাফ সমস্যার জন্য একটি শাখা-এবং-সীমাবদ্ধতা পদ্ধতি
লেখক: Yi Zhou (ইলেকট্রনিক্স বিজ্ঞান ও প্রযুক্তি বিশ্ববিদ্যালয়, চীন), Chunyu Luo (ইলেকট্রনিক্স বিজ্ঞান ও প্রযুক্তি বিশ্ববিদ্যালয়, চীন), Zhengren Wang (পিকিং বিশ্ববিদ্যালয়), Zhang-Hua Fu (শেনজেন কৃত্রিম বুদ্ধিমত্তা এবং রোবোটিক্স সমাজ ইনস্টিটিউট, CUHK শেনজেন)
শ্রেণীবিভাগ: cs.DS (ডেটা কাঠামো এবং অ্যালগরিদম)
প্রকাশনার সময়: ২০২৫ সালের নভেম্বর ৬ (arXiv v2)
কাগজের লিঙ্ক: https://arxiv.org/abs/2511.03157v2

সারসংক্ষেপ

এই কাগজটি সর্বোচ্চ নিম্ন-ব্যাস f(·)-ঘন উপগ্রাফ সমস্যা (MfDS) অধ্যয়ন করে। f(·)-ঘন গ্রাফ হল এমন একটি গ্রাফ যার n টি শীর্ষবিন্দু এবং কমপক্ষে f(n) টি প্রান্ত রয়েছে, যেখানে f(·) একটি সুসংজ্ঞায়িত ফাংশন। এই ধারণাটি γ-কোয়াসি-ক্লিক, k-ত্রুটিপূর্ণ ক্লিক এবং ঘন ক্লিক সহ বিভিন্ন ক্লিক শিথিলকরণ মডেল অন্তর্ভুক্ত করে। তবে, f(·)-ঘন গ্রাফগুলি সংযুক্ত নাও হতে পারে বা দুর্বলভাবে সংযুক্ত হতে পারে। এই সমস্যা সমাধানের জন্য, এই কাগজটি ব্যাস ২ এর বেশি নয় এমন সর্বোচ্চ f(·)-ঘন উপগ্রাফ খুঁজে পাওয়ার অধ্যয়ন করে। বিশেষভাবে, এটি সর্বোত্তম সমাধানের জন্য একটি বিয়োজন-ভিত্তিক শাখা-এবং-সীমাবদ্ধতা অ্যালগরিদম প্রস্তাব করে। অ্যালগরিদমের মূল বৈশিষ্ট্য হল গ্রাফটিকে n টি ছোট উপগ্রাফে বিয়োজন করা, যা প্রতিটি উপগ্রাফে স্বাধীন অনুসন্ধানের অনুমতি দেয়। কাগজটি অবক্ষয় ক্রম এবং দুই-হপ অবক্ষয় ক্রম সহ বিয়োজন কৌশল এবং নতুন ক্রম সীমাবদ্ধতা সহ শাখা-এবং-সীমাবদ্ধতা অ্যালগরিদম প্রবর্তন করে। ১৩৯টি বাস্তব গ্রাফে পরীক্ষার ফলাফল দেখায় যে অ্যালগরিদমটি MIP সমাধানকারী এবং বিশুদ্ধ শাখা-এবং-সীমাবদ্ধতা পদ্ধতির চেয়ে উন্নত, এক ঘণ্টার মধ্যে সর্বোত্তম সমাধান করা উদাহরণের সংখ্যা প্রায় দ্বিগুণ।

গবেষণা পটভূমি এবং প্রেরণা

১. সমাধান করার সমস্যা

নেটওয়ার্ক বিশ্লেষণে, ঘনিষ্ঠভাবে সংযুক্ত উপগ্রাফ (cohesive subgraph) চিহ্নিত করা একটি মূল কাজ, যা সম্প্রদায় আবিষ্কার, প্রোটিন জটিল সনাক্তকরণ, আর্থিক নেটওয়ার্ক বিশ্লেষণ এবং অন্যান্য ক্ষেত্রে প্রয়োগ করা হয়। ক্লাসিক ক্লিক (clique) মডেল সমস্ত শীর্ষবিন্দু জোড়ার মধ্যে প্রান্ত থাকার দাবি করে, কিন্তু এই প্রয়োজনীয়তা অত্যন্ত কঠোর, বিশেষত শব্দ এবং ত্রুটি সহ বাস্তব প্রয়োগে। অতএব, বিভিন্ন শিথিল ক্লিক মডেল উপস্থিত হয়েছে, যেমন:

γ-কোয়াসি-ক্লিক: n টি শীর্ষবিন্দুর প্রেরিত উপগ্রাফে কমপক্ষে γ(n choose 2) টি প্রান্ত রয়েছে
s-ত্রুটিপূর্ণ ক্লিক: কমপক্ষে (n choose 2) - s টি প্রান্ত রয়েছে
গড় s-plex: কমপক্ষে n(n-s)/2 টি প্রান্ত রয়েছে

এই মডেলগুলি f(·)-ঘন গ্রাফ হিসাবে একীভূত করা যেতে পারে: n টি শীর্ষবিন্দুর গ্রাফে কমপক্ষে f(n) টি প্রান্ত রয়েছে।

২. সমস্যার গুরুত্ব

বিদ্যমান f(·)-ঘন গ্রাফ মডেলগুলির গুরুতর ত্রুটি রয়েছে: সংযুক্ত নাও হতে পারে বা সংযোগ খুবই দুর্বল হতে পারে। কাগজটি চিত্র ১ এর মাধ্যমে দুটি উদাহরণ প্রদর্শন করে:

G1: ২০০ টি শীর্ষবিন্দুর ক্লিক এবং ১০ টি শীর্ষবিন্দুর পথ, v1 থেকে v210 পর্যন্ত ১০ হপ প্রয়োজন
G2: ২০০ টি শীর্ষবিন্দুর ক্লিক এবং ১০ টি বিচ্ছিন্ন শীর্ষবিন্দু, v1 এবং v210 এর মধ্যে কোন পথ নেই

এই দুটি গ্রাফই f(n)=0.9(n choose 2) এর ঘনত্ব প্রয়োজনীয়তা পূরণ করে, কিন্তু স্পষ্টতই ঘনিষ্ঠভাবে সংযুক্ত সম্প্রদায় নয়।

৩. বিদ্যমান পদ্ধতির সীমাবদ্ধতা

MIP পদ্ধতি: যদিও নির্দিষ্ট f(·) ফাংশনের জন্য মিশ্র পূর্ণসংখ্যা প্রোগ্রামিং মডেল বিদ্যমান (যেমন GF3), তবে বড় আকারের গ্রাফের জন্য অদক্ষ, এবং নিম্ন-ব্যাস সীমাবদ্ধতার জন্য কোন MIP মডেল নেই
শাখা-এবং-সীমাবদ্ধতা পদ্ধতি: নির্দিষ্ট সমস্যার জন্য অ্যালগরিদম বিদ্যমান (যেমন সর্বোচ্চ s-ত্রুটিপূর্ণ ক্লিক, সর্বোচ্চ γ-কোয়াসি-ক্লিক), কিন্তু সর্বজনীন f(·)-ঘন গ্রাফ সমাধান কাঠামোর অভাব রয়েছে
সংযোগ সীমাবদ্ধতা: Santos et al. (2024) স্প্যানিং ট্রি-ভিত্তিক সংযোগ সীমাবদ্ধতা প্রস্তাব করেছে, কিন্তু ব্যাস সীমাবদ্ধতা ঘনিষ্ঠ সংযোগ নিশ্চিত করতে আরও ভাল

৪. গবেষণা প্রেরণা

এই কাগজটি নিম্ন-ব্যাস f(·)-ঘন গ্রাফ ধারণা প্রবর্তন করে: গ্রাফটি সংযুক্ত হওয়ার, কমপক্ষে f(n) টি প্রান্ত থাকার এবং ব্যাস ২ এর বেশি না হওয়ার প্রয়োজন। ব্যাস ২ এর সীমাবদ্ধতা (2-club হিসাবে পরিচিত) নিশ্চিত করে যে যেকোনো দুটি শীর্ষবিন্দুর মধ্যে সর্বনিম্ন পথ ২ এর বেশি নয়, শক্তিশালী সংযোগ নিশ্চিত করে। কাগজটি এই NP-কঠিন সমস্যা সমাধানের জন্য দক্ষ নির্ভুল অ্যালগরিদম ডিজাইন করার লক্ষ্য রাখে।

মূল অবদান

১. সমস্যা আনুষ্ঠানিকীকরণ:

প্রথমবারের মতো f(·)-ঘন গ্রাফ এবং এর উত্তরাধিকার সম্পত্তি (hereditary property) সিস্টেমেটিকভাবে সংজ্ঞায়িত করা
সর্বোচ্চ নিম্ন-ব্যাস f(·)-ঘন উপগ্রাফ সমস্যা (MfDS) আনুষ্ঠানিকীকরণ
MIP-fD মিশ্র পূর্ণসংখ্যা রৈখিক প্রোগ্রামিং মডেল প্রদান

२. অ্যালগরিদম কাঠামো:

গ্রাফ বিয়োজনের উপর ভিত্তি করে প্রাক-প্রক্রিয়াকরণ কাঠামো প্রস্তাব করা, ইনপুট গ্রাফকে n টি ছোট উপগ্রাফে বিয়োজন করা
দুটি বিয়োজন কৌশল প্রবর্তন: অবক্ষয় ক্রম (degeneracy ordering) এবং দুই-হপ অবক্ষয় ক্রম (two-hop degeneracy ordering)
নতুন ক্রম সীমাবদ্ধতা সহ শাখা-এবং-সীমাবদ্ধতা অ্যালগরিদম ডিজাইন করা
বিভিন্ন উপাদান এবং সামগ্রিক অ্যালগরিদমের সর্বোচ্চ ক্ষেত্রে জটিলতা বিশ্লেষণ প্রদান

३. পরীক্ষামূলক যাচাইকরণ:

১৩৯টি বাস্তব গ্রাফে দুটি f(·) ফাংশন (γ-কোয়াসি-ক্লিক এবং s-ত্রুটিপূর্ণ ক্লিক) পরীক্ষা করা
বিয়োজন কাঠামো কর্মক্ষমতা উল্লেখযোগ্যভাবে উন্নত করে প্রমাণ করা, এক ঘণ্টায় সমাধান করা উদাহরণের সংখ্যা বিশুদ্ধ শাখা-এবং-সীমাবদ্ধতার দ্বিগুণ
ক্রম সীমাবদ্ধতা পদ্ধতি অনুসন্ধান গাছের আকার উল্লেখযোগ্যভাবে হ্রাস করে প্রদর্শন করা

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

ইনপুট:

নির্দেশনাহীন সরল গ্রাফ G=(V,E)
ঘনত্ব ফাংশন f: ℤ≥0 → ℝ, যা f(i) ≤ (i choose 2) সন্তুষ্ট করে
f(·) এর গণনা oracle (ধ্রুবক সময়)

আউটপুট: সর্বোচ্চ শীর্ষবিন্দু সেট S⊆V, যেমন:

|E(S)| ≥ f(|S|) (f(·)-ঘনত্ব)
diam(GS) ≤ 2 (নিম্ন-ব্যাস সীমাবদ্ধতা)

উদ্দেশ্য: ωf(G) = max{|S| : S⊆V, |E(S)|≥f(|S|), diam(GS)≤2}

জটিলতা: NP-কঠিন, W1-কঠিন, বহুপদ সময় অনুমান করা কঠিন (কারণ সর্বোচ্চ ক্লিক একটি বিশেষ ক্ষেত্র)

মূল অ্যালগরিদম কাঠামো

১. সামগ্রিক বিয়োজন কাঠামো (অ্যালগরিদম ১)

মূল লেম্মা (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|)**

অ্যালগরিদম প্রবাহ:

১. হিউরিস্টিক অ্যালগরিদম দিয়ে প্রাথমিক সমাধান S পান (নিম্ন সীমা)
२. ক্রম অ্যালগরিদম দিয়ে শীর্ষবিন্দু ক্রম π নির্ধারণ করুন
३. প্রতিটি vi এর জন্য π তে:
   - উপগ্রাফ Gi = G[Vi] তৈরি করুন
   - ExactSearch(Gi, f(·), {vi}, N^(2)_G(vi), lb) দিয়ে সমাধান করুন
४. সমস্ত উপ-সমস্যার সর্বোচ্চ সমাধান ফেরত দিন

সময় জটিলতা: O(Theur(G) + Torder(G) + poly(αG)2^αG)

αG = max(|V1|,...,|Vn|): সর্বোচ্চ উপগ্রাফ আকার
মূল বিষয় হল αG নিয়ন্ত্রণ করতে সূচক অংশ কমানো

२. দক্ষ হিউরিস্টিক অ্যালগরিদম (অ্যালগরিদম २)

অবক্ষয় ক্রম (degeneracy ordering) এর উপর ভিত্তি করে:

সংজ্ঞা: k-অবক্ষয় ক্রম হল শীর্ষবিন্দু ক্রম ⟨v1,...,vn⟩, যেমন প্রতিটি vi এর {vi,...,vn} প্রেরিত উপগ্রাফে ডিগ্রি ≤ k
গণনা: peel অ্যালগরিদম ব্যবহার করুন, O(|V|+|E|) সময়, বারবার সর্বনিম্ন ডিগ্রি শীর্ষবিন্দু মুছে ফেলুন
অবক্ষয় ডিগ্রি dG: সর্বনিম্ন k মান

হিউরিস্টিক প্রবাহ:

१. অবক্ষয় ক্রম ⟨v1,...,vn⟩ গণনা করুন
२. প্রতিটি vi এর জন্য:
   - Si ← {vi} ∪ {NG(vi) ∩ {vi+1,...,vn}}
   - Gi ← G[Si] (ব্যাস ≤ २)
   - যখন |Ei| < f(|Si|):
       Gi তে সর্বনিম্ন ডিগ্রি শীর্ষবিন্দু মুছে ফেলুন
   - সর্বোত্তম সমাধান S* আপডেট করুন
३. S* ফেরত দিন

সময় জটিলতা: O(|E| + |V|d²G)

বাস্তব গ্রাফে dG << |V| (যেমন ca-dblp-2010: dG=74, |V|=226413)

३. শীর্ষবিন্দু ক্রম কৌশল

পরিকল্পনা १: অবক্ষয় ক্রম

সুবিধা: 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

পরিকল্পনা २: দুই-হপ অবক্ষয় ক্রম (অ্যালগরিদম ३)

সংজ্ঞা: 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)

শাখা-এবং-সীমাবদ্ধতা অ্যালগরিদম (অ্যালগরিদম ४)

মূল কাঠামো

BranchBound(G, S, C, lb):
  ইনপুট: গ্রাফ G, বর্তমান সমাধান S, প্রার্থী সেট C, নিম্ন সীমা lb
  
  १. যদি G[S] সম্ভাব্য সমাধান এবং |S|>lb: lb এবং সর্বোত্তম সমাধান আপডেট করুন
  
  २. যদি f(·) উত্তরাধিকার এবং |E(S)|<f(|S|): প্রুন করে ফেরত দিন
  
  ३. UB ← SortBound(G, f(·), S, C)  // সীমা গণনা করুন
  
  ४. যদি UB ≤ lb: প্রুন করে ফেরত দিন
  
  ५. যদি f(·) উত্তরাধিকার: হ্রাস নিয়ম প্রয়োগ করুন (Lemma 5)
  
  ६. র্যান্ডমলি u∈C নির্বাচন করুন
  
  ७. যদি Lemma 4 এর শর্ত পূরণ করে: শুধুমাত্র S∪{u} শাখায় পুনরাবৃত্তি করুন
     অন্যথায়: দুটি শাখা S∪{u} এবং S তে পুনরাবৃত্তি করুন

হ্রাস নিয়ম (Lemma 4 & 5)

Lemma 4 (সর্বজনীন হ্রাস): যদি u∈C সন্তুষ্ট করে: १. |NG(u)| = |V|-1, বা २. |NG(u)| = |V|-२ এবং GS∪{u} সম্ভাব্য

তাহলে u ধারণকারী সর্বোত্তম সমাধান বিদ্যমান → শুধুমাত্র u ধারণকারী শাখা অনুসন্ধান করুন

Lemma 5 (উত্তরাধিকার ফাংশন হ্রাস): যদি f(·) উত্তরাধিকার হয়: १. যদি |E(S)| < f(|S|), তাহলে S ধারণকারী কোন সম্ভাব্য সমাধান নেই २. যদি v∈C যেমন |E(S∪{v})| < f(|S|+१), তাহলে v ধারণকারী কোন সম্ভাব্য সমাধান নেই

ক্রম সীমাবদ্ধতা অ্যালগরিদম (অ্যালগরিদম ५)

সরল সীমা (অংশ 4.6.1)

v∈C এর জন্য, সংজ্ঞায়িত করুন wS(v) = |S\N(v)| (S তে v এর অ-প্রতিবেশী সংখ্যা) १. wS(v) অ-হ্রাসমান ক্রমে C সাজান ⟨v1,...,v|C|⟩ পান २. সর্বোচ্চ k খুঁজুন যেমন wS(Sk) + |E(S)| ≤ gf(|S|+k), যেখানে gf(n)=(n choose 2)-f(n) ३. |S|+k ফেরত দিন

সঠিকতা (Lemma 6): wS(S') + |E(S)| |E(S∪S')| এর নিম্ন অনুমান

উন্নত ক্রম সীমা (SortBound)

মূল ধারণা: १. সরল সীমা S এবং C এর মধ্যে প্রান্ত উপেক্ষা করে २. সরল সীমা দুই-হপ সীমাবদ্ধতা বিবেচনা করে না

অ্যালগরিদম প্রবাহ:

१. লোভী অ্যালগরিদম ব্যবহার করে C কে χ স্বাধীন সেটে বিভক্ত করুন Π1,...,Πχ
   (χ কমিয়ে আনুন ≈ গ্রাফ রঙ সমস্যা, O(|C|³) লোভী ব্যবহার করুন)

२. প্রতিটি Πi এর জন্য:
   a. wS(v) ক্রমে Πi সাজান
   b. আরও Πi কে একাধিক Rσ তে বিভক্ত করুন, যেমন Rσ তে যেকোনো দুটি শীর্ষবিন্দুর দূরত্ব >२
   c. প্রতিটি Rσ থেকে wS(·) সর্বনিম্ন শীর্ষবিন্দু নির্বাচন করে C' তে যোগ করুন
   d. w'S(uj) = wS(uj) + j - १ গণনা করুন

३. w'S(·) ক্রমে C' সাজান, সর্বোচ্চ k খুঁজুন যেমন |E(S)| + w'S(Sk) ≤ gf(|S|+k)

४. |S|+k ফেরত দিন

সময় জটিলতা: O(|C|³ + |S||C|)

সঠিকতা (Theorem 3):

প্রতিটি স্বাধীন সেট Πi তে সর্বাধিক s'i শীর্ষবিন্দু নির্বাচন করুন
প্রতিটি Rσ তে দুই-হপ সীমাবদ্ধতার কারণে সর্বাধিক १ শীর্ষবিন্দু নির্বাচন করুন
|E(S*)| ≥ |E(S)| + Σw'S(v^(ij)m) ≥ |E(S)| + Σ^{|S'|} w'S(vj)

সুবিধা:

স্বাধীন সেট কাঠামো বিবেচনা করে (প্রান্ত সংখ্যা অতিমূল্যায়ন হ্রাস করে)
দুই-হপ সীমাবদ্ধতা বিবেচনা করে (প্রতিটি Rσ তে সর্বাধিক १ শীর্ষবিন্দু)
LP শিথিলতার চেয়ে দ্রুত, সীমা কাছাকাছি

পরীক্ষামূলক সেটআপ

ডেটাসেট

উৎস: নেটওয়ার্ক ডেটা রিপোজিটরি
স্কেল: १३९টি বাস্তব নির্দেশনাহীন গ্রাফ
পরিসীমা: সর্বাধিক ५.८७×१०⁷ শীর্ষবিন্দু, १.०६×१०⁸ প্রান্ত
ডোমেইন: সামাজিক নেটওয়ার্ক, জৈব নেটওয়ার্ক, সহযোগিতা নেটওয়ার্ক, রোড নেটওয়ার্ক ইত্যাদি

f(·) ফাংশন কনফিগারেশন

१. γ-কোয়াসি-ক্লিক: f(i) = γ(i choose 2), γ ∈ {०.९९, ०.९५, ०.९०, ०.८५}

অ-উত্তরাধিকার ফাংশন २. s-ত্রুটিপূর্ণ ক্লিক: f(i) = (i choose 2) - s, s ∈ {१, ३}
উত্তরাধিকার ফাংশন

তুলনা অ্যালগরিদম

१. Deg-BnB: অবক্ষয় ক্রম + শাখা-এবং-সীমাবদ্ধতা २. TwoDeg-BnB: দুই-হপ অবক্ষয় ক্রম + শাখা-এবং-সীমাবদ্ধতা ३. BnB: বিশুদ্ধ শাখা-এবং-সীমাবদ্ধতা (কোন বিয়োজন নেই) ४. MIP: Gurobi সমাধানকারী + MIP-fD মডেল ५. Deg-MIP: অবক্ষয় ক্রম বিয়োজন + MIP উপ-সমস্যা সমাধান করুন ६. TwoDeg-MIP: দুই-হপ অবক্ষয় ক্রম বিয়োজন + MIP উপ-সমস্যা সমাধান করুন

পরীক্ষামূলক পরিবেশ

CPU: Intel Xeon Platinum 8360Y @ २.४०GHz
সিস্টেম: Ubuntu २२.०४
সংকলন: g++ ९.३.० with -Ofast
সময় সীমা: ३६०० সেকেন্ড (१ ঘণ্টা)
কোড: https://github.com/cy-Luo000/MDSL

মূল্যায়ন সূচক

বিভিন্ন সময় বিন্দুতে সমাধান করা উদাহরণের সংখ্যা
নির্দিষ্ট গ্রাফের চালনা সময়
সীমা কঠোরতা (সর্বোত্তম সমাধানের সাথে পার্থক্য)
অনুসন্ধান গাছ নোড সংখ্যা

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

१. সামগ্রিক কর্মক্ষমতা (চিত্র ४ & ५)

γ-কোয়াসি-ক্লিক (γ=०.९९, ०.९५):

TwoDeg-BnB এবং Deg-BnB সমস্ত সময় সেগমেন্টে অন্যান্য অ্যালগরিদমের চেয়ে সম্পূর্ণভাবে উন্নত
१ ঘণ্টায়, TwoDeg-BnB প্রায় १०० উদাহরণ সমাধান করে, BnB মাত্র ५०টি
MIP প্রায় কোন উদাহরণ সমাধান করতে পারে না

γ-কোয়াসি-ক্লিক (γ=०.९०, ०.८५):

१००० সেকেন্ডের পরে, TwoDeg-MIP এবং Deg-MIP শাখা-এবং-সীমাবদ্ধতা পদ্ধতির সাথে কর্মক্ষমতা কাছাকাছি
বিয়োজন কাঠামো MIP কর্মক্ষমতা উল্লেখযোগ্যভাবে উন্নত করে

s-ত্রুটিপূর্ণ ক্লিক (s=१, ३):

TwoDeg-BnB এবং Deg-BnB প্রায় ११० উদাহরণ সমাধান করে
বিশুদ্ধ BnB প্রায় ६० উদাহরণ সমাধান করে
উত্তরাধিকার সম্পত্তি শাখা-এবং-সীমাবদ্ধতা পদ্ধতিকে আরও সুবিধাজনক করে তোলে

মূল আবিষ্কার: বিয়োজন কাঠামো সমাধান করা উদাহরণের সংখ্যা দ্বিগুণ করে

२. বড় আকারের গ্রাফ বিস্তারিত ফলাফল (টেবিল १ & २)

উল্লেখযোগ্য ক্ষেত্রে (γ=०.९९):

web-uk-२००५ (१२९,६३२ শীর্ষবিন্দু): TwoDeg-BnB ६३४ সেকেন্ড, MIP সময়সীমা অতিক্রম
inf-road-usa (२३,९४७,३४७ শীর্ষবিন্দু): TwoDeg-BnB ७० সেকেন্ড, অন্যান্য পদ্ধতি সময়সীমা অতিক্রম
scc_infect-dublin: Deg-BnB ०.५४ সেকেন্ড, TwoDeg-BnB সময়সীমা অতিক্রম (ক্রম নির্বাচন প্রভাব)

ত্বরণ প্রভাব:

TwoDeg-BnB BnB এর চেয়ে २-३ সংখ্যার মাত্রা দ্রুত (যেমন web-indochina-२००४: ०.२५ সেকেন্ড vs সময়সীমা অতিক্রম)
३९টি উদাহরণ TwoDeg-BnB বা Deg-BnB সমাধান করে কিন্তু BnB ব্যর্থ
বিয়োজন+MIP কখনও বিশুদ্ধ সমন্বয় অ্যালগরিদমের চেয়ে উন্নত (যেমন web-sk-२००५)

s-ত্রুটিপূর্ণ ক্লিক (টেবিল २):

উত্তরাধিকার সম্পত্তি আরও হ্রাস নিয়ে আসে
scc_infect-dublin (s=१): TwoDeg-BnB ०.८३ সেকেন্ড vs Deg-MIP সময়সীমা অতিক্রম
rec-amazon: TwoDeg-BnB ०.०८ সেকেন্ড vs BnB २६४ সেকেন্ড

অপসারণ পরীক্ষা

সীমা কার্যকারিতা বিশ্লেষণ (টেবিল ३ & ४)

সীমা কঠোরতা তুলনা:

LP শিথিলতা > SortBound > সরল সীমা

নির্দিষ্ট ক্ষেত্রে (γ=०.९५):

ca-CondMat:
- সর্বোত্তম: २८
- LP: २९, সরল: २८०, SortBound: १४२
- SortBound কঠোরতা এবং স্কেলেবিলিটির মধ্যে ভারসাম্য অর্জন করে
inf-roadNet-CA:
- সর্বোত্তম: ४
- LP: গণনা করা যায় না, সরল: १३, SortBound: ५
- LP বড় গ্রাফে ব্যর্থ

অনুসন্ধান গাছ আকার প্রভাব:

inf-roadNet-CA (γ=०.९५):
- TwoDeg-BnB: ५ সেকেন্ড, १० নোড
- TwoDeg-BnB/ub (কোন SortBound নেই): १० সেকেন্ড, १४,१३८,८२० নোড
- অনুসন্ধান গাছ ६ সংখ্যার মাত্রা হ্রাস
ca-MathSciNet (s=३):
- TwoDeg-BnB: ७.६२ সেকেন্ড, ८० নোড
- TwoDeg-BnB/ub: १२२८ সেকেন্ড, २५६,३२५,०२० নোড
- १०० গুণ ত্বরণ

মূল আবিষ্কার: SortBound কঠোরতা বজায় রেখে মিলিয়ন-স্তরের শীর্ষবিন্দু গ্রাফে স্কেলেবল

αG এবং চালনা সময়ের সম্পর্ক (চিত্র ६ & ७)

পর্যবেক্ষণ:

প্রায় অর্ধেক উদাহরণ αG ≤ १००० (|V| এর চেয়ে অনেক ছোট)
চালনা সময় αG এর সাথে ইতিবাচক সম্পর্ক
দুই-হপ অবক্ষয় ক্রম সাধারণত ছোট αG উৎপাদন করে

সাধারণ ক্ষেত্রে:

ca-dblp-२०१०: |V|=२२६,४१३, dG=७४, tdG=२३८, dG·ΔG=१७,६१२
- দুই-হপ অবক্ষয় ক্রম সুবিধা স্পষ্ট

যাচাইকরণ: αG কমানোর ডিজাইন ধারণা সমর্থন করে

ক্ষেত্র বিশ্লেষণ

গ্রাফ বিয়োজন প্রভাব উদাহরণ

web-indochina-२००४ উদাহরণ (|V|=११,३५८, |E|=४७,६०६):

অবক্ষয় ডিগ্রি: dG=४९
দুই-হপ অবক্ষয় ডিগ্রি: tdG=१९९
বিয়োজনের পরে: αG=१९९ (দুই-হপ ক্রম) vs αG≈२४५० (অবক্ষয় ক্রম)
কর্মক্ষমতা: TwoDeg-BnB ०.२५ সেকেন্ড vs Deg-BnB ०.१८ সেকেন্ড vs BnB १२.१० সেকেন্ড

সীমা অ্যালগরিদম উদাহরণ (চিত্র २ & ३)

ইনপুট: १० শীর্ষবিন্দু, S={v१,v२}, C={v३,...,v१०}

পদক্ষেপ: १. স্বাধীন সেটে বিভক্ত করুন: Π१={v३,v५,v७,v९}, Π२={v४,v६,v८,v१०} २. wS গণনা করুন: wS(v३)=०, wS(v५)=१, wS(v७)=२... ३. দূরত্ব দ্বারা আরও বিভক্ত করুন: R¹१={v३,v७}, R²१={v५,v९}, R¹२={v८,v४}, R²२={v१०,v६} ४. সর্বনিম্ন wS নির্বাচন করুন: C'={v३,v५,v८,v१०} ५. w'S গণনা করুন: w'S(v३)=०, w'S(v८)=०, w'S(v५)=२, w'S(v१०)=२

ফলাফল:

f(i)=०.८(i choose २): সীমা=४
f(i)=(i choose २)-४: সীমা=५

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. তাত্ত্বিক অবদান:

f(·)-ঘন গ্রাফ তত্ত্ব কাঠামো সিস্টেমেটাইজ করা
উত্তরাধিকার সম্পত্তির প্রয়োজনীয় এবং পর্যাপ্ত শর্ত প্রমাণ করা
বিয়োজন কাঠামোর সঠিকতা এবং জটিলতা বিশ্লেষণ প্রদান করা

२. অ্যালগরিদম অবদান:

বিয়োজন কাঠামো সমস্যাকে n টি স্বাধীন উপ-সমস্যায় বিয়োজন করে
দুই-হপ অবক্ষয় ক্রম কার্যকরভাবে উপগ্রাফ আকার নিয়ন্ত্রণ করে
ক্রম সীমা কঠোরতা এবং দক্ষতার মধ্যে ভারসাম্য অর্জন করে

३. পরীক্ষামূলক যাচাইকরণ:

१३९টি বাস্তব গ্রাফে সমাধান করা উদাহরণের সংখ্যা দ্বিগুণ
দশ মিলিয়ন-স্তরের শীর্ষবিন্দু গ্রাফে স্কেলেবল
ক্রম সীমা অনুসন্ধান গাছ ६ সংখ্যার মাত্রা হ্রাস করে

সীমাবদ্ধতা

१. অ্যালগরিদম সীমাবদ্ধতা:

এখনও সূচক সময় অ্যালগরিদম (O(२^αG))
ঘন গ্রাফের জন্য αG |V| এর কাছাকাছি হতে পারে
দুটি ক্রম কৌশল আগে থেকে কোনটি ভাল তা নির্ধারণ করা কঠিন

२. মডেল সীমাবদ্ধতা:

ব্যাস=२ সীমাবদ্ধতা খুব কঠোর হতে পারে
শীর্ষবিন্দু ওজন বা প্রান্ত ওজন বিবেচনা করে না
f(·) উত্তরাধিকার সম্পত্তি থাকার জন্য নির্দিষ্ট শর্ত পূরণ করতে হবে

३. পরীক্ষামূলক সীমাবদ্ধতা:

শুধুমাত্র দুটি f(·) ফাংশন পরীক্ষা করা
সমস্ত সম্পর্কিত কাজের সাথে সরাসরি তুলনা নেই
অতি-বড় আকারের গ্রাফ (বিলিয়ন-স্তরের শীর্ষবিন্দু) পরীক্ষার অভাব

ভবিষ্যত দিকনির্দেশনা

१. অ্যালগরিদম সম্প্রসারণ:

বিয়োজন কাঠামো সমান্তরালকরণ (উপ-গ্রাফ স্বাধীন সমান্তরালযোগ্য)
অন্যান্য ব্যাস সীমাবদ্ধতায় সম্প্রসারণ (k-club, k≥३)
অন্যান্য কাঠামো সীমাবদ্ধতা একত্রিত করা (শীর্ষবিন্দু সংযোগ)

२. তাত্ত্বিক গভীরকরণ:

আরও f(·) ফাংশনের উত্তরাধিকার সম্পত্তি বিশ্লেষণ
প্যারামিটারাইজড জটিলতা গবেষণা
অনুমান অ্যালগরিদম ডিজাইন

३. প্রয়োগ সম্প্রসারণ:

গতিশীল গ্রাফে বৃদ্ধিমূলক অ্যালগরিদম
ওজনযুক্ত গ্রাফ সম্প্রসারণ
নির্দিষ্ট ডোমেইন মডেল (যেমন জৈব নেটওয়ার্ক)

গভীর মূল্যায়ন

শক্তি

१. তাত্ত্বিক কঠোরতা:

সম্পূর্ণ গাণিতিক প্রমাণ (সংযোজন A)
স্পষ্ট জটিলতা বিশ্লেষণ
উত্তরাধিকার সম্পত্তির প্রয়োজনীয় এবং পর্যাপ্ত শর্ত (Lemma १ & २)

२. অ্যালগরিদম উদ্ভাবনী:

বিয়োজন কাঠামো: Lemma ३ বৈশ্বিক সমস্যাকে স্থানীয় সমস্যায় চতুরভাবে বিয়োজন করে
দুই-হপ অবক্ষয় ক্রম: ব্যাস সীমাবদ্ধতার জন্য উদ্ভাবনী ক্রম কৌশল
ক্রম সীমা: বহু-স্তরীয় নেস্টেড বিভাজন (স্বাধীন সেট+দূরত্ব সীমাবদ্ধতা) ডিজাইন সূক্ষ্ম

३. পরীক্ষামূলক সম্পূর্ণতা:

१३९টি বাস্তব গ্রাফ, ६টি অ্যালগরিদম, २টি f(·) ফাংশন
বিস্তারিত অপসারণ পরীক্ষা (টেবিল ३ & ४)
ভিজ্যুয়ালাইজেশন বিশ্লেষণ (চিত্র ६ & ७)
খোলা উৎস কোড পুনরুৎপাদনযোগ্যতা নিশ্চিত করে

४. ব্যবহারিক মূল্য:

দশ মিলিয়ন-স্তরের শীর্ষবিন্দুতে স্কেলেবল
MIP এর চেয়ে কয়েক সংখ্যার মাত্রা দ্রুত
সর্বজনীন কাঠামো একাধিক ক্লিক শিথিলকরণ মডেলে প্রযোজ্য

५. লেখার স্পষ্টতা:

প্রবর্তনী প্রেরণা স্পষ্ট (চিত্র १ স্বজ্ঞাত)
অ্যালগরিদম সিউডোকোড বিস্তারিত
প্রমেয় প্রমাণ সম্পূর্ণ

অপূর্ণতা

१. ক্রম কৌশল নির্বাচন:

কখন অবক্ষয় বনাম দুই-হপ অবক্ষয় ব্যবহার করতে হবে তার তাত্ত্বিক নির্দেশনা অভাব
টেবিল १ দেখায় কখনও Deg-BnB দ্রুত (যেমন scc_infect-dublin)
পরামর্শ: স্ব-অভিযোজিত কৌশল বা নির্বাচন হিউরিস্টিক ডিজাইন করুন

२. সীমা অ্যালগরিদম জটিলতা:

O(|C|³) বোতলের গলা হতে পারে
লোভী রঙ অ-সর্বোত্তম
উন্নতির দিক: দ্রুত রঙ অ্যালগরিদম বা সর্বোত্তমতা শিথিল করুন

३. পরীক্ষামূলক তুলনা:

Santos et al. २०२४ এর স্প্যানিং ট্রি পদ্ধতির সাথে তুলনা নেই
নির্দিষ্ট সমস্যার সর্বোত্তম অ্যালগরিদমের সাথে তুলনা অভাব (যেমন Chang २०२३ এর k-ত্রুটিপূর্ণ ক্লিক অ্যালগরিদম)
MIP মডেল উন্নতির সম্ভাবনা (যেমন বৈধ অসমতা যোগ করা)

४. স্কেলেবিলিটি বিশ্লেষণ:

αG>१०,००० ক্ষেত্রে আলোচনা অপর্যাপ্ত
ঘন গ্রাফ কর্মক্ষমতা সম্পূর্ণভাবে পরীক্ষা করা হয়নি
মেমরি খরচ বিশ্লেষণ অনুপস্থিত

५. তাত্ত্বিক শূন্যতা:

অনুমান অনুপাত বিশ্লেষণ প্রদান করা হয়নি
প্যারামিটারাইজড জটিলতা (যেমন αG এর প্যারামিটার হিসাবে) আলোচনা করা হয়নি
গড় ক্ষেত্রে জটিলতা বিশ্লেষণ করা হয়নি

প্রভাব

१. একাডেমিক অবদান:

একাধিক ক্লিক শিথিলকরণ মডেলের একীভূত তাত্ত্বিক কাঠামো
বিয়োজন কৌশল অন্যান্য উপগ্রাফ নিষ্কাশন সমস্যায় স্থানান্তরযোগ্য
উদ্ধৃতি মূল্য উচ্চ (NP-কঠিন সমস্যা, গ্রাফ বিয়োজন, শাখা-এবং-সীমাবদ্ধতা একত্রিত করে)

२. ব্যবহারিক মূল্য:

সম্প্রদায় আবিষ্কার, জৈব তথ্যবিজ্ঞান ইত্যাদি ক্ষেত্রে সরাসরি প্রয়োগ
খোলা উৎস কোড প্রযুক্তি রূপান্তর প্রচার করে
অন্যান্য অ্যালগরিদমের জন্য baseline হিসাবে কাজ করতে পারে

३. পুনরুৎপাদনযোগ্যতা:

অ্যালগরিদম বর্ণনা বিস্তারিত
কোড খোলা উৎস (https://github.com/cy-Luo000/MDSL)
ডেটাসেট জনসাধারণের জন্য উপলব্ধ (নেটওয়ার্ক ডেটা রিপোজিটরি)
পরীক্ষামূলক সেটআপ স্পষ্ট

४. সীমাবদ্ধতা:

শিল্প-স্তরের প্রয়োগের জন্য আরও অপ্টিমাইজেশন প্রয়োজন (যেমন সমান্তরালকরণ)
নির্দিষ্ট f(·) এর জন্য কাস্টমাইজড অ্যালগরিদম আরও ভাল হতে পারে
ব্যবহারিকতা যাচাই করতে আরও ডোমেইন বিশেষজ্ঞের প্রয়োজন

প্রযোজ্য পরিস্থিতি

সুপারিশকৃত পরিস্থিতি: १. সামাজিক নেটওয়ার্ক বিশ্লেষণ: ঘনিষ্ঠভাবে সংযুক্ত সম্প্রদায় খুঁজে পাওয়া (ব্যাস ≤२ দ্রুত যোগাযোগ নিশ্চিত করে) २. জৈব নেটওয়ার্ক: প্রোটিন জটিল সনাক্তকরণ (কিছু প্রান্ত অনুপস্থিত অনুমতি দেয়) ३. সহযোগিতা নেটওয়ার্ক: মূল গবেষণা দল সনাক্তকরণ ४. মধ্যম আকারের গ্রাফ: |V|<१०⁶, αG<५००० সময় সর্বোত্তম কর্মক্ষমতা

অসুপারিশকৃত পরিস্থিতি: १. অতি-বড় আকারের ঘন গ্রাফ: αG |V| এর কাছাকাছি সময় সূচক বিস্ফোরণ २. রিয়েল-টাইম প্রয়োগ: সর্বোচ্চ ক্ষেত্রে এখনও সূচক সময় প্রয়োজন ३. অনুমান সমাধান যথেষ্ট পরিস্থিতি: নির্ভুল অ্যালগরিদম খরচ বেশি

উন্নতি সুপারিশ: १. দ্রুত অনুমান সমাধানের জন্য হিউরিস্টিক অ্যালগরিদম একত্রিত করুন २. অতি-বড় আকারের গ্রাফ প্রক্রিয়া করতে সমান্তরালকরণ করুন ३. নির্দিষ্ট f(·) এর জন্য বিশেষায়িত অ্যালগরিদম ডিজাইন করুন

সংদর্ভ

মূল সম্পর্কিত কাজ

१. Veremyev et al. (२०१६): "সর্বোচ্চ কোয়াসি-ক্লিক এবং ঘন উপগ্রাফ খুঁজে পাওয়ার জন্য নির্ভুল MIP-ভিত্তিক পদ্ধতি" - GF३ MIP মডেল প্রস্তাব করে

२. Luo et al. (२०२४): "সর্বোচ্চ k-ত্রুটিপূর্ণ ক্লিক সমস্যার জন্য উন্নত সময় জটিলতা সহ দ্রুত শাখা অ্যালগরিদম" - ECAI २०२४, O(nc·१.२ⁿ) অ্যালগরিদম

३. Chang (२०२३): "উন্নত সময় জটিলতা সহ দক্ষ সর্বোচ্চ k-ত্রুটিপূর্ণ ক্লিক গণনা" - PACMMOD, উন্নত শাখা-এবং-সীমাবদ্ধতা

४. Santos et al. (२०२४): "সর্বোচ্চ কোয়াসি-ক্লিক এবং ঘনতম k-উপগ্রাফ সমস্যার জন্য সংযোগ নিশ্চিত করা" - স্প্যানিং ট্রি সংযোগ সীমাবদ্ধতা

५. Wünsche (२०२१): "শিথিল ক্লিক অনুসন্ধান করার সময় ফাঁক মনে রাখুন" - প্রথমবারের মতো দুই-হপ অবক্ষয় ক্রম প্রস্তাব করে

তাত্ত্বিক ভিত্তি

६. Matula & Beck (१९८३): "ক্ষুদ্রতম-শেষ ক্রম এবং ক্লাস্টারিং এবং গ্রাফ রঙ অ্যালগরিদম" - অবক্ষয় ক্রমের ক্লাসিক কাজ

७. Asahiro et al. (२००२): "ঘন উপগ্রাফ খুঁজে পাওয়ার জটিলতা" - f(·)-ঘন গ্রাফের জটিলতা ফলাফল

८. Downey & Fellows (२०१२): "প্যারামিটারাইজড জটিলতা" - W१-কঠোরতা তত্ত্ব

সামগ্রিক মূল্যায়ন: এটি একটি তাত্ত্বিকভাবে কঠোর, অ্যালগরিদমিকভাবে উদ্ভাবনী এবং পরীক্ষামূলকভাবে সম্পূর্ণ উৎকৃষ্ট কাগজ। বিয়োজন কাঠামো এবং ক্রম সীমা পদ্ধতি উচ্চ সাধারণতা এবং ব্যবহারিক মূল্য রাখে। প্রধান অবদান একাধিক ক্লিক শিথিলকরণ মডেল একীভূত করা এবং দক্ষ সমাধান অ্যালগরিদম প্রদান করা। গ্রহণের সুপারিশ করা হয়, গ্রাফ অ্যালগরিদম এবং নেটওয়ার্ক বিশ্লেষণ ক্ষেত্রে গুরুত্বপূর্ণ অবদান রাখে।