🔢 mathematics

A spectral inference method for determining the number of communities in networks

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

मूल लेखक: Yujia Wu, Xiucai Ding, Jingfei Zhang, Wei Lan, Chih-Ling Tsai

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

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

CC BY 4.0

मूल लेखक: Yujia Wu, Xiucai Ding, Jingfei Zhang, Wei Lan, Chih-Ling Tsai

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

कल्पना कीजिए कि आप एक विशाल, शोर-शराबे वाली पार्टी में कदम रखते हैं। वहाँ हजारों लोग आपस में मिल-जुल रहे हैं, लेकिन आप समूहों को देख नहीं पा रहे हैं। आप जानते हैं कि दोस्तों के अलग-अलग घेरे (circles) हैं—जैसे कि शायद "स्पोर्ट्स फैन्स", "आर्ट लवर्स", या "टेक गीक्स"—लेकिन आप यह नहीं बता पा रहे हैं कि एक समूह कहाँ खत्म होता है और दूसरा कहाँ शुरू होता है।

डेटा साइंस की दुनिया में, यह पार्टी एक नेटवर्क है (जैसे फेसबुक फ्रेंड्स, ट्विटर फॉलोअर्स, या रिसर्च पेपर्स में साइटेशन) और उन समूहों को कम्युनिटीज (communities) कहा जाता है।

वर्षों से, सांख्यिकीविदों (statisticians) ने यह पता लगाने के लिए "नियम पुस्तिकाएं" बनाने की कोशिश की है कि इस पार्टी में कितने समूह मौजूद हैं। लेकिन उन नियम पुस्तिकाओं में दो बड़ी समस्याएँ थीं:

वे बहुत कठोर थीं। यदि पार्टी बहुत बड़ी और विरल (sparse) थी (जहाँ लोग शायद ही एक-दूसरे को जानते हों), तो वे नियम पुस्तिकाएं टूट जाती थीं।
उन्हें समूहों की गिनती करने से पहले हर एक मेहमान के "व्यक्तित्व" का अनुमान लगाने की आवश्यकता होती थी। यह धीमा, जटिल और अक्सर गलत होता था।

यह पेपर समूहों को गिनने का एक नया, चतुर तरीका पेश करता है जो एक जादुई दर्पण (magic mirror) की तरह काम करता है। इसे मेहमानों के व्यक्तित्व को जानने की आवश्यकता नहीं है; यह बस पूरे कमरे के प्रतिबिंब को देखता है।

समस्या: अदृश्य समूहों की गिनती

नेटवर्क को कनेक्शनों की एक विशाल स्प्रेडशीट के रूप में सोचें। यदि आप इस स्प्रेडशीट को ध्यान से देखें, तो यह डॉट्स के एक बिखरे हुए बादल जैसा दिखता है। लेकिन यदि आप इस पर एक विशेष रोशनी डालते हैं (गणितीय रूप से, जिसे आइगेनवैल्यूज (eigenvalues) कहा जाता है), तो वह बादल प्रकाश की अलग-अलग किरणों में विभाजित हो जाता है।

इन चमकीली, मजबूत किरणों की संख्या आमतौर पर बताती है कि कितने समुदाय मौजूद हैं। समस्या यह है कि आप कैसे जानेंगे कि कौन सी किरणें वास्तविक समूह हैं और कौन सी केवल रैंडम शोर (noise) हैं (जैसे कि दो लोगों का गलती से आपस में टकरा जाना)?

समाधान: "गैप" डिटेक्टिव (The "Gap" Detective)

लेखक एक विधि प्रस्तावित करते हैं जिसे स्पेक्ट्रल इन्फरेंस (Spectral Inference) कहा जाता है। यहाँ सरल उपमा दी गई है:

कल्पना कीजिए कि आप एक गायक मंडली (choir) को सुन रहे हैं।

पुराना तरीका: आप हर एक गायक की आवाज़ को पहचानने, उनके सुर को मापने और यह अनुमान लगाने की कोशिश करते हैं कि कितने विभाग (सोप्रानो, ऑल्टो, आदि) हैं। यदि मंडली बहुत बड़ी है या कुछ गायक फुसफुसा रहे हैं (विरल डेटा), तो यह कठिन है।
नया तरीका: आप बस सुरों के बीच के सन्नाटे (silence between the notes) को सुनते हैं।

