پرش به محتوا

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

از ویکی‌پدیا، دانشنامهٔ آزاد

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

نگاه کلی[ویرایش]

هر مدل گراف تصادفی (که با استفاده از مجموعه‌ای از پارامترهای مشخص ساخته شده باشد) منجر به یک توزیع احتمال از گراف‌ها می شود. مدل هایی در هر کلاس توزیع حداکثر آنتروپی هستند، که در دسته خاص مدل‌های تهی بی‌غرض حداکثری، برای استنباط شبکه هستند[۲] ( به عنوان مثال استنباط شبکه‌های زیستی ). هر مدل، خانواده‌ای از توزیع‌ احتمال‌ها را بر روی مجموعه گراف‌های با اندازه ، تعریف می‌کند (برای هر به ازای یک محدود). در این مجموعه هر گراف ، با مجموعه‌ ای از قیود بر روی متغیر مشاهده پذیر که به‌ صورت تعریف می‌شود (مانند میانگین درجه مشخص، فرم خاصی از توزیع درجه و یا ترتیب درجه مشخص)، توصیف می‌شود که در کنار شرط حداکثر سازی آنتروپی با روش ضرایب لاگرانژ در توزیع گراف اعمال می شوند. توجه داشته باشید که در این موضوع، "حداکثر آنتروپی" نه به آنتروپی یک گراف منفرد، بلکه به آنتروپی کل آنسامبل آماری گراف‌های تصادفی اشاره دارد.

تعدادی از مدل‌های شبکه تصادفی که معمولاً مورد مطالعه قرار می‌گیرند، در واقع حداکثر آنتروپی هستند. برای مثال گراف‌های اردوش رنیی و (که هر کدام دارای یک محدودیت سراسری در تعداد یال‌ها هستند). همچنین مدل پیکربندی (CM) و مدل پیکربندی نرم (SCM) (که هر کدام دارای محدودیت موضعی، یکی برای درجه هر رأس هستند) نیز در این دسته قرار می‌گیرند. در دو جفت مدل ذکر شده بالا، یک عامل ایجاد تمایز مهم [۳] [۴] در این است که قید اعمال شده شارپ (به این معنا که توسط تمام عناصر مجموعه گراف‌های به اندازه که احتمال غیر صفر در آنسامبل دارند برآورده می شود)، یا نرم (به این معنا که به طور متوسط در کل آنسامبل برآورده می شود) است. حالت شارپ متناظر است با یک آنسامبل میکروکانونی، که در آن شرط حداکثر آنتروپی، به تمام گراف‌های که شرط را برآورده می‌کنند، احتمال یکسان نسبت می‌دهد. حالت نرم متناظر با یک آنسامبل کانونی است، که[۵] یک مدل گرافی تصادفی نمایی تولید می کند.

مدل نوع قید متغیر قید توزیع احتمال
اردوش-رنیی،

شارپ،

سراسری

تعداد کل یال‌ها

اردوش-رنیی،

نرم،

سراسری

تعداد چشم داشتی

یال‌ها

مدل

پیکربندی

شارپ،

موضعی

درجه هر رأس،

مدل

پیکربندی نرم

نرم،

موضعی

مقدار چشم داشتی

درجه هر رأس،

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

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

می‌خواهیم مقادیر میانگین گیری شده بر روی آنسامبل متغیرهای قابل مشاهده (مانند درجه متوسط، ضریب خوشگی متوسط و یا میانگین کوتاه ترین مسیر)، قابل تنظیم باشند، بنابراین قید "نرم" بر روی توزیع گراف‌ها بصورت زیر اعمال می‌کنیم.

که در آن قیود را شماره گذاری می‌کند. با استفاده از روش ضرایب لاگرانژ برای تعیین توزیع احتمال ای که را بیشینه می‌کند در حالی که شروط و نرمال سازی را برآورده می‌کند، منجر به نتیجه زیر می‌شود:[۱]


