Document Type : Research Article
Authors
Department of Computer Engineering, Faculty of Engineering, Arak University, Arak, Iran
Abstract
Keywords
1- مقدمه[1]
به‌تازگی با سهولت هرچه بیشتر دسترسی به اینترنت و گسترش شبکههای اجتماعی مجازی، افراد بیشتری در حال پیوستن به این گونه شبکه‌ها هستند. در این شبکه‌ها اطلاعات زیادی که انعکاسی از دنیای واقعی‌اند، بین افراد ردوبدل می‌شوند. با بررسی فرآیند انتشار این اطلاعات، اطلاعات پنهان زیادی استخراج میشود [9]. با رشد روزافزون شبکههای اجتماعی و گسترده‌ترشدنشان، تحلیل آنها نیز به‌مراتب پیچده‌تر میشود. یک راه‌حل مناسب برای غلبه بر پیچیدگی یک مسئله، تقسیم آن به زیرمسئله‌های کوچک‌تر است. تحلیل شبکه‌ها و به‌طور خاص، تحلیل شبکههای اجتماعی نیز از همین قاعده پیروی می‌کند و برای غلبه بر پیچیدگی، می‌توان آن را به زیرشبکه‌های کوچک‌تر به نام اجتماع تقسیم کرد. تشخیص اجتماعات در شبکه‌ها یک موضوع چالشی در یک دهه گذشته بوده و مطالعات زیادی دربارۀ این موضوع انجام شده است. مطالعات جامعه‌شناختی نشان می‌دهد بسیاری از رفتارها و تصمیمات اشخاص، از افراد بانفوذی تأثیر می‌گیرد که شخص به نحوی ازطریق اجتماعات مختلف با آنها ارتباط دارد. در دنیای مجازی نیز بسیاری از رفتارها و تصمیمات اشخاص، از افراد پرنفوذ تأثیر می‌گیرد که به نحوی در اجتماعاتِ مجازی مختلف با آنها در تعامل‌اند؛ درنتیجه، افراد پرنفوذ نقش مهمی در راستای تغییر رفتار دیگران دارند؛ بنابراین، شناسایی افراد پرنفوذ و تشخیص اجتماعات آنان در شبکههای اجتماعی اهمیت زیادی دارد.
شبکههای اجتماعی همانند سایر شبکههای پیچیده، ویژگی‌های ماژولاریتی سلسله‌مراتبی[1]و مستقل از مقیاس[2] دارند [1, 2]. ماژولاریتی به این معناست که شبکه‌ها عموماً شامل اجتماعات (یا ماژول‌ها) با ارتباطات داخلی چگال و ارتباطات خارجی خلوت‌اند. سلسله‌مراتبی به این معناست که درون هر یک از اجتماعات، اجتماعات دیگری وجود دارند. بیشتر روش‌های تشخیص اجتماعِ مشهور شامل نوعی بهینه‌سازی یک تابع کیفیت است. یکی از مشهورترین توابع کیفیت، Newman-Girvan modularity [3] است که با وجود برخی اشکالات [4, 5] به‌عنوان تابع هدف برای تخمین کیفیت استحکام اجتماعات استفاده میشود. این تابع پراستفاده‌ترین و مشهورترین تابع کیفیت برای تشخیص اجتماع است [6].
بیشینهسازی ماژولاریتی، یکی از روش‌های مدرن و مناسب برای تشخیص اجتماع است؛ البته بیشینهسازی ماژولاریتی یک مسئله NP-hard است [7]؛ مگر اینکه P=NP باشد؛ بدین معنی که هیچ الگوریتم شناخته‌شده‌ای وجود ندارد که در زمان چندجمله‌ای مسئله را حل کند. یک رویکرد برای حل مسائل NP-hard الگوریتم‌های تقریب است که کیفیت راه‌حل را ضمانت می‌کند. پیچیدگی زمانی یک الگوریتم تقریب لزوماً چندجمله‌ای است و آن را با میزان خطای بدترین حالت ممکن روی همۀ نمونه‌های مسئله ارزیابی می‌کنند [8]. به یک الگوریتم برای حل یک مسئلۀ بیشینهسازی، الگوریتم گویند. اگر برای هر نمونه از مسئله، جواب، حداقل امِ مقدار بهینه باشد ( )، به نرخ تقریب گفته میشود.
با رشد سریع شبکههای اجتماعی، داده‌های حجیم با سرعت زیادی تولید می‌شوند؛ از همین رو مسائل مرتبط با اینگونه شبکه‌ها با چالشی به نام کلان داده نیز روبه‌رو می‌شوند. به‌طور کلی زمانی که با کلان داده‌ها روبه‌رو هستیم، دو رویکرد برای مسئلۀ تشخیص اجتماعات وجود دارد؛ یک رویکرد، مدیریت تشخیصِ سطح به سطح (تشخیص اجتماع چند سطحی) و دیگری رویکرد کاهش گراف است [11].
هدف اصلی در الگوریتم‌های مبتنی بر مفهوم چندسطحی، ایجاد سلسله‌مراتبی از مسئله است. درحقیقت اندازۀ گراف اولیه، سطح به سطح با درهم‌آمیختن گرهها و یال‌ها کاهش پیدا می‌کند. اینگونه الگوریتم‌ها شامل سه مرحلۀ درشت‌سازی، تفکیک، بازگشت به حالت اولیه و پالایش‌اند. الگوریتم‌های زیادی بر مبنای این رویکرد پیشنهاد شدهاند که به [3, 12-16] اشاره میشود.
در رویکرد کاهش گراف، ایدۀ اصلی، کاهش اندازۀ گراف بدون از بین رفتن کیفیت راه‌حل یا تغییر ساختار گراف است. به این ترتیب، هزینۀ محاسبات روی گراف کاهش می‌یابد. یکی از روش‌های کاهش گراف، نمونه‌گیری[3] است. در این روش‌ها یک زیرمجموعه از گرهها یا یال‌ها انتخاب میشود. این روش‌ها به سه دسته تقسیم می‌شوند: (الف) نمونه‌گیری گره مانند [17] (ب) نمونه‌گیری یالی مانند [18] (ج) نمونه‌گیری براساس پیمایش مانند [19].
روش‌های تشخیص اجتماع براساس معیار کیفیت سنجی نیز دسته‌بندی می‌شوند. در منابع، آنها را به دو دسته الگوریتم‌ها براساس ماژولاریتی[4]و بدون ماژولاریتی[5] دسته‌بندی می‌کنند.
یک نوع از الگوریتم‌های بدون ماژولاریتی، خوشه‌بندی طیفی[6] هستند (به‌طور مثال، [20]). این الگوریتم‌ها براساس مفهوم تقسیم‌بندی گراف در زیرشبکه‌هایی به نام برش‌ها[7]کار می‌کنند. هدف، مینیمم‌سازی تعداد برش‌های تولیدشده است. نوع دیگری از الگوریتم‌های بدون ماژولاریتی، الگوریتم‌های پیداکردن اجتماعاتِ هم‌پوشان هستند؛ برای نمونه، یکی از الگوریتم‌های رایج COPRA [21] است که از این تکنیک استفاده می‌کند.
همان‌طور که گفته شد الگوریتم‌های براساس ماژولاریتی، از یک معیار به نام ماژولاریتی برای ارزیابی کیفیت تقسیم‌بندی استفاده می‌کنند. این معیار معمولاً با Q نشان داده میشود و الگوریتم به دنبال پیداکردن یک تقسیم‌بندی است که Q را بیشنه کند. تکنیک حریصانه، یکی از روش‌ها براساس ماژولاریتی است که در [13] ارائه شده است. در [22] و [23]، الگوریتم‌هایی براساس مدل‌های ریاضی برای بیشینهسازی ماژولاریتی با کیفیت بالا ارائه شده است که البته مقیاس‌پذیر نیستند. در چندین مقاله نیز از تکنیک تقریب برای حل مسئله استفاده شده است؛ به‌طور مثال، در [25] نویسندگان دو الگوریتم تقریب برای شناسایی اجتماعات در شبکههای اجتماعی پویا پیشنهاد داده‌اند. Dinh و همکاران در [6] الگوریتم‌هایی برای مسئلۀ بیشینهسازی ماژولاریتی در شبکههای مستقل از مقیاس ارائه کرده‌اند. این الگوریتم‌ها براساس درجۀ گرهها کار می‌کنند و هر گره را براساس برخی قواعد به عضو[8]، سرگروه [9]و مدارگرد[10]برچسب‌گذاری می‌کنند. سپس هر سرگروه، یک اجتماع تشکیل می‌دهد و دنبال‌کننده‌هایش یعنی عضوها و مدارگردها را به آن اجتماع انتساب می‌دهند. برخی نیز روش‌هایی پیشنهاد کرده‌اند که عملکرد روش‌های گذشته را بهبود می‌بخشد؛ مانند [23, 24] که در آنها از تکنیک وزن‌دهی مجدد برای بهبود تشخیص اجتماع براساس بیشینهسازی ماژولاریتی استفاده شده است.
همچنین، دربارۀ مسئلۀ بیشینهسازی نفوذ نیز کارهای زیادی صورت پذیرفته است. Banerge و همکاران در [24] این روش‌ها را به 5 دسته تقسیم کرده‌اند؛ دستۀ نخست، روش‌های تقریبی‌اند که یک کران برای بدترین حالت انتشار نفوذ ارائه می‌دهند. Kempe و همکاران [25] نخستین کسانی بودند که یک الگوریتم حریصانۀ ساده با کران پیشنهاد کردند و کارهای [26] و [27] در راستای بهبود آن گام برداشتند؛ البته بسیاری از این روش‌ها از مقیاس‌پذیر نبودن رنج می‌برند؛ یعنی با افزایش اندازۀ شبکه، زمان اجرا به‌طور فوق‌العاده‌ای زیاد میشود. یک رویکرد برای غلبه بر این چالش، نمونه‌گیری از شبکه است که در [28] و [29] استفاده شده است. این رویکرد براساس مجموعههای دردسترس معکوس تصادفی[11] (RR) قادر بوده‌اند با استفاده از نمونه‌برداری، حداکثر انتشار نفوذ را با یک میزان خطای مشخص تقریب بزنند. دستۀ دوم، روش‌های مکاشفه‌ای هستند (مانند [30]) که هرچند در بیشتر مواقع مقیاس‌پذیرند، قادر به ارائۀ هیچ کرانی برای بدترین حالت برای انتشارنفوذ نیستند. دستۀ سوم، راه‌حل‌های فرامکاشفه‌ای هستند که براساس تکنیک‌های محاسبات تکاملی کار می‌کنند (مانند روش [31]). این الگوریتم‌ها نیز هیچ کرانی برای بدترین حالت انتشار نفوذ ارائه نمی‌دهند. دستۀ چهارم، راه‌حل‌ها براساس اجتماعات هستند (مانند [32]) که الگوریتم‌های این دسته از شناسایی اجتماعات در شبکۀ اجتماعی به‌عنوان یک اقدام واسط برای کاهش اندازۀ مسئله در سطح اجتماع و بهبود مقیاس‌پذیری عمل می‌کنند. دستۀ آخر مواردی‌اند که در هیچ‌یک از دسته‌بندی‌های فوق قرار نمی‌گیرند.
در این مقاله، با استفاده از شناسایی گرههای پرنفوذ، یک الگوریتم تقریب برای مسئلۀ بیشنه‌سازی ماژولاریتی ارائه شده است. نرخ تقریب الگوریتم نیز با استفاده از مفاهیم شبکههای مستقل از مقیاس اثبات شده است. در شناسایی افراد پرنفوذ از رویکرد نمونه‌گیری استفاده میشود که این کار معمولاً با برخی اقدامات کیفی هدایت‌پذیر است و می‌توان از یکسری اطلاعات اضافی مانند ویژگی‌های گرهها بهره برد [10]. پس رویکرد ما علاوه بر مقیاس‌پذیری، انعطاف‌پذیر نیز خواهد بود؛ به این معنا که می‌توان تقسیم‌بندی یک شبکۀ اجتماعی را براساس یکسری ویژگی‌های مربوط به گرهها هدایت کرد.
در بخش 2 مفاهیم اولیه بیان شدهاند. در بخش 3، الگوریتم پیشنهادی برای شبکههای مستقل از مقیاس بدون جهت مطرح شده و سپس در بخش 4 الگوریتم برای شبکههای جهت‌دار تعمیم داده شده است. در بخش 5، نتایج آزمایشات روی چندین شبکۀ کوچک و شبکههای اجتماعی بزرگ نشان داده می‌شوند. در انتها در بخش 6 نتیجه‌گیری شده است.
2- تعریف مفاهیم اولیه
در این بخش، ابتدا مسئلۀ بیشینهسازی ماژولاریتی، معرفی و سپس تابع ماژولاریتی توصیف میشود و پس از آن، چارچوب RIS [12]و نحوۀ شناسایی گرههای پرنفوذ به‌عنوان هستۀ اجتماع معرفی میشود. در انتهای این بخش نیز شبکههای مستقل از مقیاس معرفی می‌شوند.
برخی نمادهای استفاده‌شده در این مقاله در جدول (1) آمده‌‌اند.
جدول (1) خلاصه نمادها
|
نماد |
مفهوم |
|
گراف (شبکه) اجتماعی |
|
|
مجموعه گرهها (یال‌ها) |
|
|
تعداد گرهها (یال‌ها) |
|
|
یک مجموعه معکوس نفوذ(RR) |
|
|
مجموعه از مجموعههای معکوس نفوذ (مجموعه از RRها) |
|
|
درجه‌های ورودی و خروجی گره i |
|
|
مجموعه‌ای از اجتماعات |
|
|
تعداد گرههایی که دو انتها آنها در اجتماع است |
|
|
مجموع درجات گرهها در اجتماع |
|
|
حد آستانه پیمایش گراف |
|
|
نرخ توزیع درجات |
|
|
Q |
ماژولاریتی |
1-2- تعریف بیشینهسازی ماژولاریتی
یک شبکه با گراف نشان داده میشود. تعداد گرهها n ( ) و تعداد یال‌ها m است ( ). همچنین، برای G یک ماتریس همجواری به‌صورت تعریف میشود؛ به طوری که. اگر بین و یک یال وجود داشته باشد، است؛ در غیر این صورت، است. ضمناً درجۀ گرۀ i با نشان داده شد.
مفهوم ماژولاریتی طبق تعریف موجود در [3]، یک معیار برای اندازه‌گیری کیفیت تقسیم‌بندی گرههای یک گراف ( ) به یک مجموعه از زیرمجموعه‌های مجزا از گرهها است که اجتماع این زیرمجموعه‌ها همان است. این مجموعه با نشان داده میشود. به هر یک از این زیرمجموعه‌ها (یعنی به هر یک از ) یک اجتماع گفته میشود. ماژولاریتی (Q) نسبت تعداد یال‌های هم‌نوع (یعنی یال‌های درون یک اجتماع) به کل یال‌های شبکه منهای امیدِ همین نسبت در شبکه‌ای با تقسیم‌بندیِ یکسان منتها با اتصالات تصادفی بین گرهها است. هدف از بیشینهسازی ماژولاریتی این است که یال‌های بیشتری در درون اجتماعات نسبت به زمانی باشد که یکسری اجتماعات تصادفی از گرههای گراف وجود دارد. اگر تعداد گرههای درون - اجتماع، بهتر از یک حالت تصادفی نباشد، مقدار Q نزدیک به صفر خواهد بود؛ در حالی که مقدار نزدیک به یک نشان‌دهندۀ شبکه‌هایی با ساختار اجتماعِ قوی است. به‌طور رسمی، ماژولاریتی مطابق رابطه‌ی (1) تعریف میشود [6]:
|
|
(1) |
جایی که است، اگر و در یک اجتماع باشد و در غیر این صورت، است. هدف مسئلۀ بیشینهسازی ماژولاریتی، یافتن یک تقسیم‌بندی از گرههای گراف است که ماژولاریتی را بیشینه کند. ماژولاریتی مطابق رابطۀ (2) تعریف میشود [6]:
|
(2) |
جایی که تعداد یال‌هایی است که هر دو انتهای آن در اجتماع است و برابر حجم یعنی مجموع درجه تمام گرهها در است.
2-2- چارچوب نمونه‌گیری معکوس نفوذ (Reverse Influence Sampling)
در این زیربخش، ابتدا چارچوب RIS برای پیداکردن گرههای پرنفوذ ارائه میشود. به همین منظور، در ابتدا یکی از مهم‌ترین مدل‌های انتشار یعنی مدل انتشار آبشاری - که در این پژوهش لحاظ شده است - معرفی و سپس اصول چارچوب RIS تعریف میشود.
1-2-2 مدل انتشار
مدل‌های زیادی برای شبیه‌سازی انتشار نفوذ در گراف اجتماعی وجود دارد. در این مقاله، تنها بر مدل آبشار مستقل تمرکز شده است. همچنین، فرض میشود تنها گرههای پرنفوذ در دورۀ صفر فعال‌اند و سعی در فعال‌کردن گرههای همسایه در دوره‌های بعدی را دارند. فرآیند انتشار مدل به‌صورت زیر توصیف میشود.
مدل آبشار مستقل[13] (IC) زمانی که یک گره فعال میشود، در هر دوره به استثنای دوره صفر، تنها یک شانس دارد که هر یک از همسایه‌های غیرفعال خود (به فرض ) را با احتمال موفقیت فعال کند که نسبتی از وزن یال است. درضمن، هر گره فعال تا انتهای فرآیند انتشار، فعال باقی می‌ماند.
2-2-2- اصول RIS
Borgs و همکارانش در [33] روش نمونه‌برداری معکوس نفوذ (RIS) را ارائه کرده‌اند. این روش، یک چشم‌انداز از نفوذ در گراف G را با ایجاد یک کلکسیون از مجموعههای دسترس‌پذیر معکوس تصادفی (به نام RR) به دست می‌آورد.
تعریف 1: مجموعههایRR یا مجموعههای دسترس‌پذیر معکوس [29]: فرض کنید گراف داده شده است، یک مجموعۀ تصادفیِ RR (که با نشان داده میشود)، به این صورت از G ایجاد میشود: 1) یک گرۀ تصادفی ( ) از انتخاب میشود؛ 2) یک گراف نمونه ( ) از تولید میشود و 3) ایجاد مجموعۀ به‌عنوان یک مجموعه از گرههای که می‌توانند به دسترسی پیدا کنند.
بنابراین مجموعۀ گرههایی است که می‌توانند بر تأثیر بگذارند. اگر چندین مجموعۀ تصادفیِ RR تولید شود، احتمالاً گرههای پرنفوذ به تناوب در این مجموعه‌ها ظاهر خواهند شد.
یک موضوع مهم در این چارچوب این است که مینیمم اندازۀ مجموعۀ یا به عبارتی، تعداد نمونه‌ها (یعنی تعداد ها) چیست؟ پاسخ به این سؤال مستلزم دانستن کران میزان خطای پذیرفته‌شدۀ و احتمال خطا است که به تقریب معروف است و با نمایش داده میشود.
تعریف 2: یک الگوریتم تصادفی یک تقریب برای مقدار V ارائه می‌دهد. اگر X که خروجی الگوریتم است، در رابطه صدق[14] کند، تعداد نمونه‌هایی که این شرط را اقناع می‌کند، حداقل برابر است با .
3-2- شبکههای مستقل از مقیاس
برای تحلیل کارایی الگوریتم، ابتدا لازم است گراف به‌صورت رسمی تعریف شود. با توجه به اینکه شبکههای اجتماعی مستقل از مقیاس‌اند، چنین شبکه‌هایی از توالی درجه توان پایه پیروی می‌کنند. به همین منظور، یک مدل از گراف تصادفی در نظر گرفته میشود که از توزیع درجه وابسته به دو مقدار مفروض و پیروی می‌کند.
فرض کنید گره با درجه وجود دارد، به طوری که رابطه را اقناع کند. به عبارت دیگر، ؛ به طوری که لگاریتم تعداد گرهها از درجه یک است و نرخ توزیع درجات است. واقعیت‌های زیر از این مدل استنتاج میشود:
1) بیشترین درجه گراف است.
تعداد گرهها و یال‌های گراف از روابط (3) و (4) به دست می‌آید:
|
|
(3) |
|
(4) |
جایی که تابع ریمان زتا به‌صورت است که برای همگرا و برای واگرا است.
درخور ذکر است اگر از اعداد حقیقی به جای اعداد صحیح گردشده استفاده شود، ممکن است باعث خطا شود؛ اما این خطا در اثبات این مقاله، به اندازۀ کافی کوچک است.
3- الگوریتم تقریب برای بیشینهسازی ماژولاریتی
در این بخش، یک الگوریتم با ضریب تقریب ثابت برای مسئلۀ بیشینهسازی نفوذ برای شبکههای مستقل از مقیاس ارائه میشود. ایدۀ اصلی این روش این است که اجتماعات اطراف گرههای پرنفوذ شکل می‌گیرند؛ بنابراین، اگر بتوان گرههای پرنفوذ را پیدا کرد و وزن یال‌های گراف را براساس تمایل هر گره برای ارتباط با همسایه‌هایش تقریب زد (یعنی احتمال نفوذ)، می‌توان بیشینهسازی ماژولاریتی را با پیمایش گراف اطراف گرههای پرنفوذ تقریب زد.
3-1- پیمایش گراف براساس احتمال نفوذ
الگوریتم پیمایش گراف براساس احتمال نفوذ (GTPI)، همان‌گونه که در الگوریتم 1 نشان داده شده، به این صورت است که ابتدا برای هر گره یک یا چند مجموعه دسترس‌پذیر معکوس (RR) ایجاد می‌کند، به طوری که تعداد زنجیره‌های RR حداقل باشد. سپس براساس تخمین تمایل هر گره برای ارتباط با همسایه‌هایش (یعنی احتمال نفوذ) یال‌های گراف وزن‌دهی می‌شوند. میانه وزن یال‌های گراف، همان‌گونه که در بخش 3-2 گفته شده است، به‌عنوان حد آستانۀ گراف برای پیمایش محاسبه میشود. همچنین، کلکسیونی از مجموعههای RR، یعنی نیز برای شناسایی گرههای پرنفوذی استفاده میشود که هنوز متعلق به هیچ اجتماعی نیستند. این گرههای پرنفوذ به‌عنوان هستۀ اجتماعات استفاده می‌شوند. گرههای پرنفوذ، بیشتر از دیگر گرهها در مجموعه تکرار می‌شوند. از این گرهها شروع به پیمایش گراف به‌منظور مشخص‌کردن حوزۀ نفوذ استفاده میشود؛ بنابراین، هر بار تأثیرگذارترین گره‌ای شناسایی میشود که جزء هیچ اجتماعی نیست و از آن به‌عنوان گره شروع‌کنندۀ پیمایش گراف استفاده میشود. سپس گراف، حداکثر به فاصله 2 از هسته اجتماع (گره پرنفوذ) پیمایش میشود (الگوریتم اول سطح در بخش 3-2 را ببینید). این دسته از گرههای پیمایش‌شده با همان شماره اجتماع گره پرنفوذ هسته برچسب‌گذاری می‌شوند. این کار تا جایی ادامه می‌پذیرد که هیچ گره‌ای بدون برچسب شمارۀ اجتماع وجود نداشته باشد.
در آخر الگوریتم یک، بدون خدشه وارد کردن به ضمانت تقریب یک بهینه‌سازی روی اجتماعات به‌دست‌آمده انجام می‌پذیرد؛ به این صورت که برای هر یک از اجتماعات به‌دست‌آمده یک گره انتزاعی در نظر گرفته میشود که درجۀ آن برابر با مجموع درجات تمام گرههای درون آن اجتماع است و الگوریتم تا زمانی که بهبود در ماژولاریتی داشته باشد، به‌صورت بازگشتی اجرا میشود. سرانجام نیز یک متد جستجوی محلی برای افزایش ماژولاریتی کلی صورت می‌پذیرد.
|
|
|
{
} |
شکل )1): الف) یک ساختار اجتماع با مقدار ماژولاریتی بهینه که با CPLEXبه دست آمده است. ب) یک ساختار اجتماع که با الگوریتم GTPIبه دست آمده است (بهترین نتیجۀ حاصل از ده بار اجرای الگوریتم)
3-2- الگوریتم پیمایش اول سطح (BFS)
الگوریتم پیمایش اول سطح به این صورت است که ابتدا گره v به‌عنوان شروع‌کنندۀ پیمایش و مقدار آستانه نفوذ را می‌گیرد و با توجه به ماتریس همجواری و ماتریس وزن‌دار W سعی می‌کند گرههایی را مشخص سازد که با گره v در یک اجتماع قرار می‌گیرند، به این صورت که ابتدا همسایه‌ها گره را مشخص می‌کنند و سپس برای هر گره در همسایگی اگر وزن یال از حد آستانه بیشتر بود، گره نیز به همان اجتماع گره می‌پیوندد و همین روند برای همسایه‌های گره تکرار میشود؛ یعنی در صورت برقراری شرط (وزن یال بیشتر از حد آستانه باشد)، همسایه‌های گره نیز به همان اجتماع گره می‌پیوندند.
|
|
|
|
3-3- الگوریتم پیداکردن گره پرنفوذ
پیداکردن گره پرنفوذ یک الگوریتم حریصانه است. الگوریتم هر بار گره را با بیشترین سود حاشیه‌ای، یعنی گره‌ای که بیشترین حضور را در مجموعههای RR دارد که قبلاً متعلق به هیچ اجتماعی نیستند را به‌عنوان گره پرنفوذ انتخاب می‌کند.
|
|
|
|
یک مثال از الگوریتم GTPI در شکل 1 نشان داده شده است. الگوریتم ابتدا وزن هر یال را محاسبه می‌کند و به آن انتساب می‌دهد. وزن هر یال به‌صورت محاسبه میشود؛ جایی که نشان‌دهندۀ درجۀ ورودی است. همچنین، مقادیر و تنظیم شدهاند. بر اساس این، حداقل تعداد نمونه‌ها است که هر یک از 18 گره گراف به‌ترتیب و تناوب به‌عنوان شروع‌کنندۀ زنجیرۀ نفوذ (RR) انتخاب می‌شوند. با ایجاد هر نمونه RR، شماره آن (یعنی #RR) در لیست تک‌تک گرههای موجود در مجموعه RR، اضافه میشود. این مجموعه از لیست‌ها برای وزن‌دهی یال‌های گراف استفاده میشود. وزن هر یال برابر است با نسبت تعداد اشتراک listهای هر دو گره و (یعنی هر دو در چند زنجیرۀ نفوذ به‌طور مشترک حضور دارند) به مجموع اندازه‌های لیست‌های و . بعد از این کار، میانه وزن یال‌ها به‌عنوان آستانۀ پیمایش استفاده میشود. اکنون تا زمانی که همۀ یال‌ها برچسب اجتماع نخورده‌اند، گره‌ای با بیشترین نفوذ انتخاب میشود که جزء هیچ اجتماعی نیست (برای مثال، گره شماره 2) و سپس به‌صورت پیمایش اول سطح تا فاصله دو از گره منبع (گره با نفوذ)، به شرطی که وزن یال بین دو گره بیشتر از حد آستانه باشد، پیمایش میشود. هر گره‌ای که پیمایش شد، با همان برچسب اجتماع گره منبع برچسب‌گذاری میشود.
به سبب آنکه الگوریتم برای گراف شکل 1 به‌صورت تصادفی اجرا میشود، الگوریتم 10 بار اجرا شده که بهترین ماژولاریتی 0.4366 برابر با ماژولاریتی بهینه است و بدترین حالت 0.2243 است که بیش از نیمی از ماژولاریتی بهینه است. همان‌طور که در شکل 1) ب مشاهده میشود، نتیجۀ تقسیم‌بندی گراف برابر با مقدار بهینه است.
تئوری 1: برای شبکۀ مستقل از مقیاس با ، ماژولاریتی ساختار اجتماع که با الگوریتم GTPI به دست می‌آید، حداقل خواهد بود؛ جایی که یک ثابت کوچک دلخواه باشد.
اثبات: بر طبق تعریف ماژولاریتی، ابتدا باید یک کران پایین برای قسمت اول و یک کران بالا برای قسمت دوم معادله (2) به دست آید. به همین منظور، یک کران پایین برای تعداد یال‌هایی که هر دو انتهای آن در یک اجتماع است و با نشان داده میشود و یک کران بالا برای مجموع درجه گرهها داخل هر اجتماع ارائه میشود.
نخست برای یک کران پایین لازم است به دنبال یال‌هایی در اجتماعات بود که هر دو انتهای آن در یک اجتماع باشند. الگوریتم GTPI به این صورت است که برای هر اجتماع، گره پرنفوذی به‌عنوان هستۀ اجتماع پیدا میشود که قبلاً متعلق به هیچ اجتماعی نباشد. سپس گراف به‌صورت اول سطح با شروع از آن گره پرنفوذ به شرط آنکه وزن یال از بیشتر باشد، شروع به پیمایش می‌کند، سپس به سمت گرههای همجواری می‌رود که تا کنون متعلق به لیست هیچ گره همجواری نبوده‌اند و آنها را به اجتماع اضافه می‌کند.
با توجه به معادله 5، با توجه به اینکه حد آستانۀ کمی کمتر از میانه در نظر گرفته شده است، وزن نصف یال‌ها بیشتر از این آستانه خواهد بود و عملاً دو انتهای بیش از نصف یال‌ها در یک اجتماع‌اند:
|
(5) |
|
حال نوبت آن رسیده است که یک کران بالا برای حجم درجه گرهها محاسبه شود. فرض کنید اولین گره پرنفوذ با درجه باشد، با توجه به اینکه پیمایش به آستانه و درجه بستگی دارد، تعداد کمی از همسایه‌های پیمایش‌شده به اجتماع اضافه می‌شوند. پس میانگین تعداد همسایه‌های هر گره برابر است با و طبق معادله 3 و 4 با جای‌گذاری و داریم .
درواقع یک جستجوی اول سطح تا فاصله 2 از گره پرنفوذ انجام می‌پذیرد، پس کران بالا برای حجم درجه گره برابر است با:
|
(6) |
|
و درنتیجه، با استفاده از معادلات 5 و 6 خواهیم داشت:
|
(7) |
3-4- پیچیدگی و تعیین حد آستانه
وزن‌دهی مجدد یال‌های گراف نقش مهمی در الگوریتم GTPI دارد. به همین منظور، لازم است نخست، مجموعه‌ای از RRها تولید شود و سپس اشتراک لیست (حضور) هر دو گره همسایه محاسبه شود؛ بنابراین، اگر متوسط اندازۀ هر مجموعه RR، در نظر گرفته شود و باشد، پیچیدگی الگوریتم برای فاز وزن‌دهی و برای فاز پیمایش خواهد بود.
3-5- تعیین حد آستانه
آستانه نقش مهمی در الگوریتم GTPI دارد و طبق تعریف ماژولاریتی در معادله 2، و رابطۀ مستقیمی با حد آستانه دارند.
برای تعیین حد آستانه، فرض کنید پیمایش گراف از گره شروع میشود و طبق الگوریتم یال‌هایی که وزن آنها از بیشتر است، پیمایش می‌شوند. پس تعداد از یال‌ها دو انتهای آنها در یک اجتماع قرار می‌گیرد. همچنین، دو برابر یال‌هایی است که داخل اجتماعات قرار دارند؛ بنابراین، ؛ درنتیجه، از معادله 2 خواهیم داشت:
|
(8) |
رابطه 8 زمانی بیشینه است که مشتق آن برابر صفر شود؛ بنابراین، خواهیم داشت:
|
(9) |
4- بیشینهسازی ماژولاریتی در شبکههای جهت‌دار
بسیاری از شبکههای پیچیده ذات جهت‌دار دارند، جهت یال‌ها اطلاعات دقیق‌تری از روابط بین موجودیت‌های شبکه ارائه می‌دهد. به همین منظور، لازم است جهت یال‌ها در تشخیص اجتماع در نظر گرفته شود.
در اینجا الگوریتم GTPI برای شبکههای جهت‌دار تعمیم داده شده است. برای انجام این کار، ابتدا برخی تعاریف ارائه می‌شوند. برای یک گراف جهت‌دار مفروض، درجۀ ورودی و درجۀ خروجی گره i به‌ترتیب با و نشان داده میشود. همچنین، مجموعه همسایه‌های ورودی با و مجموعه همسایه‌های خروجی با نشان داده میشود. با تعریف و معادله 1 برای گراف‌های جهت‌دار اصلاح میشود. اکنون در گراف جهت‌دار احتمال وجود یک یال از گره به گره برابر با خواهد بود. بدین ترتیب، معادله 1 به‌صورت معادله 10 اصلاح میشود:
|
(10) |
الگوریتم تقریب بیشینهسازی ماژولاریتی برای گراف‌های جهت‌دار به نام DGTPI اساساً شبیه به الگوریتم GTPI است، با این تفاوت مهم که بین و تمایز در نظر گرفته میشود.
بنابراین، ماژولاریتی تقسیم‌بندی گراف به‌صورت معادله 11 محاسبه میشود:
|
(11) |
جایی که برابر است با تعداد یال‌های جهت‌دار که دو انتهای آنها در است. برای اثبات ضمانت تقریب، نخست، یک کران پایین برای ارائه میشود. با توجه به اینکه هر یال براساس پیمایش میشود و تعیین این مقدار آستانه در قسمت 3-5 توضیح داده شد، برای آنکه بیشترین مقدار را داشته باشیم، این مقدار آستانه برابر ½ در نظر گرفته میشود و بنابراین، و بنابراین، کران پایین برای آن برابر است با .
اما برای کران بالا برای قسمت دوم معادله خواهیم داشت:
|
(12) |
درنتیجه:
|
5- نتایج آزمایش‌ها
در این قسمت، کارایی الگوریتم GTPI برای چندین شبکۀ پیچیده کوچک و بزرگ ارزیابی شده است.
5-1- شبکههای کوچک
نخست، الگوریتم GTPI با چندین روش بیشینهسازی ماژولاریتی روی چندین مورد شبکه مشهور با اندازه کوچک برای تشخیص اجتماع مقایسه میشود. نام دیتاست‌ها همراه با اندازۀ آنها در جدول 2 آورده شده است. الگوریتم پیشنهادی با سه الگوریتم دیگر مقایسه شده که الگوریتم LDF [6] به دلیل استفاده از رویکرد مشابه، یعنی تقریب‌زدن جواب بهینه و الگوریتم MCCA [12] به لحاظ استفاده از رویکرد مدیریت تشخییص سطح به سطح برای غلبه بر چالش کلان داده (مقیاس‌پذیری) و الگوریتم (MILP) [22] انتخاب شدهاند که توانایی محاسبۀ ماژولاریتی بهینه را دارد.
تمام آزمایش‌های انجام‌شده روی PC با سیستم عامل لینوکس و با پردازشگر Intel Core i7, 7700 و 16GB RAM انجام شده است. همچنین، پیاده‌سازی الگوریتم‌ها با زبان C++ صورت پذیرفته است. مقادیر ماژولاریتی به‌دست‌آمده با الگوریتم‌های مختلف در جدول 3 نشان داده شدهاند.
5-2- شبکههای اجتماعی واقعی
آزمایش های بیشتر برای ارزیابی الگوریتم روی دید لحظه‌ای[15]از چهار شبکۀ اجتماعیFoursq, Facebook Twitter و Flicker انجام شدهاند.
اندازۀ شبکههای اجتماعی به همراه ماژولاریتی الگوریتم‌ها MCCA, LDF and GTPI در جدول 4 نشان داده شده است. درخور ذکر است الگوریتم MILP به لحاظ ناتوانی اجرا روی شبکههای بزرگ در نظر گرفته نشده است. هر سه الگوریتم مقیاس‌پذیر بوده و در زمان معقولی روی این دیتاست‌ها اجرا شدهاند. الگوریتم GTPI کارایی بهتری روی شبکههای اجتماعی با پایۀ توان کمتر یعنی شبکههای Foursq and Twitter داشته است. هرچه پایه توان) ( کمتر باشد، گراف چگال‌تر خواهد بود. هرچه گراف چگال‌تر باشد، واریانس اندازۀ زنجیره‌های RR کمتر است؛ ازاین‌رو، دقت در تشخیص گرههای بانفوذ ببیشتر میشود. با تشخیص بهتر گرههای بانفوذ، هستۀ اجتماعات بهتر تشخیص داده میشود و ماژولاریتی بهتری به دست خواهد آمد.
6-نتیجه‌گیری
در این مقاله، الگوریتم‌های تقریبی برای بیشینهسازی ماژولاریتی براساس این ایده ارائه شده است که گرههای پرنفوذ در هستۀ اجتماعات‌اند و با تعیین دامنۀ نفوذ آنها اجتماعات، تشخیص داده میشود
جدول 2: ویژگی‌های دیتاست‌ها
|
تعداد یال‌ها (m) |
تعداد گرهها (n) |
نام |
شناسه |
|
78 |
34 |
Zachary’s karate club |
1 |
|
159 |
62 |
Dotphin’s social network |
2 |
|
254 |
77 |
Les Miserables |
3 |
|
441 |
105 |
Books about US politics |
4 |
|
613 |
115 |
American College Footbal |
5 |
|
819 |
512 |
Electronic Circuit(s838) |
6 |
جدول 3: مقادیر ماژولاریتی به‌دست‌آمده از الگوریتم‌های [12] MCCA ، LDF [6]، GTPI (بهترین و بدترین حالت) و مقادیر ماژولاریتی بهینه(MILP) [22] برای شبکههای کوچک
|
ماژولاریتیبهینه(MILP) |
GTPI(best) |
GTPI(worst) |
MCCA |
LDF |
n |
شناسه |
|
0.4198 |
0.4198 |
0.2571 |
0.4198 |
0.4198 |
34 |
1 |
|
0.5285 |
0.5285 |
0.3814 |
0.5274 |
0.5179 |
62 |
2 |
|
0.5600 |
1.5600 |
0.4982 |
0.5532 |
0.5600 |
77 |
3 |
|
0.5272 |
0.5270 |
0.3694 |
0.5265 |
0.5257 |
105 |
4 |
|
0.6046 |
0.6046 |
0.5516 |
0.6014 |
0.6028 |
115 |
5 |
|
0.8194 |
0.8179 |
0.6120 |
0.8168 |
0.8159 |
512 |
6 |
جدول 4: مقادیر ماژولاریتی به‌دست‌آمده از الگوریتم‌های MCCA[12] LDF [6] و GTPI
|
GTPI |
LDF |
MCCA |
تعداد یال‌ها |
تعداد گرهها |
نام شبکه اجتماعی |
|
|
0.4512 |
0.4502 |
0.4498 |
1.64 |
1664k |
45k |
Foursq |
|
0.6218 |
0.6414 |
0.6467 |
2.27 |
906k |
64k |
|
|
0.5507 |
0.5470 |
0.5491 |
1.69 |
2364 |
88k |
|
|
0.5211 |
0.5215 |
0.5236 |
2.21 |
5900k |
81k |
Flickr |
در این مقاله، از ماژولاریتی به‌عنوان معیار اندازه‌گیری کیفیت تقسیم‌بندی اجتماعات، استفاده و سعی شده است الگوریتم‌هایی به همراه ضمانت کارایی‌شان برای شبکههای مستقل از مقیاس ارائه شود. به این ترتیب که برای شبکههای مستقل از مقیاس بدون جهت با الگوریتم تقریبی با ضریب تقریب و برای شبکههای جهت‌دار با ارائه شده است. مزیت روش پیشنهادی این است که چون از رویکرد نمونه‌گیری برای شناسایی گرههای پرنفوذ به‌عنوان هستۀ اجتماع استفاده شده است و به دلیل اینکه در فرآیند نمونه‌گیری از اطلاعات اضافی مانند ویژگی‌های گرهها بهره برده میشود، پس رویکرد ما علاوه بر کارایی روی دیتاست‌های بزرگ، انعطاف‌پذیر نیز هست؛ به این معنا که قادر خواهد بود در تقسیم‌بندی شبکۀ اجتماعی از یکسری ویژگی‌های گره استفاده کند که این امر در کاربردهای مختلف و تحلیل‌های گوناگون کارایی دارد. برای کارهای آینده پیشنهاد میشود در کنار تقسیم‌بندی ساختار گراف بر تقسیم‌بندی براساس محتوای گرهها نیز تمرکز شود؛ زیرا الگوریتم‌های موجود که گراف را براساس محتوا تقسیم‌بندی می‌کنند، بیشتر با مشکل مقیاس‌ناپذیری روبه‌رو هستند و این مشکل با این راهکار تا حدی مرتفع میشود.
[1] تاریخ ارسال مقاله: 08/10/1398
تاریخ پذیرش مقاله: 05/02/1400
نام نویسندۀ مسئول: سیف‌اله سلیمانی
نشانی نویسندۀ مسئول: گروه مهندسی کامپیوتر- دانشکده مهندسی- دانشگاه اراک - اراک- ایران
)
