مدل‌های گرافی تصادفی نمایی
مدل‌های گراف تصادفی نمایی (به انگلیسی: 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 استفاده کرد.
وابستگی مارکف
Frank و Strauss در 1986 وابستگی مارکوف را معرفی کردند. این وابستگی بیان می‌کند که اگر گره i و j به یکدیگر متصل باشند؛ این اتصال روی هر اتصال دیگری که شامل i و j است تاثیر می‌گذارد. حتی اگر وضعیت همه‌ی اتصال‌های دیگر در شبکه معلوم باشد. در واقع وابستگی مارکف بیان می‌کند زمانی که دو اتصال بازیگر مشترک دارند، به صورت شرطی وابسته هستند. به عنوان مثال، رابطه بین پیتر و مری ممکن است وابسته به این باشد که آیا مری به جان وابسته است یا خیر (پیتر و جان دشمن همدیگر هستند). در واقع می‌توان گفت به دلیل اینکه گره m (مری) بین روابط احتمال P و P مشترک است، بین این دو احتمال رابطه شرطی برقرار است.
برای ساخت مدل گراف تصادفی نمایی از روی یک شبکه واقعی، نیاز به تعیین ویژگی‌های قابل اندازه‌گیری شبکه است که در مدل نشان داده می‌شوند. این ویژگی‌ها احتمال کلی یک یال در شبکه جهت‌دار و بدون جهت را در نظر می‌گیرد. به‌طور مثال ویژگی‌های زیر می‌توانند برای ساخت مدل استفاده شوند:
ویژگی‌های مشاهده شده را با x} = x, x, . . . x} و مقادیر اندازه‌گیری شده آن‌ها در شبکه واقعی را با x } = x, x, . . . x} نشان می‌دهیم.
پس از تعیین ویژگی‌ها باید مجموعه تمام گراف‌های ممکن که شبکه واقعی می‌تواند داشته باشد را مشخص کرد؛ {g={G. با توجه به کاربردهای مختلف می‌توان گراف‌های ساده، با حلقه، با یال چندگانه، وزن‌دار یا جهت‌دار را در نظر گرفت اما برای سادگی گراف‌های ساده در نظر گرفته می‌شود. در شکل [۲] یک گروه آماری از گراف‌های ساده به عنوان نمونه آورده شده‌ است:
در مدل گراف تصادفی نمایی، هر گراف G با احتمال P(G) ∝ e ظاهر می‌شود؛ (H(G گراف همیلتونی است که تعیین‌کننده ویژگی‌های شبکه‌‌های مختلف است. در ERGM توزیع احتمال (P(G به فرم زیر می‌باشد:
formula_2
که Z تابع پارتیشن نامیده می‌شود و می‌تواند با توجه به شرط نرمال بودن محاسبه شود:
formula_3
در نتیجه:
formula_4
اما شبکه همیلتونی را می‌توان به صورت زیر نوشت:
formula_5
که {(x(G} مقادیر مشاهدات {x} برای گراف G هستند و θ} = θ, θ, . . . θ} پارامترهای مجموعه گراف‌ها هستند و مقدار x که در شبکه واقعی اندازه‌گیری شده‌ است، با متوسط مقدار درون مجموعه گراف مطابقت دارد، یعنی:
formula_6
برای i = 1, 2, ... , r.
اگر فرض کنیم احتمال یک شبکه به تعداد لینک‌ها، تعداد دو ستاره‌ها، تعداد سه ستاره‌ها و تعداد مثلث‌های آن شبکه بستگی داشته باشد، آنگاه:
formula_7
در نتیجه:
formula_8
formula_9
formula_10
دو چالش مهم برای ساخت این مدل مطرح است:
برای حل برخی چالش‌ها می‌توان مواردی را در نظر گرفت. به‌طور مثال معمولاً در مدل‌سازی آماری کاربر باید از انتخاب وابستگی‌های خطی بین ویژگی‌ها جلوگیری کند، مثلاً از هر دو ویژگی یال و تراکم در یک مدل استفاده نکند. انتخاب ویژگی‌های مؤثر برای یک مدل ERG بستگی به مفهوم آن شبکه دارد. به همین دلیل از ویژگی‌هایی که در یک زمینه مثلاً شبکه‌های اجتماعی استفاده کرده‌ایم، نمی‌توان برای نشان دادن فرایندها در زمینه دیگری مانند وب غذا استفاده کرد.مدل‌های ERG یک توزیع احتمالی روی هر شبکه ممکن از n گره را نشان می‌دهد. اندازه مجموعه شبکه‌های ممکن برای یک گراف ساده با سایز n گره، 2 است. به دلیل اینکه تعداد شبکه‌های ممکن در مجموعه بسیار بیشتر از تعداد پارامترهایی است که می‌تواند مدل را محدود کند، توزیع احتمالی ایده‌ال است که را ماکزیمم کند.
وقتی وابستگی متقابل بین نودها وجود داشته باشد، تخمین شکل‌گیری شبکه نمی‌تواند در سطح جفت نودها اتفاق بیفتد بلکه باید کل شبکه را در نظر بگیرد. ERGMs این وابستگی‌ها را در نظر می‌گیرد و بنابراین مدل‌های جامعی برای تخمین شکل‌گیری شبکه هستند. در واقع همان‌طور که به وسیله نظریه قدرتمند Hammersley و Clifford در 1971 نشان داده شده است، فرم نمایی می‌تواند هر مدل گراف تصادفی را در برگیرد و وابستگی‌های دلخواه درون ارتباطات را نیز شامل شود. البته این نظریه برای شبکه‌های بدون جهت و بدون وزن مورد استفاده قرار می‌گیرد. علاوه بر این ERGM انواع مدل‌های شکل‌گیری شبکه استراتژیک (انتخابی) را در نظر می‌گیرد.
در ERGM احتمال مشاهده یک شبکه (G) به بردار ویژگی‌های آن (S(G بستگی دارد و احتمال شبکه متناسب است با:
formula_11
که β بردار پارامترهای مدل است.
هر مدل شبکه را می‌توان به صورت خانواده نمایی با شمارش ویژگی‌های آماری گراف بیان کرد. در ادامه تبدیل مدل (Erdös-Rènyi G(n,p به خانواده نمایی آورده شده‌ است. در این مدل احتمال یک گراف به احتمال هر یال (p) و تعداد یال‌های درون گراف ((L(G) بستگی دارد. پس:
formula_12
formula_13
formula_14
formula_15
که (S(G همان ویژگی آماری گراف است که در اینجا (L(G می‌باشد و β پارامتر گراف است. c نیز مقدار ثابت است
تکنیک‌های معروف زیادی وجود دارند که ویژگی‌های یک شبکه را از روی گره‌ها یا زیرمجموعه‌‌ای از گره‌ها اندازه‌گیری می‌کنند (مثلا چگالی، مرکزیت و زیرمجموعه‌های همبسته). این تکنیک‌ها برای توصیف و درک ویژگی‌های شبکه خیلی مفید هستند اما برای یافتن یک مدل مناسب از شبکه اجتماعی مشاهده شده، به دلایل زیر می‌توان فراتر از این تکنیک‌ها رفته و به خصوص از مدل‌های آماری استفاده کرد: