अधिकतम-एन्ट्रापी यादृच्छिक ग्राफ मॉडल

अधिकतम-एंट्रॉपी यादृच्छिक ग्राफ़ मॉडल यादृच्छिक ग्राफ़ मॉडल हैं जिनका उपयोग संरचनात्मक प्रतिबंध के एक समुच्चय के तहत अधिकतम एन्ट्रॉपी के सिद्धांत के अधीन जटिल नेटवर्क का अध्ययन करने के लिए किया जाता है, जो ग्लोबल, वितरणात्मक या स्थानीय हो सकता है।

अवलोकन

कोई भी यादृच्छिक ग्राफ़ मॉडल (पैरामीटर मानों के एक निश्चित समुच्चय पर) ग्राफ़ पर संभाव्यता वितरण का परिणाम देता है, और जो वितरण के विचारित वर्ग के भीतर अधिकतम एन्ट्रापी हैं, उनमें नेटवर्क अनुमान के लिए अधिकतम निष्पक्ष शून्य मॉडल होने की विशेष संपत्ति होती है ( उदाहरण के लिए जैविक नेटवर्क अनुमान)। प्रत्येक मॉडल आकार $n$ के ग्राफ़ के समुच्चय पर संभाव्यता वितरण के एक समूह को परिभाषित करता है (कुछ परिमित $n_{0}$ के लिए प्रत्येक $n>n_{0}$के लिए, $J$ वेधशालाओं $\{Q_{j}(G)\}_{j=1}^{J}$पर प्रतिबंध के संग्रह द्वारा पैरामीटरयुक्त) प्रत्येक ग्राफ $G$ के लिए परिभाषित किया गया है (जैसे निश्चित अपेक्षित औसत डिग्री, किसी विशेष रूप का डिग्री वितरण, या विशिष्ट डिग्री अनुक्रम), लैग्रेंज मल्टीप्लायरों की विधि द्वारा एन्ट्रापी अधिकतमकरण के साथ-साथ ग्राफ वितरण में लागू किया जाता है। ध्यान दें कि इस संदर्भ में "अधिकतम एन्ट्रॉपी" का तात्पर्य किसी एकल ग्राफ़ की एन्ट्रॉपी से नहीं है, बल्कि यादृच्छिक ग्राफ़ के पूरे संभाव्य समूह की एन्ट्रॉपी से है।

सामान्यतः अध्ययन किए जाने वाले कई यादृच्छिक नेटवर्क मॉडल अधिकतम एन्ट्रापी हैं, उदाहरण के लिए, ER ग्राफ़ $G(n,m)$और $G(n,p)$ (जिनमें से प्रत्येक में किनारों की संख्या पर एक ग्लोबल प्रतिबंध है), साथ ही कॉन्फ़िगरेशन मॉडल (CM) और सॉफ्ट कॉन्फ़िगरेशन मॉडल (एससीएम) (जिसमें प्रत्येक में $n$ स्थानीय प्रतिबंध हैं, प्रत्येक नोड-वार डिग्री-मान के लिए एक) हैं। ऊपर वर्णित मॉडलों के दो जोड़े में, एक महत्वपूर्ण अंतर यह है कि क्या प्रतिबंध शार्प है (यानी आकार के समुच्चय के प्रत्येक तत्व से संतुष्ट- $n$ ग्राफ़ संयोजन में गैर-शून्य संभावना के साथ), या सॉफ्ट (अर्थात संपूर्ण समूह औसतन संतुष्ट है)। पूर्व (शार्प) स्थिति एक माइक्रोकैनोनिकल समुच्चय से मेल खाता है, अधिकतम एन्ट्रापी की स्थिति जो सभी ग्राफ़ $G$ को संतुष्ट करती है $Q_{j}(G)=q_{j}\forall j$ समसंभाव्य के रूप में; बाद वाला (सॉफ्ट) स्थिति विहित है, जो एक घातीय यादृच्छिक ग्राफ मॉडल (ईआरजीएम) का निर्माण करता है।

