🔬 physics

Heuristic and exact modularity optimization with size-constrained communities

यह शोध पत्र मॉडुलैरिटी अनुकूलन (modularity optimization) के लिए एक ह्यूरिस्टिक प्रस्तावित करके आकार-प्रतिबंधित समुदाय पहचान (size-constrained community detection) की समस्या को संबोधित करता है और एक सटीक पूर्णांक अनुकूलन बेसलाइन (exact integer optimization baseline) के विरुद्ध इसका सत्यापन करता है, जो यह प्रदर्शित करता है कि ये विधियाँ उपयोगकर्ता द्वारा निर्दिष्ट आकार श्रेणियों के भीतर समुदाय प्राप्त करने के लिए रेजोल्यूशन पैरामीटर ट्यूनिंग के एक सिद्धांतपूर्ण विकल्प के रूप में कार्य करती हैं।

मूल लेखक: Filipi N. Silva, Samin Aref, Vincent Traag, Santo Fortunato

प्रकाशित 2026-05-26

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Filipi N. Silva, Samin Aref, Vincent Traag, Santo Fortunato

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक शहर योजनाकार (city planner) हैं जिसका काम एक विशाल, हलचल भरे शहर को मोहल्लों में विभाजित करना है। आपका लक्ष्य उन लोगों को समूहों में बांटना है जो एक-दूसरे को अच्छी तरह जानते हैं और साथ समय बिताते हैं, ताकि उन्हें विशिष्ट "समुदायों" (communities) में बांटा जा सके। कंप्यूटर वैज्ञानिक इसे कम्युनिटी डिटेक्शन (community detection) कहते हैं।

आमतौर पर, एल्गोरिदम मानचित्र के संपर्कों को देखकर यह तय करता है कि, "ये लोग आपस में बहुत जुड़े हुए हैं, इसलिए वे एक ही मोहल्ले में होने चाहिए।" लेकिन इसमें एक समस्या है: एल्गोरिदम को मोहल्ले के आकार की परवाह नहीं होती है। इसके परिणामस्वरूप एक विशाल, अत्यधिक भीड़भाड़ वाला जिला बन सकता है जिसमें 10,000 लोग हों, और साथ ही कुछ छोटे, अकेले पड़े छोटे गाँव भी हो सकते हैं जिनमें केवल दो लोग हों।

वास्तविक दुनिया में, विशेषज्ञों को पता होता है कि एक "अच्छा" मोहल्ला कितना बड़ा होना चाहिए। एक मार्केटिंग टीम जानती है कि एक ग्राहक वर्ग (customer segment) उपयोगी होने के लिए कम से कम 100 लोगों का होना चाहिए। एक मस्तिष्क वैज्ञानिक (brain scientist) जानता है कि मस्तिष्क का एक कार्यात्मक क्षेत्र (functional region) पूरे मस्तिष्क के आकार का नहीं होना चाहिए। लेकिन मानक उपकरण आपको यह कहने की अनुमति नहीं देते कि, "सुनिश्चित करें कि प्रत्येक मोहल्ले में 50 से 200 लोग हों।"

यह शोध पत्र इस समस्या को हल करने का एक नया तरीका पेश करता है। यहाँ सरल शब्दों में इसका विवरण दिया गया है:

पुराना तरीका: "रेज़ोल्यूशन नॉब" के साथ अनुमान लगाना

पहले, यदि विशेषज्ञ मोहल्ले के आकार को नियंत्रित करना चाहते थे, तो उन्हें एक "रेज़ोल्यूशन नॉब" (resolution knob) का उपयोग करना पड़ता था।

उपमा: कल्पना कीजिए कि आप एक विशिष्ट स्टेशन खोजने के लिए रेडियो ट्यून करने की कोशिश कर रहे हैं। आपको सटीक फ्रीक्वेंसी का पता नहीं है, इसलिए आप बस डायल को इधर-उधर घुमाते हैं, यह सुनने के लिए कि आवाज़ कितनी साफ़ हो रही है।
समस्या: नेटवर्क विज्ञान में, इस नॉब को घुमाने से समुदायों का औसत आकार बदल जाता है, लेकिन यह एक बहुत ही भद्दा उपकरण है। आप औसत को सही कर सकते हैं, लेकिन फिर भी आपके पास एक विशाल मोहल्ला और कई छोटे मोहल्ले हो सकते हैं। आपके पास विविधता (सबसे बड़े और सबसे छोटे समूहों के बीच का अंतर) पर कोई नियंत्रण नहीं है। यह बिल्कुल वैसा ही है जैसे कुकीज़ के सटीक आकार को नियंत्रित करने के लिए केवल ओवन का तापमान ऊपर-नीचे करना; आप औसत को सही कर सकते हैं, लेकिन कुछ कुकीज़ जल सकती हैं और कुछ कच्ची रह सकती हैं।

