پیش‌نویس:مدل گراف تصادفی حداکثر آنتروپی

مدل‌های گراف حداکثر آنتروپی ، مدل‌های گراف تصادفی‌ای هستند که برای مطالعه شبکه‌های پیچیده تحت تاثیر اصل حداکثر آنتروپی استفاده می‌شوند. این شبکه‌ها می‌توانند تحت مجموعه‌ای از قیود ساختاری، که ممکن است سراسری، توزیعی یا موضعی باشند قرار داشته باشند.

نگاه کلی

هر مدل گراف تصادفی (که با استفاده از مجموعه‌ای از پارامترهای مشخص ساخته شده باشد) منجر به یک توزیع احتمال از گراف‌ها می شود. مدل هایی در هر کلاس توزیع حداکثر آنتروپی هستند، که در دسته خاص مدل‌های تهی بی‌غرض حداکثری، برای استنباط شبکه هستند ( به عنوان مثال استنباط شبکه‌های زیستی ). هر مدل، خانواده‌ای از توزیع‌ احتمال‌ها را بر روی مجموعه گراف‌های با اندازه $n$، تعریف می‌کند (برای هر $n>n_{0}$ به ازای یک $n_{0}$ محدود). در این مجموعه هر گراف $G$، با مجموعه‌ ای از قیود بر روی $J$ متغیر مشاهده پذیر که به‌ صورت $\{Q_{j}(G)\}_{j=1}^{J}$ تعریف می‌شود (مانند میانگین درجه مشخص، فرم خاصی از توزیع درجه و یا ترتیب درجه مشخص)، توصیف می‌شود که در کنار شرط حداکثر سازی آنتروپی با روش ضرایب لاگرانژ در توزیع گراف اعمال می شوند. توجه داشته باشید که در این موضوع، "حداکثر آنتروپی" نه به آنتروپی یک گراف منفرد، بلکه به آنتروپی کل آنسامبل آماری گراف‌های تصادفی اشاره دارد.

تعدادی از مدل‌های شبکه تصادفی که معمولاً مورد مطالعه قرار می‌گیرند، در واقع حداکثر آنتروپی هستند. برای مثال گراف‌های اردوش رنیی $G(n,m)$ و $G(n,p)$ (که هر کدام دارای یک محدودیت سراسری در تعداد یال‌ها هستند). همچنین مدل پیکربندی (CM) و مدل پیکربندی نرم (SCM) (که هر کدام دارای $n$ محدودیت موضعی، یکی برای درجه هر رأس هستند) نیز در این دسته قرار می‌گیرند. در دو جفت مدل ذکر شده بالا، یک عامل ایجاد تمایز مهم در این است که قید اعمال شده شارپ (به این معنا که توسط تمام عناصر مجموعه گراف‌های به اندازه $n$ که احتمال غیر صفر در آنسامبل دارند برآورده می شود)، یا نرم (به این معنا که به طور متوسط در کل آنسامبل برآورده می شود) است. حالت شارپ متناظر است با یک آنسامبل میکروکانونی، که در آن شرط حداکثر آنتروپی، به تمام گراف‌های $G$ که شرط $Q_{j}(g)=q_{j}\forall j$ را برآورده می‌کنند، احتمال یکسان نسبت می‌دهد. حالت نرم متناظر با یک آنسامبل کانونی است، که یک مدل گرافی تصادفی نمایی تولید می کند.

مدل	نوع قید	متغیر قید	توزیع احتمال
اردوش-رنیی، $G(n,m)$	شارپ، سراسری	تعداد کل یال‌ها $|E(G)|$	$1/{\binom {\binom {n}{2}}{m}};\ m=|E(G)|$
اردوش-رنیی، $G(n,p)$	نرم، سراسری	تعداد چشم داشتی یال‌ها$|E(G)|$	$p^{|E(G)|}(1-p)^{{\binom {n}{2}}-|E(G)|}$
مدل پیکربندی	شارپ، موضعی	درجه هر رأس، $\{{\hat {k}}_{j}\}_{j=1}^{n}$	$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}$
مدل پیکربندی نرم	نرم، موضعی	مقدار چشم داشتی درجه هر رأس،$\{{\hat {k}}_{j}\}_{j=1}^{n}$	$Z^{-1}\exp \left[-\sum _{j=1}^{n}\psi _{j}k_{j}(G)\right];\ -{\frac {\partial \ln Z}{\partial \psi _{j}}}={\hat {k}}_{j}$

