🔬 physics

Information theory for hypergraph similarity

यह शोधपत्र एक सामान्य सूचना-सैद्धांतिक ढांचे (information-theoretic framework) को प्रस्तुत करता है जो सार्थक उच्च-क्रम अंतःक्रियाओं (higher-order interactions) को कैप्चर करके और एक सामान्यीकृत पारस्परिक सूचना माप (normalized mutual information measure) के माध्यम से भ्रामक सहसंबंधों को सुधारकर हाइपरग्राफ की सिद्धांतपूर्ण तुलना करने में सक्षम बनाता है।

मूल लेखक: Helcio Felippe, Alec Kirkley, Federico Battiston

प्रकाशित 2026-06-12

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

CC BY 4.0

मूल लेखक: Helcio Felippe, Alec Kirkley, Federico Battiston

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

कल्पना कीजिए कि आप दो जटिल सामाजिक समूहों की तुलना करने की कोशिश कर रहे हैं, जैसे दो अलग-अलग परिवार या सहकर्मियों की दो अलग-अलग टीमें।

पुराना तरीका (ग्राफ्स):
पारंपरिक रूप से, वैज्ञानिकों ने इन समूहों को केवल यह देखकर देखा है कि कौन किससे दोस्ती रखता है। वे व्यक्ति A और व्यक्ति B के बीच एक रेखा खींचते हैं यदि वे बात करते हैं। यह एक समूह फोटो को देखने जैसा है और केवल यह गिनने जैसा है कि कितने लोग ठीक एक अन्य व्यक्ति का हाथ थामे हुए हैं। यह एक सरल, दो-व्यक्ति (dyadic) दृष्टिकोण है। लेकिन वास्तविक जीवन में, लोग अक्सर बड़े समूहों में बातचीत करते हैं—जैसे तीन दोस्तों का कॉफी पीना, एक पूरी समिति की बैठक, या एक पारिवारिक रात्रिभोज। पुराना तरीका इन "ग्रुप हग्स" (समूहों के मेलजोल) को छोड़ देता है।

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

समस्या:
वैज्ञानिकों को दो अलग-अलग हाइपरग्राफ्स (बुलबुलों के दो अलग समूह) की तुलना करने में कठिनाई हुई है।

कुछ पुराने तरीके बहुत संवेदनशील थे; यदि आपने एक छोटा सा विवरण भी बदल दिया, तो पूरी तुलना टूट जाती थी।
अन्य तरीके बहुत धीमे थे; उन्हें गणना करने में बहुत समय लगता था, जैसे समुद्र तट पर रेत के हर कण को एक-एक करके गिनने की कोशिश करना।
कई तरीके यह अंतर नहीं बता पाते थे कि एक वास्तविक संबंध असली है या महज एक संयोग। यदि दो समूहों में संयोग से कुछ लोग समान होते थे, तो पुराने उपकरण कहते थे, "अरे, ये समूह समान हैं!" भले ही वे पूरी तरह से अलग हों।

समाधान: "कंप्रेशन" (संपीड़न) सादृश्य
लेखकों ने सूचना सिद्धांत (Information Theory) पर आधारित एक नया टूल बनाया है, विशेष रूप से न्यूनतम विवरण लंबाई (Minimum Description Length - MDL) की एक अवधारणा पर।

इसे समझने का सबसे अच्छा तरीका यह है: कल्पना कीजिए कि आप फोन पर अपने मित्र को एक जटिल लेगो (Lego) महल का वर्णन करने की कोशिश कर रहे हैं ताकि वे बिल्कुल वैसा ही महल बना सकें।

लक्ष्य: आप काम पूरा करने के लिए कम से कम शब्दों का (सबसे छोटा "विवरण") उपयोग करना चाहते हैं।
नुस्खा: यदि आपके मित्र को पहले से ही महल के पहले आधे हिस्से के बारे में पता है, तो आपको उन हिस्सों को फिर से वर्णित करने की आवश्यकता नहीं है। आपको केवल नए हिस्सों का वर्णन करने की आवश्यकता है।
माप: यदि आप दूसरे महल का वर्णन बहुत जल्दी कर सकते हैं क्योंकि आपके मित्र को पहले वाले के बारे में पहले से पता है, तो दोनों महल बहुत समान हैं। यदि आपको दूसरा महल वर्णित करने के लिए पूरी एक नई किताब लिखनी पड़ती है, तो वे बहुत भिन्न हैं।