नया तरीका: "आकार-लागू करने वाला" नियम (The "Size-Enforcing" Rule)

लेखक (फिलीपी सिल्वा, सामिन अरेफ, विन्सेंट ट्राग, और सैंटो फोर्टुनाटो) एक नया तरीका प्रस्तावित करते हैं जो एक क्लब के सख्त बाउंसर की तरह काम करता है।

उपमा: तापमान का अनुमान लगाने के बजाय, आप एल्गोरिदम को बताते हैं: "कोई भी मोहल्ला 50 लोगों से कम का नहीं हो सकता, और कोई भी 200 से अधिक का नहीं हो सकता।"
यह कैसे काम करता है: उन्होंने एक ह्यूरिस्टिक (Heuristic - एक स्मार्ट, तेज़ शॉर्टकट) बनाया है जो इन आकार के नियमों का सख्ती से पालन करते हुए सर्वोत्तम संभव समूहीकरण खोजने की कोशिश करता है।
- यदि कोई समूह बहुत छोटा हो जाता है, तो एल्गोरिदम लोगों को बाहर निकाल देता है।
  // यदि कोई समूह बहुत बड़ा हो जाता है, तो वह उन्हें विभाजित कर देता है।
- यह एक "पेनल्टी" (दंड) जोड़कर किया जाता है। यदि कोई समूह आकार के नियम को तोड़ता है, तो एल्गोरिदम को एक "नाराज़गी" (पेनल्टी स्कोर) मिलती है और वह इसे ठीक करने की कोशिश करता है।

"गोल्ड स्टैंडर्ड" की जाँच

यह साबित करने के लिए कि उनका नया "स्मार्ट शॉर्टकट" वास्तव में काम करता है, उन्होंने एक एक्ज़ैक्ट (Exact - सटीक) विधि भी बनाई।

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

वास्तविक दुनिया के परीक्षण

टीम ने दो प्रकार के मानचित्रों पर इसका परीक्षण किया:

नकली शहर (सिंथेटिक बेंचमार्क): उन्होंने कंप्यूटर द्वारा निर्मित नेटवर्क बनाए जहाँ वे पहले से ही "सही" मोहल्लों को जानते थे।
- परिणाम: पुराना "नॉब" वाला तरीका अक्सर सही मोहल्लों को खोजने में विफल रहा, खासकर जब कनेक्शन थोड़े अस्त-व्यस्त थे। नया "आकार-लागू करने वाला" तरीका लगभग हर बार सही समूहों को ढूंढ लेता है, भले ही पुराना तरीका भ्रमित हो गया हो।
वास्तविक शहर (वास्तविक नेटवर्क):
- मार्केट सेगमेंटेशन: व्यवसाय में, उन्होंने दिखाया कि यह ग्राहकों को उपयोगी आकार में समूहित करने में कैसे मदद करता है, जिससे एक विशाल समूह और कई बेकार छोटे समूहों की समस्या से बचा जा सकता है।
- ब्रेन मैप्स (मस्तिष्क के मानचित्र): उन्होंने मानव मस्तिष्क के एक मानचित्र को देखा। मानक तरीके अक्सर मस्तिष्क को केवल दो बड़े हिस्सों (बाएं और दाएं) में विभाजित कर देते हैं, जो बहुत उपयोगी नहीं है। मस्तिष्क क्षेत्रों के बारे में न्यूरोसाइंटिस्ट के ज्ञान के आधार पर आकार की सीमाएं निर्धारित करके, उनके तरीके ने 6 विशिष्ट, सार्थक कार्यात्मक क्लस्टर (functional clusters) खोजे जो विशेषज्ञ ज्ञान के अनुरूप थे।

मुख्य निष्कर्ष (The Takeaway)

यह शोध पत्र वैज्ञानिकों और विशेषज्ञों को एक ऐसा उपकरण देता है जिससे वे कह सकें, "मैं जानता हूँ कि मेरे क्षेत्र में एक उचित समूह का आकार क्या होता है, और मैं चाहता हूँ कि कंप्यूटर उसका सम्मान करे।"

