مدل‌های گرافی تصادفی نمایی

مدل‌های گراف تصادفی نمایی (به انگلیسی: Exponential Random Graph Models) یا مدل‌های *p یکی از مدل‌های خانواده نمایی هستند که برای تحلیل داده‌های شبکه‌ها به خصوص شبکه‌های اجتماعی به کار می‌روند. استفاده از مدل ERG زمانی مؤثر است که بخواهیم بدون ورود به جزئیات فرایند شکل‌گیری شبکه، مدل شبکه‌ای درست کنیم که تا حد ممکن با ویژگی‌های شبکه مشاهده شده مطابقت داشته باشد. این مدل‌های گراف برای مطالعه ویژگی‌های ساختاری شبکه‌ها و مدل‌های فرایندهایی که روی شبکه‌ها اتفاق می‌افتند، مانند گسترش بیماری واگیر، انتشار اطلاعات، شکل‌گیری نظرات در شبکه‌های اجتماعی و … کاربرد دارند.

پیشینه تاریخی

اولین گروه مدل از شبکه‌ها توسط Solomonof و Rapoport در سال ۱۹۵۱ معرفی شد. در این مدل مجموعه تمام گراف‌های ساده غیر جهت‌دار با تعداد ثابت N گره در نظر گرفته شده که هر جفت گره با احتمال p با یک یال به یکدیگر وصل شده‌اند. تا کنون این مدل را به نام مدل Bernoulli یا مدل Erdös-Rènyi شناخته شده‌است و در حقیقت اولین مثال از مدل ERG است.
مدل گراف تصادفی نمایی، اوایل دههٔ ۱۹۸۰ توسط Holland و Leinhard مطرح شد. توسعه‌های بعدی توسط نویسندگان دیگر در دههٔ ۱۹۹۰ ادامه پیدا کرد. در سال‌های اخیر، تعدادی از فیزیکدانان مطالعه‌های تئوری از جمله در این زمینه انجام داده‌اند.
امروزه، مدل‌های ERG بیشتر در تحلیل شبکه‌های اجتماعی (SNA) استفاده می‌شوند. علاوه بر این جعبه ابزار روش‌ها/مدل‌های شبکه اجتماعی معمولاً به مدل ERG مجهز هستند. به احتمال زیاد این موضوع به دلیل این است که ERGها به عنوان یک ابزار عملی برای مدل کردن هر شبکه پیچیده در نظر گرفته شده‌اند. مخصوصاً اینکه، چند ابزار کامپیوتری استاندارد، مانند بسته ERGM، برای شبیه‌سازی آن‌ها در نظر گرفته شده‌است.

مقدمه

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

چرایی نیاز به مدل ERG

تخمین شبکه جایگزین به دو دلیل چالش برانگیز است. اول؛ روابط به طور کلی مستقل نیستند، دوم؛ معمولا فقط یک شبکه مشاهده شده داریم. برای حل این چالش‌ها از مدل ERG استفاده می‌کنیم که با در نظر گرفتن وابستگی متقابل بین مولفه‌ها این چالش‌ها را برطرف می‌کند. به طور مثال در شبکه‌های اجتماعی، افراد گره‌های شبکه هستند و ارتباط بین دو گره مستقل از وجود یا عدم وجود ارتباط بین دیگر گره‌ها نیست. مثلا احتمال ارتباط بین دو نفر در شرایطی که دوست مشترک داشته باشند بیشتر می‌شود (وابستگی مارکف). پس برای تخمین یک شبکه اجتماعی باید این وابستگی‌ها را در نظر گرفت و در نتیجه باید از مدل ERG استفاده کرد.
وابستگی مارکف
Frank و Strauss در 1986 وابستگی مارکوف را معرفی کردند. این وابستگی بیان می‌کند که اگر گره i و j به یکدیگر متصل باشند؛ این اتصال روی هر اتصال دیگری که شامل i و j است تاثیر می‌گذارد. حتی اگر وضعیت همه‌ی اتصال‌های دیگر در شبکه معلوم باشد. در واقع وابستگی مارکف بیان می‌کند زمانی که دو اتصال بازیگر مشترک دارند، به صورت شرطی وابسته هستند. به عنوان مثال، رابطه بین پیتر و مری ممکن است وابسته به این باشد که آیا مری به جان وابسته است یا خیر (پیتر و جان دشمن همدیگر هستند). در واقع می‌توان گفت به دلیل اینکه گره m (مری) بین روابط احتمال Pᵢₘ و Pₘⱼ مشترک است، بین این دو احتمال رابطه شرطی برقرار است.

مثال

اگر فرض کنیم احتمال یک شبکه به تعداد لینک‌ها، تعداد دو ستاره‌ها، تعداد سه ستاره‌ها و تعداد مثلث‌های آن شبکه بستگی داشته باشد، آنگاه:
در نتیجه:

نمایش مدل‌های مختلف شبکه به صورت خانواده نمایی

وقتی وابستگی متقابل بین نودها وجود داشته باشد، تخمین شکل‌گیری شبکه نمی‌تواند در سطح جفت نودها اتفاق بیفتد بلکه باید کل شبکه را در نظر بگیرد. ERGMs این وابستگی‌ها را در نظر می‌گیرد و بنابراین مدل‌های جامعی برای تخمین شکل‌گیری شبکه هستند. در واقع همان‌طور که به وسیله نظریه قدرتمند Hammersley و Clifford در 1971 نشان داده شده است، فرم نمایی می‌تواند هر مدل گراف تصادفی را در برگیرد و وابستگی‌های دلخواه درون ارتباطات را نیز شامل شود. البته این نظریه برای شبکه‌های بدون جهت و بدون وزن مورد استفاده قرار می‌گیرد. علاوه بر این ERGM انواع مدل‌های شکل‌گیری شبکه استراتژیک (انتخابی) را در نظر می‌گیرد. 
در ERGM احتمال مشاهده یک شبکه (G) به بردار ویژگی‌های آن (S(G بستگی دارد و احتمال شبکه متناسب است با:
که β بردار پارامترهای مدل است. 

هر مدل شبکه را می‌توان به صورت خانواده نمایی با شمارش ویژگی‌های آماری گراف بیان کرد. در ادامه تبدیل مدل (Erdös-Rènyi G(n,p به خانواده نمایی آورده شده‌ است. در این مدل احتمال یک گراف به احتمال هر یال (p) و تعداد یال‌های درون گراف ((L(G) بستگی دارد. پس:
که (S₁(G همان ویژگی آماری گراف است که در اینجا (L(G می‌باشد و β₁ پارامتر گراف است. c نیز مقدار ثابت است.