यह शोध पत्र इसी तर्क का उपयोग करके हाइपरग्राफ्स के लिए एक "शब्दकोश" बनाता है। वे पूछते हैं: "यदि मैं आपको समूह B का वर्णन करने से पहले समूह A के बारे में बताता हूँ, तो मैं सूचना के कितने बिट्स बचाता हूँ?"

तुलना के तीन स्तर
लेखकों ने इसे करने के तीन तरीकों का एक "पदानुक्रम" (hierarchy) बनाया है, जो अधिक परिष्कृत होते जा रहे हैं:

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

सादृश्य: यदि आप जानते हैं कि एक पांच सदस्यों वाला परिवार (माँ, पिता और तीन बच्चे) रात का खाना खा रहा है, तो आप स्वतः ही जानते हैं कि "माँ और पिता" की जोड़ी भी रात का खाना खा रही है। आपको उस जोड़ी को अलग से सूचीबद्ध करने की आवश्यकता नहीं है; बड़ा समूह छोटे समूह को अपने भीतर समाहित करता है।
"क्रॉस" विधि इन "नेस्टेड" (एक के भीतर एक) संबंधों को खोजती है। यह पूछती है: "क्या नेटवर्क A का बड़ा समूह नेटवर्क B के छोटे समूह की व्याख्या करता है?" यह उन समानताओं को खोजने की अनुमति देता है जिन्हें अन्य विधियाँ पूरी तरह से मिस कर देती हैं।

उन्होंने क्या पाया
लेखकों ने इसे नकली डेटा (यह सुनिश्चित करने के लिए कि यह काम करता है) और वास्तविक डेटा (यह देखने के लिए कि यह उपयोगी है) पर परखा।

नकली डेटा: उन्होंने यादृच्छिक समूह बनाए और उनमें "शोर" (रैंडम बदलाव) जोड़ा। उनके नए टूल ने सही ढंग से कहा, "ये अलग हैं," भले ही समूह बहुत बड़े और विरल (sparse) थे। पुराने उपकरण अक्सर संयोग से होने वाली चीजों से धोखा खा जाते थे।
वास्तविक डेटा: उन्होंने तीन वास्तविक उदाहरण देखे:
1. वैज्ञानिक: भौतिकी के क्षेत्रों की तुलना करना। उन्होंने पाया कि "न्यूक्लियर फिजिक्स" और "पार्टिकल फिजिक्स" बहुत समान हैं (उनके बीच कई समूह अंतःक्रियाएं साझा हैं), जबकि "गैस फिजिक्स" काफी अलग है।
2. फिल्में: मूवी जॉनर (genres) की तुलना करना। उन्होंने पाया कि अभिनेताओं के समूह बनाने के तरीके में "थ्रिलर" और "ड्रामा" समान हैं, लेकिन "डॉक्यूमेंट्री" पूरी तरह से अलग है (क्योंकि डॉक्स में लोगों के व्यवहार का तरीका अद्वितीय होता है)।
3. सॉफ्टवेयर: कोडिंग टीमों की तुलना करना। उन्होंने पाया कि "कमांड लाइन्स," "डेवलपमेंट," और "डेटा स्ट्रक्चर्स" के उपकरण बहुत समान हैं क्योंकि वे समान सहयोग पैटर्न साझा करते हैं।

निष्कर्ष
यह शोध पत्र वैज्ञानिकों को जटिल समूहों की समानता मापने के लिए एक नया, निष्पक्ष और तेज़ पैमाना प्रदान करता है। यह केवल यह नहीं गिनता कि कौन किसे जानता है; यह समझता है कि लोग विभिन्न आकारों की टीमों में मिलकर कैसे काम करते हैं, और यह वास्तविक संबंध और एक भाग्यशाली संयोग के बीच अंतर कर सकता है। यह भीड़ की ब्लैक-एंड-व्हाइट फोटो से अपग्रेड होकर एक हाई-डेफिनिशन 3D वीडियो की तरह है जो दिखाता है कि समूह वास्तव में कैसे चलते हैं और परस्पर क्रिया करते हैं।