एक नॉब को अंधेरे में घुमाने और उम्मीद करने के बजाय, अब आप स्पष्ट सीमाएं निर्धारित कर सकते हैं (जैसे, "समूह 43 से 187 लोगों के बीच होने चाहिए")। नया तरीका इन सीमाओं का सम्मान करता है, उच्च गुणवत्ता वाले समूहीकरण पाता है, और इतना तेज़ है कि इसे वास्तविक, बड़े पैमाने के डेटा पर उपयोग किया जा सके। यह कम्युनिटी डिटेक्शन को "अनुमान और जांच" के खेल से बदलकर एक सटीक, सिद्धांत आधारित प्रक्रिया में बदल देता है।

तकनीकी सारांश: आकार-सीमित समुदायों के साथ ह्यूरिस्टिक और सटीक मॉडुलैरिटी अनुकूलन

समस्या विवरण

कम्युनिटी डिटेक्शन (समुदाय पहचान) नेटवर्क विश्लेषण में एक मौलिक कार्य है, फिर भी मानक एल्गोरिदम अक्सर आकार संबंधी डोमेन-विशिष्ट पूर्व ज्ञान को शामिल करने में विफल रहते हैं। बाजार विभाजन (market segmentation), न्यूरोसाइंस (ब्रेन कनेक्टोम), और जीनोमिक्स (क्रोमोसोमल इंटरैक्शन) जैसे अनुप्रयोगों में, विशेषज्ञों के पास समुदायों के आकार के उचित रेंज के बारे में ज्ञान होता है। हालांकि, मौजूदा अनकन्स्ट्रेंड (unconstrained) विधियां अक्सर चरम आकार के अंतर वाले विभाजन (जैसे, एक विशाल समुदाय और कई तुच्छ समुदाय) उत्पन्न करती हैं या जैविक या कार्यात्मक वास्तविकताओं के साथ संरेखित होने में विफल रहती हैं।

जबकि मल्टी-रेज़ोल्यूशन तकनीकें एक रेज़ोल्यूशन पैरामीटर ( $\gamma$ ) को ट्यून करके औसत समुदाय आकार को अप्रत्यक्ष रूप से प्रभावित करने की अनुमति देती हैं, यह दृष्टिकोण व्यक्तिगत समुदायों के आकार को नियंत्रित नहीं करता है, न ही यह गारंटी देता है कि सभी समुदाय उपयोगकर्ता द्वारा परिभाषित एक विशिष्ट सीमा के भीतर होंगे। यह शोध पत्र साइज-कंस्ट्रेंड मैक्सिमम मॉडुलैरिटी (SMM) समस्या को संबोधित करता है: एक नेटवर्क का ऐसा विभाजन खोजना जो मॉडुलैरिटी को अधिकतम करे और साथ ही यह सुनिश्चित करे कि प्रत्येक समुदाय का आकार $n_c$ इस प्रकार हो कि $n_{min} \le n_c \le n_{max}$ ।

कार्यप्रणाली

लेखक SMM समस्या को हल करने के लिए एक दोहरी पद्धति प्रस्तावित करते हैं: एक सटीक अनुकूलन बेसलाइन और एक स्केलेबल ह्यूरिस्टिक।

1. सटीक अनुकूलन बेसलाइन (SMMk)

विश्वसनीयता के लिए ग्राउंड ट्रुथ स्थापित करने हेतु, लेखक इस समस्या को एक इंटीजर प्रोग्राम (IP) के रूप में स्वरूपित करते हैं।

स्वरूपण: वे मैक्सिमम मॉडुलैरिटी $k$ -पार्टिशन (MMk) समस्या के लिए मानक इंटीजर प्रोग्रामिंग स्वरूपण का विस्तार करते हैं।
बाधाएं (Constraints): मॉडल में आकार की सीमाओं को लागू करने के लिए रैखिक बाधाएं शामिल हैं। विशेष रूप से, वे ऐसी बाधाएं पेश करते हैं जो सुनिश्चित करती हैं कि किसी भी गैर-खाली समुदाय $c$ के लिए, नोड्स की संख्या $\sum x_{ic} \ge n_{min}$ हो, और सभी संभावित समुदायों के लिए, $\sum x_{ic} \le n_{max}$ हो।
सॉल्वर: छोटे से मध्यम आकार के ग्राफों के लिए वैश्विक रूप से इष्टतम (या निकट-इष्टतम) विभाजन प्राप्त करने के लिए मॉडल को Gurobi ऑप्टिमाइज़र का उपयोग करके हल किया जाता है। यह ह्यूरिस्टिक के मूल्यांकन के लिए आधार (baseline) के रूप में कार्य करता है।