लेखक संगीत के सुरों (आइगेनवैल्यूज) के बीच के "गैप्स" को देखते हैं।

यदि 3 अलग-अलग समूह हैं, तो आप 3 तेज़ स्वर सुनेंगे, जिसके बाद एक बड़ा सन्नाटा होगा, और फिर बहुत सारे छोटे, धीमे फुसफुसाहट (शोर) होंगे।
यदि 4 समूह हैं, तो शोर से पहले 4 तेज़ स्वर सुनाई देंगे।

उनकी विधि इन गैप्स के एक विशिष्ट अनुपात (ratio) की गणना करती है। यह पूछती है: "क्या तीसरे और चौथे सुर के बीच का गैप एक वास्तविक समूह होने के लिए पर्याप्त बड़ा है, या यह केवल रैंडम स्टेटिक (शोर) है?"

यह क्यों एक गेम-चेंजर है

यह पेपर इस नई विधि की तीन महाशक्तियाँ बताता है:

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

पर्दे के पीछे का "जादू"

उन्हें कैसे पता चलता है कि एक गैप वास्तविक है और शोर नहीं?

वे उन्नत भौतिकी और गणित की एक अवधारणा का उपयोग करते हैं जिसे ट्रेसी-विडोम डिस्ट्रीब्यूशन (Tracy-Widom distribution) कहा जाता है।

उपमा: कल्पना कीजिए कि आपके पास बिल्कुल निष्पक्ष पासे (dice) का एक बैग है। यदि आप उन्हें दस लाख बार फेंकते हैं, तो आपको मिलने वाला उच्चतम नंबर एक बहुत ही विशिष्ट, अनुमानित पैटर्न का पालन करता है।
लेखकों ने महसूस किया कि नेटवर्क में "शोर" बिल्कुल उन्हीं निष्पक्ष पासे के उछाल की तरह व्यवहार करता है।
उन्होंने एक कैलिब्रेशन टूल बनाया (जिसे गौसियन ऑर्थोगोनल एनसेम्बल (GOE) कहा जाता है, जो केवल "सिम्युलेटेड रैंडम नॉइज़" कहने का एक फैंसी तरीका है)।
वे वास्तविक नेटवर्क के "गैप" की तुलना उस "गैप" से करते हैं जिसकी आप शुद्ध रैंडम शोर से अपेक्षा करते हैं। यदि वास्तविक गैप रैंडम शोर के गैप से काफी बड़ा है, तो बिंगो! आपने एक समुदाय खोज लिया।

वास्तविक दुनिया का प्रमाण

लेखकों ने दो वास्तविक उदाहरणों पर इसका परीक्षण किया:

राजनीतिक ब्लॉग: उन्होंने सही ढंग से पहचाना कि यहाँ 2 मुख्य समूह (रूढ़िवादी और उदारवादी) हैं, जबकि कुछ पुरानी विधियाँ भ्रमित होकर सोचने लगीं कि वहाँ अधिक समूह हैं।
सिना वीबो (चीनी ट्विटर): उन्होंने प्रभाव के आधार पर उपयोगकर्ताओं के 2 अलग-अलग प्रकार पाए, और एक बार फिर, अन्य विधियों को मात दी जो संरचना देखने में विफल रही थीं।

निष्कर्ष

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

यह अंततः उन चश्मों के होने जैसा है जो आपको भीड़ भरी पार्टी में भी दोस्तों के अदृश्य घेरों को देखने की अनुमति देते हैं, चाहे पार्टी कितनी भी अराजक क्यों न हो जाए।

यहाँ शोध पत्र "A spectral inference method for determining the number of communities in networks" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र नेटवर्क डेटा में समुदायों की संख्या ( $K$ ) का अनुमान लगाने की महत्वपूर्ण चुनौती को संबोधित करता है। हालाँकि विभिन्न ब्लॉक मॉडल मौजूद हैं (जैसे, स्टोकेस्टिक ब्लॉक मॉडल (SBM), डिग्री-करेक्टेड SBM (DCSBM), मिश्रित सदस्यता मॉडल), लेकिन अंतर्निहित एज-प्रोबेबिलिटी मैट्रिक्स $P$ के वास्तविक रैंक $K$ को निर्धारित करना अक्सर अज्ञात होता है।

मौजूदा विधियों की सीमाएँ:

मॉडल निर्भरता (Model Dependence): अधिकांश मौजूदा विधियों के लिए $K$ का परीक्षण करने से पहले विशिष्ट पैरामीट्रिक मॉडल को फिट करने और अज्ञात मापदंडों (जैसे, नोड सदस्यता, डिग्री विषमता) का अनुमान लगाने की आवश्यकता होती है।
विरलता बाधाएँ (Sparsity Constraints): कई विधियाँ केवल घने (dense) नेटवर्क के लिए मान्य हैं (जहाँ एज प्रोबेबिलिटी $P_{ij}$ स्थिर क्रम में है) और विरल (sparse) शासन ( $P_{ij} \to 0$ ) में विफल हो जाती हैं।
निश्चित बनाम विचलनशील $K$ (Fixed vs. Diverging $K$ ): मौजूदा दृष्टिकोण अक्सर यह मान लेते हैं कि $K$ निश्चित है या बहुत धीरे-धीरे बढ़ता है (जैसे, $O(\log \log n)$ )। बहुत कम विधियाँ नेटवर्क आकार $n$ बढ़ने के साथ समुदायों की बढ़ती संख्या ( $K \to \infty$ ) को समायोजित कर पाती हैं।
ट्यूनिंग पैरामीटर (Tuning Parameters): कई विधियों के लिए ट्यूनिंग पैरामीटर (जैसे, सबसैंपलिंग या बैंडविड्थ चयन के लिए) पर निर्भर रहना पड़ता है, जिन्हें इष्टतम रूप से चुनना कठिन हो सकता है।

2. कार्यप्रणाली (Methodology)

लेखक eigengap ratios पर आधारित एक मॉडल-मुक्त स्पेक्ट्रल इन्फरेंस विधि (model-free spectral inference method) प्रस्तावित करते हैं। इस दृष्टिकोण के लिए नेटवर्क वितरण मापदंडों का अनुमान लगाने या विशिष्ट ब्लॉक मॉडल को फिट करने की आवश्यकता नहीं है।

2.1 परिकल्पना परीक्षण ढांचा (Hypothesis Testing Framework)

विधि $K$ को निर्धारित करने के लिए एक अनुक्रमिक परीक्षण ढांचे का उपयोग करती है:

शून्य परिकल्पना ( $H_0$ ): $K = K_0$ (परिकल्पित समुदायों की संख्या)।
वैकल्पिक परिकल्पना ( $H_1$ ): $K_0 < K \le K_{max}$ ।
अनुमानक (Estimator): समुदायों की अनुमानित संख्या $\hat{K}$ वह सबसे छोटी $K_0$ है जिसके लिए $H_0$ को स्वीकार किया जाता है:
$\hat{K} := \inf \{ K_0 \ge 0 : H_0 \text{ को स्वीकार किया जाता है} \}$

2.2 टेस्ट स्टैटिस्टिक (Test Statistic)

इस विधि का मुख्य आधार एडजेसेंसी मैट्रिक्स $A$ ( $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n$ ) के आइगेनवैल्यू (eigenvalues) से निर्मित टेस्ट स्टैटिस्टिक $T$ है:
$T = \frac{\lambda_{K_0+1}(A) - \lambda_{K_{max}+1}(A)}{\lambda_{K_{max}+1}(A) - \lambda_{K_{max}+2}(A)}$

अंश (Numerator): परिकल्पित रैंक और स्पेक्ट्रम के टेल (tail) के बीच के अंतर का प्रतिनिधित्व करता है।
हर (Denominator): टेल आइगेनवैल्यू (शोर के स्तर/noise floor) के बीच के अंतर का प्रतिनिधित्व करता है।
तर्क (Logic): $H_0$ के तहत, अंश और हर समान क्रम ( $O_p(1)$ ) के होते हैं। $H_1$ के तहत, $T$ का मान $O_p(n^{2/3})$ की दर से बढ़ता है, जिससे $T$ बड़ा हो जाता है।

2.3 कैलिब्रेशन और क्रिटिकल वैल्यू (Calibration and Critical Values)

चूँकि $H_0$ के तहत $T$ का सीमित वितरण (limiting distribution) जटिल है और अज्ञात $P$ की संरचना पर निर्भर करता है, इसलिए लेखक एक कैलिब्रेशन प्रक्रिया प्रस्तावित करते हैं:

