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

مدل‌های گراف تصادفی نمایی (به انگلیسی: 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_im و P_mj مشترک است، بین این دو احتمال رابطه شرطی برقرار است.

مدل ERG

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

شکل [۱]: چند نمونه از ویژگی‌های مدل گراف تصادفی نمایی

• تعداد یال‌ها (E)
• دنباله درجه گره‌ها: k_i} = k₁, k₂, . . . k_N}
• متوسط طول کوتاه‌ترین مسیر (l)
• ضریب خوشه‌بندی (C)تعداد مثلث‌ها یا زیرگراف‌های دیگر مثل دوستاره، سه ستاره،..
• تراکم: این معیار همان چگالی شبکه است که برابر است با تعداد یال‌های شبکه تقسیم بر ${\frac {n(n-1)}{2}}$(تعداد یال‌های گراف کامل)
• تعداد مولفه‌های متصل در گراف
• گره‌های متقابل (mutual): این ویژگی تنها می‌تواند در گراف‌های جهت‌دار استفاده شود و برابر تعداد یال‌هایی است که هم (i → j) و هم (j → i) وجود دارد. یا می‌توان تنها یال‌هایی را شمارش کرد که مربوط به گره خاصی هستند.
• گره‌های نامتقارن: این ویژگی تنها می‌تواند در گراف‌های جهت‌دار استفاده شود و برابر تعداد یال‌هایی است که یا (i → j) یا (j → i) وجود دارد. یا می‌توان تنها یال‌هایی را شمارش کرد که مربوط به گره خاصی هستند.

ویژگی‌های مشاهده شده را با x_i} = x₁, x₂, . . . x_r} و مقادیر اندازه‌گیری شده آن‌ها در شبکه واقعی را با x^∗_i } = x^∗₁, x^∗₂, . . . x^*_r} نشان می‌دهیم.

