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

Revision as of 09:36, 5 December 2023

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

अवलोकन

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

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

मॉडल	प्रतिबंध प्रकार	प्रतिबंध चर	प्रायिकता वितरण
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$ के परिणामस्वरूप निम्नलिखित परिणाम मिलते हैं:^[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$ किनारों की एक निश्चित संख्या है, ^[8] जो कि $|\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$ की प्रमुखता है।

सामान्यीकरण

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

यह भी देखें

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

संदर्भ

↑ ^1.0 ^1.1 Park, Juyong; M.E.J. Newman (2004-05-25). "The statistical mechanics of networks". arXiv:cond-mat/0405566.
↑ van der Hoorn, Pim; Gabor Lippner; Dmitri Krioukov (2017-10-10). "Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution". arXiv:1705.10261.
↑ Newman, Mark (2010). Networks: An Introduction - Oxford Scholarship. doi:10.1093/acprof:oso/9780199206650.001.0001. ISBN 9780199206650. Archived from the original on 2023-02-04. Retrieved 2018-09-13.
↑ Garlaschelli, Diego; den Hollander, Frank; Roccaverde, Andrea (2018-07-13). "यादृच्छिक ग्राफ़ में समतुल्यता को तोड़ने के पीछे सहप्रसरण संरचना". Journal of Statistical Physics. 173 (3–4): 644–662. arXiv:1711.04273. Bibcode:2018JSP...173..644G. doi:10.1007/s10955-018-2114-x. ISSN 0022-4715.
↑ Roccaverde, Andrea (August 2018). "Is breaking of ensemble equivalence monotone in the number of constraints?". Indagationes Mathematicae. 30: 7–25. arXiv:1807.02791. doi:10.1016/j.indag.2018.08.001. ISSN 0019-3577.
↑ Bianconi, G. (2018-08-21). Multilayer Networks: Structure and Function. Oxford University Press. ISBN 9780198753919. Archived from the original on 2023-02-04. Retrieved 2018-09-13.
↑ Anand, K.; Bianconi, G. (2009). "Entropy measures for networks: Toward an information theory of complex topologies". Physical Review E. 80 (4): 045102. arXiv:0907.1514. Bibcode:2009PhRvE..80d5102A. doi:10.1103/PhysRevE.80.045102. PMID 19905379.
↑ Erdős, P.; Rényi, A. (1959). "On Random Graphs. I" (PDF). Publicationes Mathematicae. 6: 290–297. Archived (PDF) from the original on 2020-08-07. Retrieved 2018-09-13.
↑ Zuev, Konstantin; Or Eisenberg; Dmitri Krioukov (2015-10-29). "Exponential Random Simplicial Complexes". arXiv:1502.05032.
↑ Hillar, Christopher; Andre Wibisono (2013-08-26). "Maximum entropy distributions on graphs". arXiv:1301.3321.

[Park-1] 1.0 ^1.1 Park, Juyong; M.E.J. Newman (2004-05-25). "The statistical mechanics of networks". arXiv:cond-mat/0405566.

[van_der_Hoorn-2] van der Hoorn, Pim; Gabor Lippner; Dmitri Krioukov (2017-10-10). "Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution". arXiv:1705.10261.

[Newman_2010-3] Newman, Mark (2010). Networks: An Introduction - Oxford Scholarship. doi:10.1093/acprof:oso/9780199206650.001.0001. ISBN 9780199206650. Archived from the original on 2023-02-04. Retrieved 2018-09-13.

[4] Garlaschelli, Diego; den Hollander, Frank; Roccaverde, Andrea (2018-07-13). "यादृच्छिक ग्राफ़ में समतुल्यता को तोड़ने के पीछे सहप्रसरण संरचना". Journal of Statistical Physics. 173 (3–4): 644–662. arXiv:1711.04273. Bibcode:2018JSP...173..644G. doi:10.1007/s10955-018-2114-x. ISSN 0022-4715.

[5] Roccaverde, Andrea (August 2018). "Is breaking of ensemble equivalence monotone in the number of constraints?". Indagationes Mathematicae. 30: 7–25. arXiv:1807.02791. doi:10.1016/j.indag.2018.08.001. ISSN 0019-3577.

[6] Bianconi, G. (2018-08-21). Multilayer Networks: Structure and Function. Oxford University Press. ISBN 9780198753919. Archived from the original on 2023-02-04. Retrieved 2018-09-13.

[Anand-7] Anand, K.; Bianconi, G. (2009). "Entropy measures for networks: Toward an information theory of complex topologies". Physical Review E. 80 (4): 045102. arXiv:0907.1514. Bibcode:2009PhRvE..80d5102A. doi:10.1103/PhysRevE.80.045102. PMID 19905379.

[ER-8] Erdős, P.; Rényi, A. (1959). "On Random Graphs. I" (PDF). Publicationes Mathematicae. 6: 290–297. Archived (PDF) from the original on 2020-08-07. Retrieved 2018-09-13.

[Zuev-9] Zuev, Konstantin; Or Eisenberg; Dmitri Krioukov (2015-10-29). "Exponential Random Simplicial Complexes". arXiv:1502.05032.

[Hillar-10] Hillar, Christopher; Andre Wibisono (2013-08-26). "Maximum entropy distributions on graphs". arXiv:1301.3321.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 19: / Line 19: @@
 |arxiv = 1705.10261}}</ref> ( उदाहरण के लिए जैविक नेटवर्क अनुमान)। प्रत्येक मॉडल आकार <math>n</math> के ग्राफ़ के सेट पर संभाव्यता वितरण के एक समूह को परिभाषित करता है (कुछ परिमित <math>n_0</math> के लिए प्रत्येक <math>n>n_0</math>के लिए, <math>J</math> वेधशालाओं <math>\{Q_j(G)\}_{j=1}^J</math>पर प्रतिबंध के संग्रह द्वारा पैरामीटरयुक्त) प्रत्येक ग्राफ <math>G</math> के लिए परिभाषित किया गया है (जैसे निश्चित अपेक्षित औसत डिग्री, किसी विशेष रूप का डिग्री वितरण, या विशिष्ट डिग्री अनुक्रम), लैग्रेंज मल्टीप्लायरों की विधि द्वारा एन्ट्रापी अधिकतमकरण के साथ-साथ ग्राफ वितरण में लागू किया जाता है। ध्यान दें कि इस संदर्भ में "अधिकतम एन्ट्रॉपी" का तात्पर्य किसी एकल ग्राफ़ की एन्ट्रॉपी से नहीं है, बल्कि यादृच्छिक ग्राफ़ के पूरे संभाव्य समूह की एन्ट्रॉपी से है।