ऊपरी सीमा का चयन ( $K_{max}$ ): एडजेसेंसी मैट्रिक्स पर एक समानांतर विश्लेषण (पैरलेल एनालिसिस/परम्यूटेशन विधि) के माध्यम से निर्धारित किया जाता है ताकि यह सुनिश्चित हो सके कि $K_{max} \ge K$ है।
GOE कैलिब्रेशन: क्रिटिकल वैल्यू को गौसियन ऑर्थोगोनल एनसेंबल (GOE) मैट्रिसेस (गौसियन प्रविष्टियों वाले सममित मैट्रिसेस) का उपयोग करके $T$ $T$ को सिम्युलेट करके प्राप्त किया जाता है।
- सैद्धांतिक औचित्य: $H_0$ के तहत, $T$ का वितरण Type-I Tracy-Widom वितरण का एक फलन (functional) है जो Airy kernel द्वारा अभिलक्षित है।
- क्रिटिकल वैल्यू $c_\alpha$ स्वतंत्र $J$ GOE मैट्रिसेस से गणना किए गए स्टैटिस्टिक का $(1-\alpha)$ -क्वांटाइल है।

2.4 एल्गोरिदम (Algorithm)

एडजेसेंसी मैट्रिक्स $A$ और परिकल्पित $K_0$ इनपुट लें।
पैरलेल एनालिसिस (एल्गोरिदम S.1) का उपयोग करके $K_{max}$ निर्धारित करें।
समीकरण (1.5) का उपयोग करके टेस्ट स्टैटिस्टिक $T$ की गणना करें।
GOE मैट्रिसेस के मोंटे कार्लो सिमुलेशन के माध्यम से क्रिटिकल वैल्यू $c_\alpha$ की गणना करें।
यदि $T > c_\alpha$ हो, तो $H_0$ को अस्वीकार करें।

3. मुख्य योगदान (Key Contributions)

3.1 सैद्धांतिक प्रगति (Theoretical Advancements)

मॉडल-मुक्त (Model-Free): यह विधि $\pi_i$ (सदस्यता) या $\omega_i$ (डिग्री) जैसे मापदंडों का अनुमान लगाए बिना विभिन्न ब्लॉक मॉडलों (SBM, DCSBM, MM, DCMM) पर लागू की जा सकती है।
विचलनशील $K$ (Diverging $K$ ): यह $n$ के साथ विचलनशील समुदायों की संख्या $K$ को संभालने वाली पहली विधि है।
विरलता-विचलन व्यापार-बंद (Sparsity-Divergence Trade-off): लेखक Tracy-Widom सीमा की वैधता के लिए एक पर्याप्त शर्त स्थापित करते हैं:
$n^{1/3} \frac{\max_{i,j} P_{ij}}{K^2} \to \infty$
यह शर्त विरल नेटवर्क (जहाँ $P_{ij} \to 0$ ) की अनुमति देती है, बशर्ते $K$ की वृद्धि की दर स्पर्सिटी (sparsity) के सापेक्ष बहुत अधिक न हो। यह $K \ll n^{1/6}$ वाले घने SBM परिदृश्य को पुनः प्राप्त करता है और पिछले निश्चित- $K$ या धीमी-विचलन धारणाओं से आगे बढ़ता है।
एसिम्प्टोटिक पावर (Asymptotic Power): यह दिखाया गया है कि यह परीक्षण एसिम्प्टोटिक रूप से शक्तिशाली है, जहाँ स्टैटिस्टिक $H_1$ के तहत $O_p(n^{2/3})$ की दर से बढ़ता है, जो मौजूदा विधियों (जैसे, Han et al., 2023; Hu et al., 2021) से बेहतर प्रदर्शन करता है जिनकी विचलन दर धीमी है या जो विशिष्ट सेटिंग्स में शक्ति की कमी रखते हैं।

3.2 व्यावहारिक योगदान (Practical Contributions)

कोई ट्यूनिंग पैरामीटर नहीं: सबसैंपलिंग या बैंडविड्थ चयन की आवश्यकता वाली विधियों के विपरीत, यह विधि पूरी तरह से स्वचालित है (एक बार $K_{max}$ सेट होने के बाद)।
कंप्यूटेशनल दक्षता: इसके लिए केवल शीर्ष $K_{max} + 2$ आइगेनवैल्यू की गणना करने की आवश्यकता होती है, जिससे यह स्पार्स ग्राफ के लिए $O(n^2 K_{max})$ या उससे भी तेज़ हो जाता है, जबकि पूर्ण आइगेनडीकंपोजिशन या लाइकलीहुड-आधारित विधियों के लिए यह $O(n^3)$ है।
मजबूती (Robustness): जब तक $K_{max}$ एक उचित सीमा के भीतर है, यह विधि $K_{max}$ के चयन के प्रति मजबूत है।