که در آن ضریب نرمالیزاسیون ( تابع پارش ) است و پارامترهایی هستند (ضرایب لاگرانژ)، که با متغیرهای قابل مشاهده گراف‌های شماره گذاری شده کوپل شده اند، که با تنظیم آن‌ها می‌توان نمونه‌ای از گراف‌ها با خواص (مانند درجه میانگین یا میانگین طول کوتاه ترین مسیر) دلخواه تولید کرد. نتیجه آن یک خانواده نمایی و آنسامبل کانونی است که به طور خاص یک مدل گرافی تصادفی نمایی است.

مدل اردوش رنیی [ویرایش]

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

قید شارپ بر روی مدل ،تعداد ثابت یال‌های آن،‌ است.[۶] یعنی برای هر گراف که از آنسامبل (انتخاب شده با احتمال )، شرط باید برقرار باشد. این شرط فضای نمونه را از (همه گراف‌های رأسی) به زیرفضای محدود می‌کند. این متناظر با آنسامبل میکروکانونی در مکانیک آماری کلاسیک است، که در آن سیستم به یک منیفولد نازک در فضای فاز محدود می‌شود که همه حالت‌های آن دارای یک انرژی خاص هستند.

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

که در آن آخرین عبارت که بر حسب ضرایب دوجمله ای نوشته شده است، تعداد روش‌های قرار دادن یال در میان یال ممکن است، که در نتیجه این همان اندازه یا کاردینالیتی مجموعه است.

تعمیم دادن[ویرایش]

انواع متعددی از آنسامبل‌های آنتروپی حداکثری بر روی تعمیم‌هایی از گراف‌های ساده مورد مطالعه قرار گرفته‌اند. برای مثال، این‌ها شامل آنسامبل‌هایی از مجتمع‌های سادکی،[۷] و گراف‌های تصادفی وزن‌دار با توالی درجه چشم داشتی مشخصخطای یادکرد: برچسب‌های <ref> یافته شد که درونشان محتوایی نبود. یادکرد منبع باید بین برچسب‌ها قرار گیرد. (صفحهٔ راهنما را مطالعه کنید.). است.

صفحات مرتبط[ویرایش]

منابع[ویرایش]

  1. ۱٫۰ ۱٫۱ Park, Juyong; Newman, M. E. J. (2004-12-07). "Statistical mechanics of networks". Physical Review E. 70 (6). doi:10.1103/physreve.70.066117. ISSN 1539-3755.
  2. van der Hoorn, Pim; Lippner, Gabor; Krioukov, Dmitri (2017-10-06). "Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution". Journal of Statistical Physics. 173 (3–4): 806–844. doi:10.1007/s10955-017-1887-7. ISSN 0022-4715.
  3. Garlaschelli, Diego; den Hollander, Frank; Roccaverde, Andrea (2018-11). "Covariance Structure Behind Breaking of Ensemble Equivalence in Random Graphs". Journal of Statistical Physics (به انگلیسی). 173 (3–4): 644–662. doi:10.1007/s10955-018-2114-x. ISSN 0022-4715. {{cite journal}}: Check date values in: |date= (help)
  4. Roccaverde, Andrea (2019-01). "Is breaking of ensemble equivalence monotone in the number of constraints?". Indagationes Mathematicae (به انگلیسی). 30 (1): 7–25. doi:10.1016/j.indag.2018.08.001. {{cite journal}}: Check date values in: |date= (help)
  5. Anand, Kartik; Bianconi, Ginestra (2009-10-13). "Entropy measures for networks: Toward an information theory of complex topologies". Physical Review E (به انگلیسی). 80 (4). doi:10.1103/PhysRevE.80.045102. ISSN 1539-3755.
  6. Erdős, P.; Rényi, A. (2022-07-01). "On random graphs. I." Publicationes Mathematicae Debrecen. 6 (3–4): 290–297. doi:10.5486/pmd.1959.6.3-4.12. ISSN 0033-3883.
  7. Zuev, Konstantin; Eisenberg, Or; Krioukov, Dmitri (2015-10-26). "Exponential random simplicial complexes". Journal of Physics A: Mathematical and Theoretical. 48 (46): 465002. doi:10.1088/1751-8113/48/46/465002. ISSN 1751-8113.