-आमतौर पर अध्ययन किए जाने वाले कई यादृच्छिक नेटवर्क मॉडल अधिकतम एन्ट्रापी हैं, उदाहरण के लिए, ER ग्राफ़ <math>G(n,m)</math>और <math>G(n,p)</math> (जिनमें से प्रत्येक में किनारों की संख्या पर एक वैश्विक प्रतिबंध है), साथ ही कॉन्फ़िगरेशन मॉडल (CM)<ref name="Newman 2010">{{cite book|title=Networks: An Introduction - Oxford Scholarship|last=Newman|first=Mark|doi=10.1093/acprof:oso/9780199206650.001.0001|year=2010|isbn=9780199206650|url=https://cds.cern.ch/record/1281254|access-date=2018-09-13|archive-date=2023-02-04|archive-url=https://web.archive.org/web/20230204160415/https://catalogue.library.cern/legacy/1281254|url-status=live}}</ref> और सॉफ्ट कॉन्फ़िगरेशन मॉडल (एससीएम) (जिसमें प्रत्येक में <math>n</math> स्थानीय बाधाएं हैं, प्रत्येक नोड-वार डिग्री-मान के लिए एक) हैं। ऊपर वर्णित मॉडलों के दो जोड़े में, एक महत्वपूर्ण अंतर <ref>{{cite journal|last=Garlaschelli|first=Diego|last2=den Hollander|first2=Frank|last3=Roccaverde|first3=Andrea|date=2018-07-13|title=यादृच्छिक ग्राफ़ में समतुल्यता को तोड़ने के पीछे सहप्रसरण संरचना|journal=Journal of Statistical Physics|volume=173|issue=3–4|pages=644–662|doi=10.1007/s10955-018-2114-x|issn=0022-4715|arxiv=1711.04273|bibcode=2018JSP...173..644G}}</ref><ref>{{cite journal|last=Roccaverde|first=Andrea|date=August 2018|title=Is breaking of ensemble equivalence monotone in the number of constraints?|journal=Indagationes Mathematicae|volume=30|pages=7–25|doi=10.1016/j.indag.2018.08.001|issn=0019-3577|arxiv=1807.02791}}</ref> यह है कि क्या प्रतिबंध तेज है (यानी आकार के सेट के प्रत्येक तत्व से संतुष्ट- <math>n</math> ग्राफ़ संयोजन में गैर-शून्य संभावना के साथ), या सॉफ्ट (अर्थात संपूर्ण समूह औसतन संतुष्ट है)। पूर्व (तेज) मामला एक माइक्रोकैनोनिकल समुच्चय से मेल खाता है,<ref>{{cite book
+सामान्यतः अध्ययन किए जाने वाले कई यादृच्छिक नेटवर्क मॉडल अधिकतम एन्ट्रापी हैं, उदाहरण के लिए, ER ग्राफ़ <math>G(n,m)</math>और <math>G(n,p)</math> (जिनमें से प्रत्येक में किनारों की संख्या पर एक वैश्विक प्रतिबंध है), साथ ही कॉन्फ़िगरेशन मॉडल (CM)<ref name="Newman 2010">{{cite book|title=Networks: An Introduction - Oxford Scholarship|last=Newman|first=Mark|doi=10.1093/acprof:oso/9780199206650.001.0001|year=2010|isbn=9780199206650|url=https://cds.cern.ch/record/1281254|access-date=2018-09-13|archive-date=2023-02-04|archive-url=https://web.archive.org/web/20230204160415/https://catalogue.library.cern/legacy/1281254|url-status=live}}</ref> और सॉफ्ट कॉन्फ़िगरेशन मॉडल (एससीएम) (जिसमें प्रत्येक में <math>n</math> स्थानीय प्रतिबंध हैं, प्रत्येक नोड-वार डिग्री-मान के लिए एक) हैं। ऊपर वर्णित मॉडलों के दो जोड़े में, एक महत्वपूर्ण अंतर <ref>{{cite journal|last=Garlaschelli|first=Diego|last2=den Hollander|first2=Frank|last3=Roccaverde|first3=Andrea|date=2018-07-13|title=यादृच्छिक ग्राफ़ में समतुल्यता को तोड़ने के पीछे सहप्रसरण संरचना|journal=Journal of Statistical Physics|volume=173|issue=3–4|pages=644–662|doi=10.1007/s10955-018-2114-x|issn=0022-4715|arxiv=1711.04273|bibcode=2018JSP...173..644G}}</ref><ref>{{cite journal|last=Roccaverde|first=Andrea|date=August 2018|title=Is breaking of ensemble equivalence monotone in the number of constraints?|journal=Indagationes Mathematicae|volume=30|pages=7–25|doi=10.1016/j.indag.2018.08.001|issn=0019-3577|arxiv=1807.02791}}</ref> यह है कि क्या प्रतिबंध शार्प है (यानी आकार के सेट के प्रत्येक तत्व से संतुष्ट- <math>n</math> ग्राफ़ संयोजन में गैर-शून्य संभावना के साथ), या सॉफ्ट (अर्थात संपूर्ण समूह औसतन संतुष्ट है)। पूर्व (शार्प) स्थिति एक माइक्रोकैनोनिकल समुच्चय से मेल खाता है,<ref>{{cite book
   |last         = Bianconi
   |first        = G.
@@ Line 32: / Line 32: @@
   |archive-url  = https://web.archive.org/web/20230204160403/https://global.oup.com/academic/product/multilayer-networks-9780198753919?cc=us&lang=en&
   |url-status   = live
-}}</ref> अधिकतम एन्ट्रापी की स्थिति जो सभी ग्राफ़ <math>G</math> को संतुष्ट करती है <math>Q_j(G)=q_j\forall j</math> समसंभाव्य के रूप में; बाद वाला (सॉफ्ट) मामला विहित है,<ref name="Anand">{{cite journal
+}}</ref> अधिकतम एन्ट्रापी की स्थिति जो सभी ग्राफ़ <math>G</math> को संतुष्ट करती है <math>Q_j(G)=q_j\forall j</math> समसंभाव्य के रूप में; बाद वाला (सॉफ्ट) स्थिति विहित है,<ref name="Anand">{{cite journal
 |last1=Anand
 |first1=K.
@@ Line 60: / Line 60: @@
 |-
   || शार्प, लोकल || प्रत्येक शीर्ष की डिग्री,
-|
+|प्रत्येक शीर्ष की डिग्री <math>{\displaystyle \{{\hat {k}}_{j}\}_{j=1}^{n}}</math>
+|<math>{\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}}</math>
 |-
-  || सॉफ्ट, लोकल|| प्रत्येक शीर्ष की अपेक्षित डिग्री, ||
+  || सॉफ्ट, लोकल|| प्रत्येक शीर्ष की अपेक्षित डिग्री, ||प्रत्येक शीर्ष की अपेक्षित डिग्री <math>{\displaystyle \{{\hat {k}}_{j}\}_{j=1}^{n}}</math>
+|<math>{\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}}</math>
 |}
 ==ग्राफ़ का विहित समूह (सामान्य रूपरेखा)==
-मान लीजिए कि हम एक यादृच्छिक ग्राफ मॉडल का निर्माण कर रहे हैं जिसमें <math>n</math> शीर्षों वाले सरल ग्राफ़ के सेट <math>\mathcal{G}_n</math>पर संभाव्यता वितरण <math>\mathbb{P}(G)</math> शामिल है। इस समूह की गिब्स एन्ट्रॉपी <math>S[G]</math> दी जाएगी
+मान लीजिए कि हम एक यादृच्छिक ग्राफ मॉडल का निर्माण कर रहे हैं जिसमें <math>n</math> शीर्षों वाले सरल ग्राफ़ के सेट <math>\mathcal{G}_n</math>पर संभाव्यता वितरण <math>\mathbb{P}(G)</math> सम्मिलित है। इस समूह की गिब्स एन्ट्रॉपी <math>S[G]</math> दी जाएगी
 :      <math> S[G]=-\sum_{G\in \mathcal{G}_n}\mathbb{P}(G)\log\mathbb{P}(G).</math>
@@ Line 72: / Line 74: @@
 :      <math> \langle Q_j \rangle = \sum_{G\in \mathcal{G}_n}\mathbb{P}(G)Q_j(G) = q_j, </math>
-जहाँ <math>j=1,...,J</math> जे बाधाओं को लेबल करें। वितरण <math>\mathbb{P}(G)</math> को निर्धारित करने के लिए लैग्रेंज मल्टीप्लायरों की विधि का अनुप्रयोग जो <math>\langle Q_j \rangle=q_j</math> को संतुष्ट करते हुए <math>S[G]</math> को अधिकतम करता है, और सामान्यीकरण की स्थिति <math>\sum_{G\in \mathcal{G}_n}\mathbb{P}(G)=1</math> के परिणामस्वरूप निम्नलिखित परिणाम मिलते हैं:<ref name="Park" />
+जहाँ <math>j=1,...,J</math> जे प्रतिबंधों को लेबल करें। वितरण <math>\mathbb{P}(G)</math> को निर्धारित करने के लिए लैग्रेंज मल्टीप्लायरों की विधि का अनुप्रयोग जो <math>\langle Q_j \rangle=q_j</math> को संतुष्ट करते हुए <math>S[G]</math> को अधिकतम करता है, और सामान्यीकरण की स्थिति <math>\sum_{G\in \mathcal{G}_n}\mathbb{P}(G)=1</math> के परिणामस्वरूप निम्नलिखित परिणाम मिलते हैं:<ref name="Park" />
 :      <math> \mathbb{P}(G) = \frac{1}{Z}\exp\left[-\sum_{j=1}^J\psi_j Q_j(G)\right],</math>
@@ Line 79: / Line 81: @@
 ==एर्डोस-रेनी मॉडल <math>G(n,m)</math>==
-उपरोक्त विहित ढांचे में, संयोजन-औसत मात्राओं <math>\langle Q_j \rangle</math> पर प्रतिबंध लगाए गए थे। हालाँकि ये गुण औसतन <math>\{\psi_j\}_{j=1}^J</math> की उचित सेटिंग द्वारा निर्दिष्ट मानों पर आधारित होंगे, प्रत्येक विशिष्ट उदाहरण <math>G</math> में <math>Q_j(G)\ne q_j</math> हो सकता है, जो अवांछनीय हो सकता है। इसके बजाय, हम अधिक सख्त शर्त लगा सकते हैं: गैर-शून्य संभावना वाले प्रत्येक ग्राफ को <math>Q_j(G)= q_j</math> को बिल्कुल संतुष्ट करना होगा। इन "तीव्र" बाधाओं के तहत, अधिकतम एन्ट्रापी वितरण निर्धारित किया जाता है। हम इसका उदाहरण एर्डोस-रेनी मॉडल <math>G(n,m)</math> से देते हैं।
+उपरोक्त विहित ढांचे में, संयोजन-औसत मात्राओं <math>\langle Q_j \rangle</math> पर प्रतिबंध लगाए गए थे। हालाँकि ये गुण औसतन <math>\{\psi_j\}_{j=1}^J</math> की उचित सेटिंग द्वारा निर्दिष्ट मानों पर आधारित होंगे, प्रत्येक विशिष्ट उदाहरण <math>G</math> में <math>Q_j(G)\ne q_j</math> हो सकता है, जो अवांछनीय हो सकता है। इसके बजाय, हम अधिक सख्त शर्त लगा सकते हैं: गैर-शून्य संभावना वाले प्रत्येक ग्राफ को <math>Q_j(G)= q_j</math> को बिल्कुल संतुष्ट करना होगा। इन "तीव्र" प्रतिबंधों के तहत, अधिकतम एन्ट्रापी वितरण निर्धारित किया जाता है। हम इसका उदाहरण एर्डोस-रेनी मॉडल <math>G(n,m)</math> से देते हैं।
 <math>G(n,m)</math> में तीव्र प्रतिबंध <math>m</math> किनारों की एक निश्चित संख्या है, <ref name="ER">{{cite journal
@@ Line 98: / Line 100: @@
 }}</ref> जो कि <math>|\operatorname E(G)|=m</math> है, संयोजन से खींचे गए सभी ग्राफ़ <math>G</math> के लिए (संभावना के साथ तत्काल <math>\mathbb{P}_{n,m}(G)</math> दर्शाया गया है। यह <math>\mathcal{G}_n</math>से नमूना स्थान को प्रतिबंधित करता है। (<math>n</math> शीर्षों पर सभी ग्राफ़) उपसमुच्चय <math>\mathcal{G}_{n,m}=\{g\in\mathcal{G}_n;|\operatorname E(g)|=m\}\subset \mathcal{G}_n</math> तक। यह चिरसम्मत सांख्यिकीय यांत्रिकी में माइक्रोकैनोनिकल संयोजन के सीधे सादृश्य में है, जिसमें सिस्टम एक विशेष ऊर्जा मूल्य के सभी अवस्थाओं के चरण स्थान में एक पतली विविधता तक सीमित है।
-हमारे नमूना स्थान को <math>\mathcal{G}_{n,m}</math> तक सीमित करने पर, हमारे पास संतुष्ट करने के लिए कोई बाहरी बाधा (सामान्यीकरण के अलावा) नहीं है, और इस प्रकार हम लैग्रेंज मल्टीप्लायरों का उपयोग किए बिना <math>S[G]</math> को अधिकतम करने के लिए <math>\mathbb{P}_{n,m}(G)</math> का चयन करेंगे। यह सर्वविदित है कि बाहरी बाधाओं की अनुपस्थिति में एन्ट्रापी-अधिकतम वितरण नमूना स्थान पर समान वितरण है (अधिकतम एन्ट्रापी संभाव्यता वितरण देखें), जिससे हम प्राप्त करते हैं:
+हमारे नमूना स्थान को <math>\mathcal{G}_{n,m}</math> तक सीमित करने पर, हमारे पास संतुष्ट करने के लिए कोई बाहरी बाधा (सामान्यीकरण के अलावा) नहीं है, और इस प्रकार हम लैग्रेंज मल्टीप्लायरों का उपयोग किए बिना <math>S[G]</math> को अधिकतम करने के लिए <math>\mathbb{P}_{n,m}(G)</math> का चयन करेंगे। यह सर्वविदित है कि बाहरी प्रतिबंधों की अनुपस्थिति में एन्ट्रापी-अधिकतम वितरण नमूना स्थान पर समान वितरण है (अधिकतम एन्ट्रापी संभाव्यता वितरण देखें), जिससे हम प्राप्त करते हैं:
 :      <math>\mathbb{P}_{n,m}(G)=\frac{1}{|\mathcal{G}_{n,m}|}=\binom{\binom{n}{2}}{m}^{-1},</math>
-जहां द्विपद गुणांक के संदर्भ में अंतिम अभिव्यक्ति संभव किनारों के बीच <math>\binom{n}{2}</math> किनारों को रखने के तरीकों की संख्या है, और इस प्रकार <math>\mathcal{G}_{n,m}</math>, <math>m</math> की प्रमुखता है।
+जहां द्विपद गुणांक के संदर्भ में अंतिम अभिव्यक्ति संभव किनारों के बीच <math>\binom{n}{2}</math> किनारों को रखने के विधियों की संख्या है, और इस प्रकार <math>\mathcal{G}_{n,m}</math>, <math>m</math> की प्रमुखता है।
 ==सामान्यीकरण==
@@ Line 112: / Line 114: @@
 |date=2015-10-29
 |arxiv = 1502.05032}}
-</ref> और किसी दिए गए अपेक्षित डिग्री अनुक्रम के साथ भारित यादृच्छिक ग्राफ़ इनमें शामिल हैं। <ref name="Hillar">{{cite news
+</ref> और किसी दिए गए अपेक्षित डिग्री अनुक्रम के साथ भारित यादृच्छिक ग्राफ़ इनमें सम्मिलित हैं। <ref name="Hillar">{{cite news
 |title=Maximum entropy distributions on graphs
 |last=Hillar

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 09:36, 5 December 2023

Contents

अवलोकन

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

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

सामान्यीकरण

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 09:36, 5 December 2023

अवलोकन

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

एर्डोस-रेनी मॉडल G⁡(n,m){\displaystyle G(n,m)}

सामान्यीकरण

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories

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