پس از تعیین ویژگی‌ها باید مجموعه تمام گراف‌های ممکن که شبکه واقعی می‌تواند داشته باشد را مشخص کرد؛ {g={G. با توجه به کاربردهای مختلف می‌توان گراف‌های ساده، با حلقه، با یال چندگانه، وزن‌دار یا جهت‌دار را در نظر گرفت اما برای سادگی گراف‌های ساده در نظر گرفته می‌شود. در شکل [۲] یک گروه آماری از گراف‌های ساده به عنوان نمونه آورده شده‌ است:

شکل [۲]: تناظر یک به یک بین گراف‌های ساده و ماتریس‌های متقارن با اندازهٔ N و عناصر A_ij که می‌توانند ۰ یا ۱ باشند را نشان می‌دهد.

در مدل گراف تصادفی نمایی، هر گراف G با احتمال ⁽P(G) ∝ e^H(G ظاهر می‌شود؛ (H(G گراف همیلتونی است که تعیین‌کننده ویژگی‌های شبکه‌‌های مختلف است. در ERGM توزیع احتمال (P(G به فرم زیر می‌باشد:

$P(G)={\frac {1}{Z}}{\exp(H(G))},$

که Z تابع پارتیشن نامیده می‌شود و می‌تواند با توجه به شرط نرمال بودن محاسبه شود:

$\sum _{G\in g}P(G)={\frac {1}{Z}}\sum _{G\in g}\exp(H(G))=1.$

در نتیجه:

$Z=\sum _{G\in g}\exp(H(G)).$

اما شبکه همیلتونی را می‌توان به صورت زیر نوشت:

$H(G)=\sum _{i=1}^{r}\theta _{i}x_{i}(G),$

که {(x_i(G} مقادیر مشاهدات {x_i} برای گراف G هستند و θ_i} = θ₁, θ₂, . . . θ_r} پارامترهای مجموعه گراف‌ها هستند و مقدار x^*_i که در شبکه واقعی اندازه‌گیری شده‌ است، با متوسط مقدار درون مجموعه گراف مطابقت دارد، یعنی:

$<x_{i}>=\sum _{G\in g}x_{i}(G)P(G)=x_{i}^{*},$

برای i = 1, 2, .... , r.

مثال

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

$H(G)=\beta _{1}LinkCount(G)+\beta _{2}2StarsCount(G)+\beta _{3}3StarsCount(G)+\beta _{4}TriangleCount(G)=\beta _{1}L(G)+\beta _{2}S_{2}(G)+\beta _{3}S_{3}(G)+\beta _{4}T(G)$

در نتیجه:

$P(G)\sim \exp[\beta _{1}L(G)+\beta _{2}S_{2}(G)+\beta _{3}S_{3}(G)+\beta _{4}T(G)]$

$P(G)={\frac {\exp[\beta _{1}L(G)+\beta _{2}S_{2}(G)+\beta _{3}S_{3}(G)+\beta _{4}T(G)]}{\sum _{G\in g}\exp[\beta _{1}L(G)+\beta _{2}S_{2}(G)+\beta _{3}S_{3}(G)+\beta _{4}T(G)]}}$

$P(G)=\exp[\beta _{1}L(G)+\beta _{2}S_{2}(G)+\beta _{3}S_{3}(G)+\beta _{4}T(G)-c]$

چالش‌های اصلی ساخت یک مدل ERG

دو چالش مهم برای ساخت این مدل مطرح است:

• از چه ویژگی‌هایی استفاده کنیم؟
• کدام ویژگی‌ها می‌توانند در شرایط خاص استفاده شوند و کدام یک نمی‌توانند؟

برای حل برخی چالش‌ها می‌توان مواردی را در نظر گرفت. به‌طور مثال معمولاً در مدل‌سازی آماری کاربر باید از انتخاب وابستگی‌های خطی بین ویژگی‌ها جلوگیری کند، مثلاً از هر دو ویژگی یال و تراکم در یک مدل استفاده نکند. انتخاب ویژگی‌های مؤثر برای یک مدل ERG بستگی به مفهوم آن شبکه دارد. به همین دلیل از ویژگی‌هایی که در یک زمینه مثلاً شبکه‌های اجتماعی استفاده کرده‌ایم، نمی‌توان برای نشان دادن فرایندها در زمینه دیگری مانند وب غذا استفاده کرد.

ویژگی‌های کلی مدل ERG

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

مدل‌های ERG یک توزیع احتمالی روی هر شبکه ممکن از n گره را نشان می‌دهد. اندازه مجموعه شبکه‌های ممکن برای یک گراف ساده با سایز n گره، 2^n(n-1)/2 است. به دلیل اینکه تعداد شبکه‌های ممکن در مجموعه بسیار بیشتر از تعداد پارامترهایی است که می‌تواند مدل را محدود کند، توزیع احتمالی ایده‌ال است که آنتروپی گبیز را ماکزیمم کند.

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

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

در ERGM احتمال مشاهده یک شبکه (G) به بردار ویژگی‌های آن (S(G بستگی دارد و احتمال شبکه متناسب است با:

$P(G)\sim \exp(\beta S(G))$

که β بردار پارامترهای مدل است.

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

$P(G)=p^{L(G)}(1-p)^{{\frac {n(n-1)}{2}}-L(G)}$

$=[{\frac {p}{1-p}}]^{L(G)}(1-p)^{\frac {n(n-1)}{2}}$

$=\exp[\log({\frac {p}{1-p}}){L(G)}-\log({\frac {1}{1-p}}){\frac {n(n-1)}{2}}]$

$=\exp[\beta _{1}S_{1}(G)-c]$

که (S₁(G همان ویژگی آماری گراف است که در اینجا (L(G می‌باشد و β₁ پارامتر گراف است. c نیز مقدار ثابت است_.

مدل کردن شبکه‌های اجتماعی با ERGM

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

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