तकनीकी सारांश: हाइपरग्राफ समानता के लिए सूचना सिद्धांत

समस्या विवरण
नेटवर्क प्रणालियों की तुलना करना क्लस्टरिंग, वर्गीकरण और विसंगति का पता लगाने जैसे कार्यों के लिए मौलिक है। जबकि द्वि-आधारी (pairwise) अंतःक्रियाओं वाले ग्राफों के लिए पारंपरिक नेटवर्क समानता माप अच्छी तरह से विकसित हैं, वे उन जटिल प्रणालियों की गतिशीलता को पकड़ने में विफल रहते हैं जहाँ अंतःक्रियाओं में दो से अधिक नोड्स के समूह शामिल होते हैं (उच्च-क्रम की अंतःक्रियाएं)। हाइपरग्राफ (ग्राफ का सामान्यीकरण जिसमें किसी भी संख्या में नोड्स वाले किनारे/edges होते हैं) की तुलना करने वाली मौजूदा विधियाँ महत्वपूर्ण सीमाओं का सामना करती हैं: कई विधियाँ ट्यून करने योग्य मापदंडों (parameters) पर निर्भर करती हैं जिनके प्रति परिणाम अत्यधिक संवेदनशील होते हैं, जबकि अन्य (स्पेक्ट्रल गुणों, पथ लंबाई या ग्राफलेट्स पर आधारित) ऐसी कम्प्यूटेशनल जटिलताएँ लागू करती हैं जो नेटवर्क के आकार के साथ खराब रूप से स्केल करती हैं (कम से कम द्विघाती रूप से)। इसके अलावा, कई वर्तमान दृष्टिकोण स्पष्ट मौलिक सिद्धांतों के बिना 'एड हॉक' (ad hoc) संरचनात्मक विशेषताओं को शामिल करते हैं, जिससे परिणामों की व्याख्या करना कठिन हो जाता है और वे विभिन्न डोमेन में सामान्यीकृत नहीं हो पाते हैं। उच्च-क्रम वाले नेटवर्क में संरचनात्मक ओवरलैप को मापने के लिए एक सिद्धांत-आधारित, गैर-पैरामीट्रिक ढांचे की आवश्यकता है जो सांख्यिकीय शोर और किनारे के घनत्व से उत्पन्न होने वाले स्पूरियस (spurious) सहसंबंधों को ठीक कर सके।

कार्यप्रणाली
लेखक न्यूनतम विवरण लंबाई (Minimum Description Length - MDL) सिद्धांत पर आधारित हाइपरग्राफ समानता के लिए एक सामान्य सूचना-सैद्धांतिक ढांचा तैयार करते हैं। मुख्य विचार यह है कि दो हाइपरग्राफ, $G_1$ और $G_2$ , के बीच समानता को इस मात्रा द्वारा मापा जाता है कि एक हाइपरग्राफ को दूसरे के ज्ञान और उनके संरचनात्मक ओवरलैप के आधार पर प्रसारित करने में कितनी सूचना बचती है।