آنسامبل گراف‌‌های کانونی (چارچوب کلی)

فرض کنید می‌خواهیم مدل گراف رندومی بسازیم که تابع توزیع احتمال آن بصورت $\mathbb {P} (G)$ بر روی مجموعه ${\mathcal {G}}_{n}$ از گراف‌های ساده با $n$ رأس تعریف شود. آنتروپی گیبس، $S[G]$ این مجموعه توسط معادله زیر بدست می‌آید:

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

می‌خواهیم مقادیر میانگین گیری شده بر روی آنسامبل $\{\langle Q_{j}\rangle \}_{j=1}^{J}$ متغیرهای قابل مشاهده $\{Q_{j}(G)\}_{j=1}^{J}$ (مانند درجه متوسط، ضریب خوشگی متوسط و یا میانگین کوتاه ترین مسیر)، قابل تنظیم باشند، بنابراین $J$ قید "نرم" بر روی توزیع گراف‌ها بصورت زیر اعمال می‌کنیم.

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

که در آن $j=1,...,J$ قیود را شماره گذاری می‌کند. با استفاده از روش ضرایب لاگرانژ برای تعیین توزیع احتمال $\mathbb {P} (G)$ ای که $S[G]$ را بیشینه می‌کند در حالی که شروط $\langle Q_{j}\rangle =q_{j}$ و نرمال سازی $\sum _{G\in {{\mathcal {G}}_{n}}}\mathbb {P} (G)=1$ را برآورده می‌کند، منجر به نتیجه زیر می‌شود:

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

^{که در آن $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$ است. یعنی برای هر گراف $G$ که از آنسامبل (انتخاب شده با احتمال} $\mathbb {P} _{n,m}(G)$^{)، شرط} $|E(G)|=m$ ^{باید برقرار باشد. این شرط فضای نمونه را از} ${\mathcal {G}}_{n}$^{(همه گراف‌های $n$ رأسی) به زیرفضای} ${\mathcal {G}}_{n,m}=\{g\in {\mathcal {G}}_{n};|E(g)|=m\}\subset {\mathcal {G}}_{n}$ ^{محدود می‌کند. این متناظر با آنسامبل میکروکانونی در مکانیک آماری کلاسیک است، که در آن سیستم به یک منیفولد نازک در فضای فاز محدود می‌شود که همه حالت‌های آن دارای یک انرژی خاص هستند.}

^{با محدود کردن فضای نمونه‌مان به} ${\mathcal {G}}_{n,m}$^{، ما هیچ قید خارجی‌ای (بجز شرط نرمال کردن)، برای ارضای کردن نداریم بنابراین} $\mathbb {P} _{n,m}(G)$ ^{را طوری انتخاب می‌کنیم که} $S[G]$ ^{را بدون استفاده از ضرایب لاگرانژ، بیشینه کند. مشخص است که توزیعی که آنتروپی را بیشینه کند، در غیاب قیود خارجی، همان توزیع یکنواخت در فضای نمونه است (به توزیع احتمال حداکثر آنتروپی مراجعه کنید) که از آن} $\mathbb {P} _{n,m}(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}$ ^است.

تعمیم دادن

^{انواع متعددی از آنسامبل‌های آنتروپی حداکثری بر روی تعمیم‌هایی از گراف‌های ساده مورد مطالعه قرار گرفته‌اند. برای مثال، این‌ها شامل آنسامبل‌هایی از مجتمع‌های سادکی، و گراف‌های تصادفی وزن‌دار با توالی درجه چشم داشتی مشخص است.}

صفحات مرتبط

• ^{اصل حداکثر آنتروپی}
• ^{توزیع احتمال حداکثر آنتروپی}
• ^{روش ضرایب لاگرانژ}
• ^{مدل تهی}
• ^{گراف تصادفی}
• ^{مدل‌های گرافی تصادفی نمایی}
• ^{آنسامبل کانونی}
• ^{آنسامبل میکروکانونی}