मॉडल	प्रतिबंध प्रकार	प्रतिबंध चर	प्रायिकता वितरण
ER, $G(n,m)$	शार्प, ग्लोबल	कुल बढ़त-गणना $|E(G)|$	$1/{\binom {\binom {n}{2}}{m}};\ m=|E(G)|$
ER, $G(n,p)$	शार्प, ग्लोबल	अपेक्षित कुल बढ़त-गणना $|E(G)|$	$p^{|E(G)|}(1-p)^{{\binom {n}{2}}-|E(G)|}$
शार्प, लोकल	प्रत्येक शीर्ष की डिग्री,	प्रत्येक शीर्ष की डिग्री ${\displaystyle \{{\hat {k}}_{j}\}_{j=1}^{n}}$	${\displaystyle 1/\left\vert \Omega (\{{\hat {k}}_{j}\}_{j=1}^{n})\right\vert ;\Omega (\{k_{j}\}_{j=1}^{n})=\{g\in {\mathcal {G}}_{n}:k_{j}(g)={\hat {k}}_{j}\forall j\}\subset {\mathcal {G}}_{n}}$
सॉफ्ट, लोकल	प्रत्येक शीर्ष की अपेक्षित डिग्री,	प्रत्येक शीर्ष की अपेक्षित डिग्री ${\displaystyle \{{\hat {k}}_{j}\}_{j=1}^{n}}$	${\displaystyle Z^{-1}\exp \left[-\sum _{j=1}^{n}\psi _{j}k_{j}(G)\right];\ -{\frac {\partial \ln Z}{\partial \psi _{j}}}={\hat {k}}_{j}}$

ग्राफ़ का विहित समूह (सामान्य रूपरेखा)

मान लीजिए कि हम एक यादृच्छिक ग्राफ मॉडल का निर्माण कर रहे हैं जिसमें $n$ शीर्षों वाले सरल ग्राफ़ के समुच्चय ${\mathcal {G}}_{n}$पर संभाव्यता वितरण $\mathbb {P} (G)$ सम्मिलित है। इस समूह की गिब्स एन्ट्रॉपी $S[G]$ दी जाएगी

$S[G]=-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)\log \mathbb {P} (G).$

हम चाहते हैं कि अवलोकन योग्य वस्तुओं का समुच्चय-औसत मान $\{\langle Q_{j}\rangle \}_{j=1}^{J}$ $\{Q_{j}(G)\}_{j=1}^{J}$ (जैसे औसत डिग्री, औसत क्लस्टरिंग, या औसत सबसे छोटी पथ लंबाई) ट्यून करने योग्य हो, इसलिए हम ग्राफ़ वितरण पर $J$ "सॉफ्ट" प्रतिबंध लगाते हैं:

$\langle Q_{j}\rangle =\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)Q_{j}(G)=q_{j},$

जहाँ $j=1,...,J$ जे प्रतिबंधों को लेबल करें। वितरण $\mathbb {P} (G)$ को निर्धारित करने के लिए लैग्रेंज मल्टीप्लायरों की विधि का अनुप्रयोग जो $\langle Q_{j}\rangle =q_{j}$ को संतुष्ट करते हुए $S[G]$ को अधिकतम करता है, और सामान्यीकरण की स्थिति $\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)=1$ के परिणामस्वरूप निम्नलिखित परिणाम मिलते हैं:

$\mathbb {P} (G)={\frac {1}{Z}}\exp \left[-\sum _{j=1}^{J}\psi _{j}Q_{j}(G)\right],$

जहां $Z$ एक सामान्यीकृत स्थिरांक (विभाजन फ़ंक्शन) है और $\{\psi _{j}\}_{j=1}^{J}$ पैरामीटर (लैग्रेंज मल्टीप्लायर) हैं जो संगत रूप से अनुक्रमित ग्राफ़ अवलोकनों से जुड़े होते हैं, जिन्हें उन गुणों के वांछित मानों के साथ ग्राफ़ नमूने प्राप्त करने के लिए ट्यून किया जा सकता है। औसत; परिणाम एक घातीय समूह और विहित पहनावा है; विशेष रूप से एक ईआरजीएम उत्पन्न करना।

एर्डोस-रेनी मॉडल $G(n,m)$