4. परिणाम (Results)

4.1 सिमुलेशन अध्ययन (Simulation Studies)

लेखकों ने SBM, DCSBM और DCMM के तहत घने और विरल नेटवर्क पर इस विधि का परीक्षण किया।

साइज कंट्रोल (Size Control): प्रस्तावित विधि ( $T$ ) सभी सेटिंग्स में नाममात्र 5% स्तर के करीब अनुभवजन्य आकार (empirical sizes) बनाए रखती है। प्रतिस्पर्धी विधियों (जैसे, $T_{Lei}, T_{Hu}$ ) ने महत्वपूर्ण आकार विकृति (size distortions) दिखाई, विशेष रूप से जब $K$ बड़ा था या नेटवर्क विरल था।
पावर (Power): प्रस्तावित विधि ने लगभग सभी परिदृश्यों में, जहाँ $K > K_0$ था, लगभग 1 के करीब पावर प्राप्त की। प्रतिस्पर्धी विधियों (जैसे, $T_{Han}$ ) ने विरल सेटिंग्स में लगभग कोई पावर नहीं दिखाया, जबकि अन्य ( $T_{Hu}$ ) ने कम पावर या आकार विकृति दिखाई।
स्केलेबिलिटी (Scalability): $n=9,000$ के लिए भी प्रस्तावित विधि का गणना समय सेकंड के अंश से लेकर एकल-अंक सेकंड तक रहा, जबकि बूटस्ट्रैप-आधारित प्रतिस्पर्धियों को हजारों सेकंड लगे।

4.2 वास्तविक दुनिया के अनुप्रयोग (Real-World Applications)

पॉलिटिकल ब्लॉग नेटवर्क: इसने सही ढंग से $K=2$ (रूढ़िवादी बनाम उदारवादी) की पहचान की, जो ग्राउंड ट्रुथ के अनुरूप है। प्रतिस्पर्धी विधियाँ या तो $K=1$ को अस्वीकार करने में विफल रहीं या $K=2$ को अस्वीकार कर दिया।
सिना वीबो नेटवर्क: आपसी प्रभाव के आधार पर सही ढंग से $K=2$ समुदायों की पहचान की। प्रतिस्पर्धी विधियों ने $K=2$ के लिए शून्य परिकल्पना को गलत तरीके से अस्वीकार कर दिया।
गत $K=2$ (स्नातक वर्ष) की पहचान सफलतापूर्वक की, जो ऐसे नेटवर्क में है जहाँ अन्य एल्गोरिदम अक्सर विफल हो जाते हैं।

5. महत्व (Significance)

यह शोध पत्र जटिल नेटवर्क में समुदाय संख्या अनुमान के लिए एक एकीकृत, सैद्धांतिक रूप से कठोर और कंप्यूटेशनल रूप से कुशल समाधान प्रदान करता है।

अंतराल को भरना: यह घने और विरल नेटवर्क विश्लेषण के बीच, तथा निश्चित और विचलनशील समुदाय गणनाओं के बीच के अंतर को पाटता है।
व्यावहारिक उपयोगिता: पैरामीटर अनुमान और ट्यूनिंग की आवश्यकता को समाप्त करके, यह विविध प्रकार के नेटवर्क (सामाजिक, जैविक, वित्तीय) से निपटने वाले अभ्यासकर्ताओं के लिए एक "प्लग-एंड-प्ले" समाधान प्रदान करता है।
सैद्धांतिक आधार: विरल नेटवर्क में विचलनशील $K$ के लिए Tracy-Widom सीमा का व्युत्पन्न, नेटवर्क पर लागू उच्च-आयामी रैंडम मैट्रिक्स थ्योरी में नए मार्ग खोलता है।

भावी दिशाएं: लेखक अत्यंत विरल नेटवर्क (जहाँ वर्तमान शर्त विफल हो जाती है), नॉन-पैरामीट्रिक ग्राफिकल मॉडल और सहसंबद्ध बाइनरी नेटवर्क डेटा (लेटेंट स्पेस मॉडल) तक इस विधि के विस्तार का सुझाव देते हैं।