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

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

अवलोकन

कोई भी यादृच्छिक ग्राफ़ मॉडल (पैरामीटर मानों के एक निश्चित सेट पर) ग्राफ़ पर संभाव्यता वितरण का परिणाम देता है, और जो वितरण के विचारित वर्ग के भीतर अधिकतम एन्ट्रापी हैं, उनमें नेटवर्क अनुमान के लिए अधिकतम निष्पक्ष शून्य मॉडल होने की विशेष संपत्ति होती है ( उदाहरण के लिए जैविक नेटवर्क अनुमान)। प्रत्येक मॉडल आकार $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$ समसंभाव्य के रूप में; बाद वाला (सॉफ्ट) मामला विहित है, जो एक घातीय यादृच्छिक ग्राफ मॉडल (ईआरजीएम) का निर्माण करता है।

Model	Constraint type	Constraint variable	Probability distribution
ER, $G(n,m)$	Sharp, global	Total edge-count $|E(G)|$	$1/{\binom {\binom {n}{2}}{m}};\ m=|E(G)|$
ER, $G(n,p)$	Soft, global	Expected total edge-count $|E(G)|$	$p^{|E(G)|}(1-p)^{{\binom {n}{2}}-|E(G)|}$
तीव्र, स्थानीय	प्रत्येक शीर्ष की डिग्री, गणित>\{\टोपी{k}_j\}_{j=1}^n</math> || गणित>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 {जी}_एन</गणित>
सॉफ्ट, स्थानीय	प्रत्येक शीर्ष की अपेक्षित डिग्री, गणित>\{\टोपी{k}_j\}_{j=1}^n</math> || गणित>Z^{-1}\exp\left[-\sum_{j=1}^n\psi_ j k j(G)\wright]; \ -\frac{\आंशिक\ln Z}{\आंशिक \psi j} = \hat{k}_j </math>

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

मान लीजिए कि हम संभाव्यता वितरण से युक्त एक यादृच्छिक ग्राफ़ मॉडल बना रहे हैं $\mathbb {P} (G)$ मंच पर ${\mathcal {G}}_{n}$ ग्राफ़ का (असतत गणित)#सरल ग्राफ़ के साथ $n$ शिखर. एन्ट्रॉपी (सांख्यिकीय थर्मोडायनामिक्स)#गिब्स एन्ट्रॉपी फॉर्मूला $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)$ वह अधिकतम होता है $S[G]$ संतुष्ट करते हुए $\langle Q_{j}\rangle =q_{j}$, और सामान्यीकरण की स्थिति $\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}$, हमारे पास संतुष्ट करने के लिए (सामान्यीकरण के अलावा) कोई बाहरी बाधा नहीं है, और इस प्रकार हम चयन करेंगे $\mathbb {P} _{n,m}(G)$ बढ़ाने के लिए $S[G]$ लैग्रेंज मल्टीप्लायरों का उपयोग किए बिना। यह सर्वविदित है कि बाहरी बाधाओं की अनुपस्थिति में एन्ट्रापी-अधिकतम वितरण नमूना स्थान पर असतत समान वितरण है (अधिकतम एन्ट्रापी संभाव्यता वितरण देखें), जिससे हम प्राप्त करते हैं:

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

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

सामान्यीकरण

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

यह भी देखें

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