2. ह्यूरिस्टिक ऑप्टिमाइज़ेशन (कंस्ट्रेंड लीडन - CL)

मानक मॉडुलैरिटी ह्यूरिस्टिक्स (जैसे लीडन एल्गोरिदम) के भीतर आकार की बाधाओं को सीधे लागू करना समस्याग्रस्त है क्योंकि नोड्स के स्थानीय बदलाव आसानी से आकार की सीमाओं का उल्लंघन कर सकते हैं (उदाहरण के लिए, एक नोड को नए सिंगलटन समुदाय में ले जाने से $n_{min} > 1$ का उल्लंघन होता है)।

पेनल्टी दृष्टिकोण: एक बैरियर विधि (जो खोज स्थान को प्रतिबंधित करती है) के बजाय, लेखक एक संशोधित ऑब्जेक्टिव फंक्शन को अनुकूलित करके समस्या को एक अनकन्स्ट्रेंड समस्या में बदलने के लिए पेनल्टी दृष्टिकोण का उपयोग करते हैं:
$Q'(G, P) = Q(G, P) - \phi \Theta(P)$
जहाँ $\Theta(P)$ आकार की बाधाओं का उल्लंघन करने वाले समुदायों के लिए एक पेनल्टी फंक्शन है, और $\phi$ एक पेनल्टी वेट है।
पेनल्टी फंक्शन: एक समुदाय के लिए पेनल्टी $\theta(n_c)$ जिसका आकार $n_c$ है, इस प्रकार परिभाषित है:
$\theta(n_c) = \begin{cases} \sqrt{n_{min} - n_c} & \text{यदि } n_c < n_{min} \\ \sqrt{n_c - n_{max}} & \text{यदि } n_c > n_{max} \end{cases}$
वर्गमूल (square root) फंक्शन को इसलिए चुना गया है क्योंकि यह सब-एडिटिव (sub-additive) है, जो एल्गोरिदम को ऐसे लोकल ऑप्टिमा में फंसने से रोकता है जहाँ एक बड़े उल्लंघन करने वाले समुदाय को दो छोटे उल्लंघन करने वाले समुदायों में विभाजित करने से कुल पेनल्टी कम हो जाती है।
प्रोग्रेसिव शेड्यूल: एल्गोरिदम $\phi = 0$ (अनकन्स्ट्रेंड) से शुरू होता है। यदि परिणामी विभाजन बाधाओं का उल्लंघन करता है, तो $\phi$ को बढ़ाया जाता है ( $10^{-4}$ से शुरू होकर और दोगुना करके) और पिछले समाधान से अनुकूलन को पुन: आरंभ किया जाता है। यह तब तक जारी रहता है जब तक कि एक व्यवहार्य (feasible) विभाजन नहीं मिल जाता।

मुख्य परिणाम

लेखकों ने सिंथेटिक और वास्तविक दुनिया के नेटवर्क में प्रस्तावित कंस्ट्रेंड लीडन (CL) पद्धति का अनकन्स्ट्रेंड लीडन (UL) और कंस्ट्रेंड इंटीजर प्रोग्रामिंग (CIP) बेसलाइन के विरुद्ध मूल्यांकन किया।

सिंथेटिक बेंचमार्क

प्लांटेड पार्टीशन मॉडल: ज्ञात ग्राउंड-ट्रुथ समुदायों वाले नेटवर्क में, CL और CIP, रिट्रीवल रेट (एडजस्टेड म्यूचुअल इंफॉर्मेशन, AMI द्वारा मापा गया) में UL से काफी बेहतर रहे, विशेष रूप से जब मिक्सिंग पैरामीटर कम से मध्यम था। UL अक्सर प्लांटेड समुदायों को प्राप्त करने में विफल रहा क्योंकि इसने आकार की अपेक्षित सीमा से बाहर के आकार वाले विभाजन उत्पन्न किए।
रिंग ऑफ क्लीक्स: 50 क्लीक्स (आकार 5) के ग्राफ में जो क्रमवार जुड़े हुए हैं, UL केवल तभी सही विभाजन प्राप्त करता है जब रेज़ोल्यूशन पैरामीटर को एक विशिष्ट रेंज ( $[5, 40]$ ) के लिए मैन्युअल रूप से ट्यून किया जाता है। इसके विपरीत, CL ने सही आकार रेंज $[2, 8]$ दिए जाने पर डिफॉल्ट रेज़ोल्यूशन ( $\gamma=1$ ) पर प्लांटेड पार्टीशन को सटीक रूप से प्राप्त किया।
विश्वसनीयता: ह्यूरिस्टिक CL की रिट्रीवल दर लगातार CIP बेसलाइन के करीब थी, और कभी-कभी उसके बराबर भी थी, जो यह दर्शाता है कि ह्यूरिस्टिक गति के लिए सटीकता से समझौता नहीं करता है।

