موضوع مقاله: مدل‌های گرافی تصادفی نمایی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مدل‌های گرافی تصادفی نمایی | مقدمه: استفاده از مدل ERG زمانی مؤثر است که بخواهیم بدون ورود به جزئیات فرایند شکل‌گیری شبکه، مدل شبکه‌ای درست کنیم که تا حد ممکن با ویژگی‌های شبکه مشاهده شده مطابقت داشته باشد. | ## بخش 1: مدل‌های گرافی تصادفی نمایی | این مدل‌های گراف برای مطالعه ویژگی‌های ساختاری شبکه‌ها و مدل‌های فرایندهایی که روی شبکه‌ها اتفاق می‌افتند، مانند گسترش بیماری واگیر، انتشار اطلاعات، شکل‌گیری نظرات در شبکه‌های اجتماعی و … کاربرد دارند. علاوه بر این جعبه ابزار روش‌ها/مدل‌های شبکه اجتماعی معمولاً به مدل ERG مجهز هستند. به احتمال زیاد این موضوع به دلیل این است که ERGها به عنوان یک ابزار عملی برای مدل کردن هر شبکه پیچیده در نظر گرفته شده‌اند. مخصوصاً اینکه، چند ابزار کامپیوتری استاندارد، مانند بسته ERGM، برای شبیه‌سازی آن‌ها در نظر گرفته شده‌است. مقدمه برای توصیف ویژگی‌های ساختاری یک شبکه مشاهده شده معیارهای بسیاری مانند تراکم، مرکزیت یا جذب وجود دارند. اما این معیارها تنها شبکه مشاهده شده را که فقط یک نمونه از تعداد زیادی شبکه جایگزین ممکن است، توصیف می ‌کند. مجموعه شبکه‌های جایگزین، ممکن است ویژگی‌های ساختاری مشابه یا متفاوتی داشته باشند. یک مدل آماری در فرآیندهای موثر بر شکل‌گیری ساختار شبکه، باید مجموعه تمام شبکه‌های جایگزین ممکن را با توجه به شباهت آن‌ها به شبکه مشاهده شده در نظر بگیرد. مدل‌های ERG بیان کننده فرآیندهایی هستند که ویژگی‌های تعیین شده از گراف مشاهده شده را استخراج می‌کنند. در مدل سنتی، داده شامل مجموعه‌ای از مشاهدات است که هر کدام روی تعدادی متغیر مجزا اندازه‌گیری شده‌ است. یک یا تعداد بیشتری از این متغیرها، متغیر پاسخ (وابسته) و بقیهٔ متغیرها به عنوان پیش‌بینی کننده (مستقل) در نظر گرفته می‌شوند. با وجود اینکه این متغیرها ممکن است همبستگی داشته باشند اما به صورت مجزا اندازه‌گیری می‌شوند. در یک شبکه، مشاهدات علاوه بر متغیرهای پاسخ، ویژگی‌های گره را به عنوان متغیر مستقل دربر دارند. اما در ERGM متغیرهای پیش‌بینی کننده عملکرد مستقیم متغیرهای پاسخ هستند، در نتیجه برای گراف مشاهده شده، تنها متغیر پیش‌بینی کننده داریم که پیکربندی‌هایی از گره‌ها مثل مثلث، دوستاره و سه‌ستاره هستند. برای حل این چالش‌ها از مدل ERG استفاده می‌کنیم که با در نظر گرفتن وابستگی متقابل بین مولفه‌ها این چالش‌ها را برطرف می‌کند. به طور مثال در شبکه‌های اجتماعی، افراد گره‌های شبکه هستند و ارتباط بین دو گره مستقل از وجود یا عدم وجود ارتباط بین دیگر گره‌ها نیست. مثلا احتمال ارتباط بین دو نفر در شرایطی که دوست مشترک داشته باشند بیشتر می‌شود (وابستگی مارکف). پس برای تخمین یک شبکه اجتماعی باید این وابستگی‌ها را در نظر گرفت و در نتیجه باید از مدل ERG استفاده کرد. | ## بخش 2: مدل‌های گرافی تصادفی نمایی | این وابستگی بیان می‌کند که اگر گره i و j به یکدیگر متصل باشند؛ این اتصال روی هر اتصال دیگری که شامل i و j است تاثیر می‌گذارد. در واقع وابستگی مارکف بیان می‌کند زمانی که دو اتصال بازیگر مشترک دارند، به صورت شرطی وابسته هستند. به عنوان مثال، رابطه بین پیتر و مری ممکن است وابسته به این باشد که آیا مری به جان وابسته است یا خیر (پیتر و جان دشمن همدیگر هستند). در واقع می‌توان گفت به دلیل اینکه گره m (مری) بین روابط احتمال Pim و Pmj مشترک است، بین این دو احتمال رابطه شرطی برقرار است. مدل ERG برای ساخت مدل گراف تصادفی نمایی از روی یک شبکه واقعی، نیاز به تعیین ویژگی‌های قابل اندازه‌گیری شبکه است که در مدل نشان داده می‌شوند. kN} متوسط طول کوتاه‌ترین مسیر (l) ضریب خوشه‌بندی (C)تعداد مثلث‌ها یا زیرگراف‌های دیگر مثل دوستاره، سه ستاره،.. تراکم: این معیار همان چگالی شبکه است که برابر است با تعداد یال‌های شبکه تقسیم بر (تعداد یال‌های گراف کامل) تعداد مولفه‌های متصل در گرافHandcock, M. گره‌های نامتقارن: این ویژگی تنها می‌تواند در گراف‌های جهت‌دار استفاده شود و برابر تعداد یال‌هایی است که یا (i → j) یا (j → i) وجود دارد. پس از تعیین ویژگی‌ها باید مجموعه تمام گراف‌های ممکن که شبکه واقعی می‌تواند داشته باشد را مشخص کرد؛ {g={G. با توجه به کاربردهای مختلف می‌توان گراف‌های ساده، با حلقه، با یال چندگانه، وزن‌دار یا جهت‌دار را در نظر گرفت اما برای سادگی گراف‌های ساده در نظر گرفته می‌شود. در ERGM توزیع احتمال (P(G به فرم زیر می‌باشد: که Z تابع پارتیشن نامیده می‌شود و می‌تواند با توجه به شرط نرمال بودن محاسبه شود: در نتیجه: اما شبکه همیلتونی را می‌توان به صورت زیر نوشت: که xi(G} مقادیر مشاهدات {xi} برای گراف G هستند و θi} = θ1, θ2, . θr} پارامترهای مجموعه گراف‌ها هستند و مقدار x*i که در شبکه واقعی اندازه‌گیری شده‌ است، با متوسط مقدار درون مجموعه گراف مطابقت دارد، یعنی: برای i = 1, 2, ... مثال اگر فرض کنیم احتمال یک شبکه به تعداد لینک‌ها، تعداد دو ستاره‌ها، تعداد سه ستاره‌ها و تعداد مثلث‌های آن شبکه بستگی داشته باشد، آنگاه: در نتیجه: چالش‌های اصلی ساخت یک مدل ERG دو چالش مهم برای ساخت این مدل مطرح است: از چه ویژگی‌هایی استفاده کنیم؟ به‌طور مثال معمولاً در مدل‌سازی آماری کاربر باید از انتخاب وابستگی‌های خطی بین ویژگی‌ها جلوگیری کند، مثلاً از هر دو ویژگی یال و تراکم در یک مدل استفاده نکند. به همین دلیل از ویژگی‌هایی که در یک زمینه مثلاً شبکه‌های اجتماعی استفاده کرده‌ایم، نمی‌توان برای نشان دادن فرایندها در زمینه دیگری مانند وب غذا استفاده کرد. ویژگی‌های کلی مدل ERG مشاهده واحد به جای مشاهدات متوالی شبکه مشاهده شده را با استفاده از ویژگی‌ها به گروه شبکه‌های تصادفی تغییر می‌دهد. گام قابل توجه به سمت مدل‌سازی صحیح شبکه‌ها به صورت اتفاقی مدل‌های ERG یک توزیع احتمالی روی هر شبکه ممکن از n گره را نشان می‌دهد. به دلیل اینکه تعداد شبکه‌های ممکن در مجموعه بسیار بیشتر از تعداد پارامترهایی است که می‌تواند مدل را محدود کند، توزیع احتمالی ایده‌ال است که آنتروپی گبیز را ماکزیمم کند. | ## بخش 3: مدل‌های گرافی تصادفی نمایی | نمایش مدل‌های مختلف شبکه به صورت خانواده نمایی وقتی وابستگی متقابل بین نودها وجود داشته باشد، تخمین شکل‌گیری شبکه نمی‌تواند در سطح جفت نودها اتفاق بیفتد بلکه باید کل شبکه را در نظر بگیرد. ERGMs این وابستگی‌ها را در نظر می‌گیرد و بنابراین مدل‌های جامعی برای تخمین شکل‌گیری شبکه هستند. 1971 نشان داده شده است، فرم نمایی می‌تواند هر مدل گراف تصادفی را در برگیرد و وابستگی‌های دلخواه درون ارتباطات را نیز شامل شود. علاوه بر این ERGM انواع مدل‌های شکل‌گیری شبکه استراتژیک (انتخابی) را در نظر می‌گیرد. در ERGM احتمال مشاهده یک شبکه (G) به بردار ویژگی‌های آن (S(G بستگی دارد و احتمال شبکه متناسب است با: که β بردار پارامترهای مدل است. هر مدل شبکه را می‌توان به صورت خانواده نمایی با شمارش ویژگی‌های آماری گراف بیان کرد. در این مدل احتمال یک گراف به احتمال هر یال (p) و تعداد یال‌های درون گراف L(G) بستگی دارد. پس: که (S1(G همان ویژگی آماری گراف است که در اینجا (L(G می‌باشد و β1 پارامتر گراف است. مدل کردن شبکه‌های اجتماعی با ERGM تکنیک‌های معروف زیادی وجود دارند که ویژگی‌های یک شبکه را از روی گره‌ها یا زیرمجموعه‌‌ای از گره‌ها اندازه‌گیری می‌کنند (مثلا چگالی، مرکزیت و زیرمجموعه‌های همبسته). این تکنیک‌ها برای توصیف و درک ویژگی‌های شبکه خیلی مفید هستند اما برای یافتن یک مدل مناسب از شبکه اجتماعی مشاهده شده، به دلایل زیر می‌توان فراتر از این تکنیک‌ها رفته و به خصوص از مدل‌های آماری استفاده کرد: به دلیل پیچیدگی رفتارهای اجتماعی، به احتمال زیاد متغیرهایی وجود دارد که بعید است بتوانیم آن‌ها را به درستی شناسایی کنیم، مدل‌های تصادفی این امکان را می‌دهد تا این متغیرها را در نظر بگیریم. همان‌طور که واتس (1999) نشان داده است، "اضافه کردن" مقدار تصادفی کم به یک فرآیند به طور منظم می‌تواند روی ویژگی‌های حاصل تاثیر زیادی بگذارد. گاهی اوقات، فرآیندهای اجتماعی مختلف می‌توانند ساختارهای شبکه مشابهی را پیش‌بینی کنند و تنها با استفاده از مدل‌سازی دقیق، تفاوت پیش‌بینی‌ها را می‌توان ارزیابی کرد. به عنوان مثال، خوشه‌بندی شبکه‌ها ممکن است یا با توجه به ساختار کلی شبکه و یا با توجه به ویژگی‌های گره‌ها به دست آید. برای تصمیم‌گیری بین دو پیشنهاد، نیاز به مدلی است که هر دو اثر را ترکیب کرده و سپس سهم نسبی هر یک را ارزیابی کند. با استفاده از شبکه با ساختار پیچیده‌تر، مدل‌ها به صورت مناسب‌تری فرموله شده و کارایی آنها بالا می‌رود. روش‌های قطعی متنوعی برای تجزیه و تحلیل شبکه‌ها وجود دارد، اما بسیاری از آن‌ها برای مدل کردن اطلاعات پیچیده مناسب نیستند. | ## جمع‌بندی | از این رو می‌توان از روش‌های ساده‌تر به همراه متغیرهای تصادفی برای ایجاد مدل استفاده کرد.