सूचना-सैद्धांतिक सूत्रीकरण:
ढांचा विशिष्ट एन्कोडिंग योजनाओं ( $c$ ) के आधार पर एंट्रॉपी ( $H_c$ ) और कंडीशनल एंट्रॉपी ( $H_c(G_j|G_i)$ ) को परिभाषित करता है। म्यूचुअल इंफॉर्मेशन (MI) को $MI_c(G_1; G_2) = H_c(G_2) - H_c(G_2|G_1)$ के रूप में गणना किया जाता है। एक समान पैमाने को सुनिश्चित करने के लिए, इसे $[0, 1]$ की सीमा में एक नॉर्मलाइज्ड म्यूचुअल इंफॉर्मेशन (NMI) स्कोर में सामान्यीकृत किया जाता है, जिसे निम्नानुसार परिभाषित किया गया है:
$NMI_c(G_1, G_2) = 1 - \min \left\{ \frac{H_c(G_2|G_1)}{H_c(G_2)}, \frac{H_c(G_1|G_2)}{H_c(G_1)} \right\}$
यह सूत्रीकरण एन्कोडिंग प्रक्रिया में विषमता (asymmetry) की अनुमति देता है, जो नेस्टेड (nested) संरचनाओं को संभालने के लिए महत्वपूर्ण है जहाँ उच्च-क्रम के किनारों से निम्न-क्रम के किनारों को प्रसारित करना सूचनात्मक रूप से सस्ता होता है।
एन्कोडिंग का पदानुक्रम (Hierarchy of Encodings):
लेखक विभिन्न पहलुओं को पकड़ने के लिए तीन विशिष्ट एन्कोडिंग का एक पदानुक्रम प्रस्तावित करते हैं:

$NMI_{bulk}$ : सभी हाइपर-किनारों को एक साथ प्रसारित करता है। यह इंट्रा-ऑर्डर (intra-order) समानता को पकड़ता है, लेकिन वास्तविक दुनिया के स्पार्स (sparse) हाइपरग्राफ के लिए यह अक्षम है, क्योंकि यह संभावित हाइपर-किनारों के विशाल स्थान के कारण समानता स्कोर को बढ़ा देता है।
$NMI_{align}$ : हाइपर-किनारों को परत-दर-परत (क्रम $\ell$ द्वारा) प्रसारित करता है, केवल समान क्रम की परतों की तुलना करता है। यह परतों के बीच विषम घनत्वों को ठीक करता है और सांख्यिकीय शोर के प्रति मजबूत है, लेकिन क्रॉस-ऑर्डर (cross-order) समानताओं को पकड़ने में विफल रहता है।
$NMI_{cross}$ : सबसे लचीला माप, यह संदर्भ हाइपरग्राफ से किसी भी उच्च-क्रम की परत $G^{(k)}_i$ (जहाँ $k \ge \ell$ ) का उपयोग करके एक परत $G^{(\ell)}_j$ को प्रसारित करने की अनुमति देता है। यह इंट्रा-ऑर्डर और क्रॉस-ऑर्डर समानता (नेस्टेडनेस) दोनों को पकड़ता है। यह बड़े सिस्टमों के लिए स्केलेबिलिटी सक्षम करने हेतु एक रिकर्सिव एल्गोरिदम का उपयोग करता है जो सभी सब-टुपल्स (sub-tuples) को स्पष्ट रूप से उत्पन्न किए बिना ओवरलैप की गणना करता है।

बहु-स्तरीय विस्तार (Multiscale Extension):
इस ढांचे को नोड्स को पार्टिशन (जैसे समुदायों) में मोटे तौर पर वर्गीकृत (coarse-graining) करके मल्टीस्केल समानता के लिए विस्तारित किया गया है। यह हाइपरग्राफ की मैक्रो-स्केल पर तुलना करने, यानी मॉड्यूलर संरचना में समानता का आकलन करने की अनुमति देता है, भले ही व्यक्तिगत हाइपर-किनारे ओवरलैप न हों।

प्रमुख योगदान

सिद्धांत-आधारित ढांचा: हाइपरग्राफ तुलना के लिए एक गैर-पैरामीट्रिक, सूचना-सैद्धांतिक आधार की शुरुआत जो मनमाने पैरामीटर ट्यूनिंग से बचता है।
मापों का पदानुक्रम: NMI मापों ( $NMI_{bulk}$ , $NMI_{align}$ , $NMI_{cross}$ ) का व्युत्पन्न जो क्रमिक रूप से सूक्ष्म संरचनात्मक ओवरलैप, जिसमें क्रॉस-ऑर्डर इंटरैक्शन और नेस्टेडनेस शामिल है, को कैप्चर करते हैं।
कम्प्यूटेशनल दक्षता: $NMI_{cross}$ के लिए एक रिकर्सिव काउंटिंग स्कीम का विकास जो प्रत्यक्ष प्रोजेक्शन के कॉम्बिनेटोरियल विस्फोट (combinatorial explosion) से बचता है, जिससे लाखों नोड्स और बड़े हाइपर-एज ऑर्डर वाले हाइपरग्राफ की कुशल तुलना संभव होती है।
स्पूरियस सहसंबंधों का सुधार: यह विधि उन स्पूरियस ओवरलैप्स को स्वाभाविक रूप से ठीक करती है जो उच्च किनारे घनत्व या विषम परत घनत्व के कारण उत्पन्न होते हैं, जो सरल ओवरलैप-आधारित मेट्रिक्स के लिए समस्या पैदा करते हैं।