वास्तविक दुनिया के नेटवर्क

ब्रेन कनेक्टोम: बुडापेस्ट ब्रेन कनेक्टोम नेटवर्क पर लागू करने पर, UL ने चार समुदायों (हेमिस्फेयर के अनुरूप) का एक तुच्छ विभाजन बनाया, जिसमें न्यूरोसाइंस उपयोगिता की कमी है।
डोमेन अलाइनमेंट: Brainnetome और Schaefer एटलस (नोड्स $[43, 187]$ ) के आधार पर विशेषज्ञ ज्ञान से प्राप्त आकार रेंज का उपयोग करके CL को लागू करने पर, इसने 6 समुदाय बनाए। यह परिणाम ज्ञात कार्यात्मक मस्तिष्क क्लस्टर्स (जैसे Ye et al. द्वारा परिभाषित 7 क्लस्टर) के साथ बहुत बेहतर ढंग से संरेखित होता है।
विविधता का नियंत्रण: लेखकों ने प्रदर्शित किया कि UL में रेज़ोल्यूशन पैरामीटर को बदलने से समुदायों का औसत आकार नियंत्रित होता है लेकिन यह आकारों की विविधता (variance) को नियंत्रित करने में विफल रहता है। CL माध्य और विविधता दोनों पर सीधा नियंत्रण प्रदान करता है, जिससे यह सुनिश्चित होता है कि सभी समुदाय निर्दिष्ट सीमाओं के भीतर हों।

महत्व और दावे

यह शोध पत्र दावा करता है कि प्रस्तावित विधि समुदाय पहचान में डोमेन विशेषज्ञता को शामिल करने का एक सिद्धांतिक तरीका प्रदान करती है।

प्रत्यक्ष नियंत्रण: रेज़ोल्यूशन पैरामीटर्स को ट्यून करने के "ट्रायल-एंड-एरर" अभ्यास के विपरीत, CL उपयोगकर्ताओं को समुदायों के न्यूनतम और अधिकतम आकार को स्पष्ट रूप से परिभाषित करने की अनुमति देता है, जो सीधे डोमेन विशेषज्ञों की आवश्यकताओं को संबोधित करता है।
स्केलेबिलिटी: जबकि सटीक IP विधि (CIP) ग्राफ के आकार के कारण कम्प्यूटेशनल जटिलता से सीमित है, CL ह्यूरिस्टिक स्केलेबल है और इसे बड़े नेटवर्क पर लागू किया जा सकता है, जिससे यह वास्तविक दुनिया के अनुप्रयोगों के लिए व्यावहारिक बनता है।
कार्यान्वयन: विधि को पायथन लीडन एल्गोरिदम पैकेज के भीतर लागू किया गया है, जिससे यह तत्काल उपयोग के लिए सुलभ है।

लेखक निष्कर्ष निकालते हैं कि हालांकि मॉडुलैरिटी की ज्ञात सीमाएं हैं (जैसे रेज़ोल्यूशन लिमिट और स्पष्ट सांख्यिकीय आधार की कमी), उनके ह्यूरिस्टिक के माध्यम से आकार की बाधाओं को लागू करने की क्षमता अधिक सूचनात्मक और डोमेन-संरेखित विभाजन की अनुमति देती है। वे सुझाव देते कि भविष्य का कार्य स्टोकैस्टिक ब्लॉक मॉडल्स (SBMs) जैसे अन्य ढांचों में आकार की बाधाओं को शामिल करने की खोज कर सकता है, ताकि सांख्यिकीय अनुमान संदर्भ के भीतर इन बाधाओं का लाभ उठाया जा सके।