उपरोक्त विहित ढांचे में, संयोजन-औसत मात्राओं $\langle Q_{j}\rangle$ पर प्रतिबंध लगाए गए थे। हालाँकि ये गुण औसतन $\{\psi _{j}\}_{j=1}^{J}$ की उचित सेटिंग द्वारा निर्दिष्ट मानों पर आधारित होंगे, प्रत्येक विशिष्ट उदाहरण $G$ में $Q_{j}(G)\neq q_{j}$ हो सकता है, जो अवांछनीय हो सकता है। इसके बजाय, हम अधिक सख्त शर्त लगा सकते हैं: गैर-शून्य संभावना वाले प्रत्येक ग्राफ को $Q_{j}(G)=q_{j}$ को बिल्कुल संतुष्ट करना होगा। इन "तीव्र" प्रतिबंधों के तहत, अधिकतम एन्ट्रापी वितरण निर्धारित किया जाता है। हम इसका उदाहरण एर्डोस-रेनी मॉडल $G(n,m)$ से देते हैं।

$G(n,m)$ में तीव्र प्रतिबंध $m$ किनारों की एक निश्चित संख्या है, जो कि $|\operatorname {E} (G)|=m$ है, संयोजन से खींचे गए सभी ग्राफ़ $G$ के लिए (संभावना के साथ तत्काल $\mathbb {P} _{n,m}(G)$ दर्शाया गया है। यह ${\mathcal {G}}_{n}$से नमूना स्थान को प्रतिबंधित करता है। ($n$ शीर्षों पर सभी ग्राफ़) उपसमुच्चय ${\mathcal {G}}_{n,m}=\{g\in {\mathcal {G}}_{n};|\operatorname {E} (g)|=m\}\subset {\mathcal {G}}_{n}$ तक। यह चिरसम्मत सांख्यिकीय यांत्रिकी में माइक्रोकैनोनिकल संयोजन के सीधे सादृश्य में है, जिसमें सिस्टम एक विशेष ऊर्जा मूल्य के सभी अवस्थाओं के चरण स्थान में एक पतली विविधता तक सीमित है।

हमारे नमूना स्थान को ${\mathcal {G}}_{n,m}$ तक सीमित करने पर, हमारे पास संतुष्ट करने के लिए कोई बाहरी बाधा (सामान्यीकरण के अलावा) नहीं है, और इस प्रकार हम लैग्रेंज मल्टीप्लायरों का उपयोग किए बिना $S[G]$ को अधिकतम करने के लिए $\mathbb {P} _{n,m}(G)$ का चयन करेंगे। यह सर्वविदित है कि बाहरी प्रतिबंधों की अनुपस्थिति में एन्ट्रापी-अधिकतम वितरण नमूना स्थान पर समान वितरण है (अधिकतम एन्ट्रापी संभाव्यता वितरण देखें), जिससे हम प्राप्त करते हैं:

$\mathbb {P} _{n,m}(G)={\frac {1}{|{\mathcal {G}}_{n,m}|}}={\binom {\binom {n}{2}}{m}}^{-1},$

जहां द्विपद गुणांक के संदर्भ में अंतिम अभिव्यक्ति संभव किनारों के बीच ${\binom {n}{2}}$ किनारों को रखने के विधियों की संख्या है, और इस प्रकार ${\mathcal {G}}_{n,m}$, $m$ की प्रमुखता है।

सामान्यीकरण

सरल रेखांकन के सामान्यीकरण पर विभिन्न प्रकार के अधिकतम-एन्ट्रॉपी संयोजनों का अध्ययन किया गया है। उदाहरण के लिए, सरल समूहों का समुच्चय, और किसी दिए गए अपेक्षित डिग्री अनुक्रम के साथ भारित यादृच्छिक ग्राफ़ इनमें सम्मिलित हैं।

यह भी देखें

• अधिकतम एन्ट्रापी का सिद्धांत
• अधिकतम एन्ट्रापी संभाव्यता वितरण
• लैग्रेंज मल्टीप्लायरों की विधि
• शून्य मॉडल
• यादृच्छिक ग्राफ
• घातीय यादृच्छिक ग्राफ मॉडल
• विहित समुच्चय
• माइक्रोकैनोनिकल समुच्चय