परिणाम
लेखक सिंथेटिक और अनुभवजन्य डेटा पर व्यापक प्रयोगों के माध्यम से ढांचे को मान्य करते हैं:

सिंथेटिक इंट्रा-ऑर्डर समानता: रैंडम हाइपरग्राफ के प्रयोगों में, $NMI_{align}$ विषम परत घनत्वों में सार्थक ओवरलैप को शोर से सफलतापूर्वक अलग करता है, जबकि $N_B$ घनत्व प्रभावों के कारण उच्च-शोर वाले शासन (regimes) में समानता स्कोर को बढ़ा देता है।
सिंथेटिक क्रॉस-ऑर्डर समानता: "ब्लॉक-नेस्टेड" हाइपरग्राफ का उपयोग करते हुए, जहाँ परतें विभिन्न ऑर्डर्स में नेस्टेड हैं, $NMI_{cross}$ संरचनात्मक समानता का पता लगाने में सफल रहता है भले ही इंट्रा-ऑर्डर समानता नष्ट हो गई हो। इसके विपरीत, $NMI_{align}$ इन क्रॉस-ऑर्डर संबंधों का पता लगाने में विफल रहता है और शून्य के करीब समानता दिखाता है।
अनुभवजन्य अनुप्रयोग (Empirical Applications): इस ढांचे को तीन वास्तविक दुनिया के मल्टीप्लेक्स हाइपरग्राफ पर लागू किया गया है:
- फिजिक्स कोलैबोरेशन (APS): संरचनात्मक रूप से संबंधित क्षेत्रों (जैसे न्यूक्लियर और एलीमेंट्री पार्टिकल फिजिक्स) के बीच उच्च समानता और विजातीय क्षेत्रों के बीच असमानता को प्रकट करता है।
- फिल्म उद्योग (IMDb): उन शैलियों के बीच उच्च समानता की पहचान करता है जिनकी सीमाएं धुंधली हैं (जैसे थ्रिलर और ड्रामा) और मौलिक रूप से भिन्न प्रारूपों (जैसे डॉक्यूमेंट्री) के बीच कम समानता की पहचान करता है।
- सॉफ्टवेयर डेवलपमेंट (Rust): सहयोग पैटर्न के आधार पर रिपॉजिटरी श्रेणियों (जैसे कमांड लाइन यूटिलिटीज और डेवलपमेंट टूल्स) के बीच कार्यात्मक समानता का पता लगाता है।
विसंगति का पता लगाना (Anomaly Detection): एनरॉन (Enron) ईमेल डेटा के टेम्पोरल हाइपरग्राफ पर लागू करने पर, यह संरचनात्मक विसंगतियों और संगठनात्मक बदलावों का पता लगाता है जिन्हें द्वि-आधारी ग्राफ समानता उपाय मिस कर देते हैं, जो उच्च-क्रम की गतिशीलता के महत्व को दर्शाता है।
गतिक प्रासंगिकता (Dynamical Relevance): SIS कंटाजियन प्रक्रियाओं के साथ प्रयोगों से पता चलता है कि $NMI_{cross}$ स्कोर महामारी की दहलीज (epidemic threshold) के साथ सह-संबंधित है; नेस्टेड संदर्भ के साथ उच्च संरचनात्मक समानता वाले हाइपरग्राफ में महामारी का आगमन जल्दी होता है, जो संरचनात्मक समानता को गतिशील व्यवहार से जोड़ता है।

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

इसी तरह के और पेपर