مقاله تشخیص اجتماعات با رویکرد ترکیبی در شبکه های اجتماعی

بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

تشخیص اجتماعات با رویکرد ترکیبی در شبکه های اجتماعی

چکیده- تشخیص اجتماعات در شبکههای پیچیده یا شبکههای اجتماعی یکی از مهمترین مشکلات در زمینههای علمی میباشد. خوشهبندی یا تشخیص اجتماعات، ساختار گروهها در شبکههای اجتماعی و ارتباطات پنهان بین مولفههای آن را آشکار خواهد نمود. با درنظر گرفتن افزایش پایگاهدادههای مربوط به شبکههای اجتماعی، به الگوریتمهای مقیاسپذیری برای تجزیه تحلیل آنها نیاز داریم. در این مقاله ما درصدد پیدا نمودن اجتماعات صحیح و دقیق با استفاده از خوشهبندی ترکیبی هستیم. اکثر روشهای رایج تشخیص اجتماعات موجود قطعی نیستند و نتایج آنها به مقادیر اولیهای که در اکثر مواقع به صورت تصادفی انتخاب میشود بستگی دارد. خوشهبندی ترکیبی در تحلیل دادهها برای رسیدن به نتایج ثابت(پایدار) بدون توجه به مقادیر اولیه تصادفی میباشد. در این مقاله نشان خواهیم داد که خوشهبندی ترکیبی توانایی ترکیب با هر روش دیگری را خواهد داشت بهگونهای که دقت نتایج اجتماعات را افزایش میدهد. نتایج این بررسیها میتواند در مسائل بسیاری از جمله تشخیص دقیقتر اجتماعات، بازاریابی، تبلیغات، درک شبکه و بهبود موتورهای جستجو مورد استفاده قرار گیرد.

کلید واژه- خوشهبندی، خوشهبندی ترکیبی، تشخیص اجتماعات، شبکههای اجتماعی.

-1 مقدمه

امروزه اینترنت و خدمات وب به سرعت در حال گسترش هستند و همزمان شبکههای اجتماعی مجـازی نقـش مهمـی در زنـدگی واقعی افراد دارد. در واقع شبکههای اجتماعی، شبکههای تعـاملی هستند که از اینترنت به عنوان رسانهای برای ایجاد ارتبـاط بـین افراد استفاده میکننـد. بـا افـزایش سـریع کـاربران شـبکههـای اجتماعی، کاوش در مقیاس بالای دادهها میتواند کـارایی بهتـر و موثرتری از پتانسیل پنهان این شبکهها فراهم کند.[1]

تشخیص اجتماعات1 یا خوشهبنـدی2 یکـی از مراحـل اصـلی در دادهکاوی است که وظیفـه کـاوش الگوهـای پنهـان در دادههـای بدون برچسب را بر عهـده دارد. بـا توجـه بـه پیچیـدگی مسـئله خوشهبندی و ضعف روشهای پایهای آن، امروزه اکثـر مطالعـات در خصوص خوشهبندی به سمت روشهای خوشهبندی ترکیبی3 هدایت شده است. همانگونه کـه در بـالا اشـاره شـد، تشـخیص اجتماعات و خوشهبندی شباهتهای بسیار زیادی با هـم دارنـد و منابع زیادی این دو را یکسان میدانند.[4][3][2][1]

رویکرد خوشهبندی ترکیبی بدینصورت میباشد که بـا اسـتفاده از روشهای پایهای و یا هر روش ممکن موجود، با ترکیـب تـک-تک این روشها با یکدیگر درصدد پیدا نمودن یک جـواب پایـدار از نتایج متفاوت میباشد. بهطوری که جواب نهـایی دارای دقـت، پایداری، صحت و از اجماع نتایج روشهای مختلف بدسـت مـی-آید، که دارای اطمینان بالاتری میباشد. با توجه به قابلیت ادغـام خوشهبندی ترکیبی و تشـخیص اجتماعـات در ایـن مقالـه بـرای بهبــود نتــایج نهــایی در تشــخیص اجتماعــات از »خوشــهبنــدی ترکیبی« استفاده شده است. دقت و صحت اجتماعـات نهـایی در تشخیص اجتماعات مسئله مهمی میباشد، چـرا کـه الگـوریتمای در تشخیص اجتماعات وجود ندارد که در تمام حالات و دادههای گوناگون جواب دقیق و حتی نزدیک به آن را داشته باشد.

در این مقاله سعی داریم که با استفاده از خوشهبندی ترکیبی در شبکههـای اجتمـاعی بـه بررسـی اجتماعـات در ایـن شـبکههـا بپردازیم. بدینصورت که با اعمـال روشهـای مختلـف تشـخیص اجتماعات و بدست آوردن نتایج متفاوت و در نهایت ترکیـب ایـن

1

روشها و بدسـت آوردن یکسـری اجتماعـات کـه در مقایسـه بـا الگوریتمهای پایه در تشخیص اجتماعات دارای دقت بالاتر، نتایج مطمئنتر و پایداری بیشتری هستند. نتایج این بررسیها میتواند در مسائل بسیاری از جمله تشخیص دقیقتر اجتماعات، بازاریابی، تبلیغات، درک شبکه و بهبود موتورهای جسـتجو مـورد اسـتفاده قرار گیرد. قسمتهای موجود در این مقاله بدین شرح مـیباشـد که بعد از شرح تعاریف و مفاهیم و نیز بررسی کارهای انجام شده موجود، یک روش پیشنهادی در خصوص پیدا نمودن اجتماعـات مطرح و در نهایـت ایـن روش را مـورد ارزیـابی قـرار مـیدهـیم. استفاده از این روش دارای مزایای و معایبی نیز مـیباشـد کـه در قسمت نتیجهگیری به ان اشاره شده است.

-2 تعاریف و مفاهیم

در این قسمت به بررسی تعاریف و مفـاهیمی کـه در ایـن مقالـه مورد استفاده قرار گرفته است میپردازیم.

-1-2 شبکههای اجتماعی

شبکههـای اجتمـاعی سـاختاری اجتمـاعی اسـت و از افـراد یـا سازمانهایی تشکیل شده است که گرههای شبکه را تشکیل مـی دهند. گرهها توسط یک یا چند نـوع خـاص از وابسـتگی بـه هـم متصل هستند، برای مثال تبادلات مالی، دوستیها، خویشـاوندی، تجــارت، لینــکهــای وب، ســرایت بیمــاریها(اپیــدمولوژی) یــا مسیرهای هواپیمایی نمونههایی از ارتباط هستند. اما ساختارهای حاصل از این شبکهها اغلب بسـیار گسـترده و پیچیـده هسـتند. تحلیل شبکه اجتماعی4 عبـارت اسـت از نگاشـت و انـدازهگیـری روابط و همکـاریهـا در بـین افـراد، گـروههـا، سـازمانهـا و هـر موجودیتی که قابلیت پردازش اطلاعات و دانش را داشـته باشـد. برای نمایش و تحلیـل شـبکههـای اجتمـاعی معمـولا از تئـوری گراف5 استفاده میشود. مولفههای موجود در تئوری گراف گره6 و لبه7 است.[1]

یــک شــبکه N را مــیتــوان بــه صــورت یــک گــراف بــه شــکل G = V , E تعریــف نمــود، کــه در آن گــراف G شــامل V مجموعه گرههای گراف و E مجموعه لبهها اسـت. بعـد از بدسـت آوردن گــراف فــوق مــیتــوان از روی گــراف، مــاتریس مجــاورتی متناظر بـا آن را بدسـت آورد. مـاتریس A را مـاتریس مجـاورتی

گراف G گویند، این ماتریس یک ماتریس مربعی بـه ابعـاد تعـداد گرههای گراف متناظر با آن بوده و در صورت وجود ارتبـاط بـین دو گره به آن ماتریس عدد یک و درغیر ایـن صـورت عـدد صـفر منظور میگردد.

-1-1 تشخیص اجتماعات

در شبکههای اجتماعی برخی گرهها در مقایسه با کل گـرههـای شبکه، ارتباط بیشتری با هم دارند که به آنها اجتماع گفته می-شود.[3] هدف از تشخیص اجتماعـات، جـدا کـردن گـروههـا یـا اجتماعاتی است که ارتبـاط بیشـتری بـا هـم دارنـد.[2] در واقـع تشخیص اجتماعات، تقسیمبندیهای موجود در شـبکه را نشـان میدهد و اجتماعات یک گراف را از هم مجزا میکنـد. تشـخیص اجتماعات به ما کمک میکند تا دید بهتـری نسـبت بـه سـاختار شبکه پیدا کنیم.[4]

در [4] تشخیص اجتماعات را بدینصورت تعریف مینماید:
اگر A را ماتریس مجاورتی یک گراف درنظر بگیریم، درجه یـک گــره در گــراف را بــا ki نشــان مــیدهنــد کــه برابــر اســت بــا:

میباشد. با در نظر گرفتن یـک زیـر گـراف S بـه-طوری که S ⊆G باشد.

در رابطه (1) نیز درجـه هـر گـره را بـرای اجتماعـات داخلـی و خــارجی بــهصــورت تعریف میکنیم.

حال به تعریف مسئله اصلی که همان تشخیص اجتماعات مـی-باشد میپردازیم.

با توجه به رابطه مجموع درجـههـای تمـامی گرههایی که در اجتمـاع یـا زیرگـراف S وجـود دارد مـیباشـد و مجموع درجههای تمامی گرههایی که در اجتمـاع یا زیرگراف S وجود نـدارد مـیباشـد. بنـابراین مسـئله اصـلی در

زمینه تشخیص اجتماعات این است که بدانیم چگونه به بهتـرین حالت شبکه را به گروههای اصلی آن تقسیم کنـیم. در شـبکههـا واقعی هیچ اطلاعاتی دربـاره تعـداد اجتماعـات وجـود نـدارد. در بعضی روشهای تشخیص اجتماعات فرض بر آن است که تعـداد اجتماعات شبکه را از قبل میدانیم. در حـالی کـه در بسـیاری از شبکهها، هیچ دانش اولیـهای در مـورد اجتماعـات شـبکه وجـود ندارد و روشهای جدید بدنبال برطرف کردن این نقیصه هستند. روشهای تشخیص اجتماعات معمولا با استفاده از گـراف ایجـاد شده از ارتباطـات بـین افـراد در شـبکههـای اجتمـاعی مـاتریس همبستگی8 متناظر بـا آن را محاسـبه مـیکننـد و بعـد از آن بـا اعمال الگوریتمهای تشخیص اجتماعات بر روی این ماتریس می-توان نتایج گوناگون بر روی دادههای متفاوت را بدسـت آورد. هـر یک از روشها با توجه به روش انتخابی و نیـز نـوع و حجـم داده ورودی، اجتماعــات متفــاوتی را پیــدا مــینماینــد، کــه در بعضــی شرایط یـک الگـوریتم جـواب خـوب و در شـرایط دیگـر جـواب نامناسبی ایجاد مینماید، بنابراین هر روشی برای مجموعـه داده-های خاص مناسب و مورد استفاده قرار میگیرد.

-2-1 خوشهبندی ترکیبی

خوشهبندی یکی از مراحل اصلی در دادهکاوی است که در جهت کاوش الگوهای پنهان در دادههای بدون برچسب مـورد اسـتفاده قرار میگیرد. روشهای خوشهبندی عادی بدینصورت عمل می-نمایند که با تعریف یک الگوریتم سعی در برطرف نمودن مشـکل خوشهبندی دارند. درصورتی که اعمال هر یـک از ایـن الگـوریتم برروی دادههای یکسان دارای نتایج گوناگونی خواهد. با توجه بـه پیچیدگی مسئله تشخیص اجتماعات و ضعف روشهـای پایـهای آن، امروزه اکثر مطالعات به سمت روشهای خوشهبندی ترکیبی هدایت شده است.

بعد از اعمال الگوریتمهای مختلف بر روی شـبکه مـورد تحلیـل همانطوری که در »شکل «1 نیز نشان داده میشود، یک سـری نتـــایج متفـــاوت بدســـت خواهـــد آمـــد کـــه بـــهصـــورت Π* ={π1, π2 ,..., πm} تعریف میگردد. بـا ترکیـب صـحیح روشهای مختلف با استفاده از خوشهبندی ترکیبی مـیتـوان بـه یک نتیجه بسیار بهتر، مطمئنتر، پایدارتر و دقیق رسید.

در این مقاله برای برطـرف کـردن ایـن نقیصـه از خوشـهبنـدی

ترکیبی استفاده شده است، تا جوابها از مجموع جوابها حاصل گردد. دقت جوابهـا در ایـن روش بسـیار بهتـر و مطمـئنتـر و پایدارتر خواهد بود. چرا که در ایـن روش تنهـا از یـک الگـوریتم برای بدسـت آوردن نتیجـه بـر روی دادههـای مختلـف اسـتفاده ننمودهایم و از اجماع تمامی روشها با قطعیت بیشتری در مـورد نتیجه صحبت مینماییم.

خوشهبندی ترکیبی درصدد ترکیب نتایج بهمنظور پیـدا نمـودن نتایج مستحکمتر و دقیقتر از نتایج بدسـت آمـده قبلـی دارد. بـا ترکیب نتایج میتوان یک خوشهبندی یـا اجتماعـات دقیـقتـری داشته باشیم.[5]

-3 روشهای موجود تشخیص اجتماعات

روشهای مختلفی برای بدست آوردن اجتماعات در شبکه وجود دارد. بررسی تـکتـک گـرههـا و قـرار دادن آنهـا در اجتماعـات مختلف و در نهایت ارزیابی آن دارای هزینـه زمـانی و محاسـباتی بالایی است و این رویکرد بهطور عملی امکانپـذیر نیسـت. بـرای غلبه بر این مشکل روشهای مبتنی بر تجربه 9 به کمک آمدهانـد. که از جمله این روشها میتوان به روشهای طیفـی10، تقسـیم-کننــده11، تجمعــی12، روشهــای مبتنــی بــر بهینــهســازی ماژولاریتی13، تکنیکهـای حریصـانه 14، گـداختگی شـبیهسـازی شده 15، الگوریتمهای تکاملی16 اشاره نمود. هر کدام از این روش-هــا بــه نــوعی در بهبــود عملکــرد تشــخیص اجتماعــات مــوثر است.[3][4]

ماژولاریتی از پرکاربردترین معیارهای مورد استفاده در روشهای مختلف است. این معیار کمیتی از گروهبنـدی کـه از کـل گـراف بدست آمده است، ارائه میکند و نقش بسزایی در تعیـین صـحت گــروهبنــدی دارد. معمــولا بــرای ارزیــابی هــر روش تشــخیص اجتماعات در شبکه، مقدار ماژولاریتی گروهبنـدی پیشـنهادی آن روش را برای شبکهها و گرافهـای مختلـف محاسـبه مـیکننـد. هرچه ماژولاریتی بهدست آمده بیشتر باشد، دقت روش موردنظـر بهتر بوده است. معیـار مـاژولاریتی مهمتـرین محـک در ارزیـابی روشهای تشـخیص اجتماعـات در شـبکههـای اجتمـاعی اسـت. ماژولاریتی بهصورت فرمول (1) زیر تعریف میشود:[6][7]

در رابطه فوق i و j اندیسهای اجتماع است و eii نسبت تعـداد لبههایی که گرههای داخل اجتماع i را بههم متصل مـیکنـد بـه کل لبههای گراف است. به عبارت دیگر کسری از تعداد لبهها که دو سر آن در اجتماع i قـرار دارد بـه کـل لبـههـای گـراف و ai نسبت تعداد لبههایی که حداقل یک گره آن در اجتماع i باشد به کل لبههای گراف است. در واقع رابطه فوق سهم هر اجتمـاع i را در کل شبکه بیان میکند. هرچه ایـن عـدد بزرگتـر باشـد، ایـن اجتماع سهم بیشتری در شبکه دارد و در واقـع اجتمـاع قـویتـر است. بدین معنی که ارتباطـات داخـل اجتمـاع در آن بیشـتر از ارتباط آن با سایر اجتماعات شبکه است. اگـر کـل گـراف شـامل تنهــا یــک اجتمــاع باشــد یــا گــرههــا بصــورت تصــادفی در بــین اجتماعات قرار گرفته باشند Q=0 خواهد بود. هرچه مقدار Q بـه یک نزدیکتر باشد اجتماعات بهتر جدا شدهاند ولی هیچگاه یـک نمیشود. در عمل Q>0,3 ساختار گروهی مناسبی را نشان مـی-دهد. ماژولاریتی میتواند مقادیر منفی را نیـز بپـذیرد.[8] مقـدار ماژولاریتی ممکن است برای یک شبکه در بهترین حالت زهبندی از عدد خاص بیشتر نشود. این بدان معنا نیست تشخیص اجتماع به درستی انجام نشده است، بلکه ممکن است بیشترین مقـداری باشد که ماژولاریتی برای آن شبکه میتواند داشته باشد.

یکی از روشهای تشخیص اجتماعات روش تقسـیمکننـده مـی-باشد. در شبکهها، هر چه تعـداد مسـیرهایی کـه از گـره یـا لبـه خاصی عبور می کنند بیشتر باشد آن گره یا لبـه مهـمتـر اسـت. بنابراین با فرض اینکه کوتاهترین مسیر بین دو گره محاسبهپـذیر باشد، اهمیت یک گره یا لبه را میتوان اندازهگیری نمود، کـه بـه آن مرکزیت مابینی گفتـه مـیشـود. یکـی از روشهـای بدسـت آوردن اجتماعات که [9] ارائه شده است مرکزیـت مـابینی مـی-باشد. رابطه مرکزیت مابینی به صورت رابطه (4) تعریف میشود:

کــه در آن σ(i,u, j) تعــداد کوتــاه تــرین مســیر هــا بــین دو اجتماع i و j است که از گره یا لبـه u عبـور مـی کنـد. σ(i, j) تعداد کل مسیر ها بین دو گره i و j است. در ایـن روش بـا پیـدا

نمودن لبهای که بیشترین مرکزیت یا ارتباط بـا دیگـر گـرههـا را دارد و حذف بازگشتی آن لبـه در نهایـت اجتماعـات جـدا شـده بدست میآید. روشهای دیگری نیز مانند ضریب خوشهبندی لبه نیز وجود دارد که از این ایده اسـتفاده نمـودهانـد ولـی در رابطـه مربوطه لبههایی که اجتماعات را بـه یکـدیگر مـرتبط مـیکننـد ضریب کوچکی دارند که در هر مرحله حذف میشوند.[10]

روشهای دیگر که از جمله روشهای طیفی است با ایجـاد یـک برش نرمال بر روی گراف به تقسیم نمودن گراف میپردازد. ایـن معیار بر این اساس است که یک گروهبندی خوب تعداد لبـههـای بین اجتماعات را کمینه میکند، در عـین حـال لبـههـای داخـل اجتماع را نگه میدارد.[11] این معیار به صورت زیر تعریـف مـی شود:
گراف G(V,E) را در نظر بگیرید که در آن V مجموعه گرههـای گراف و E مجموعه تمام لبههای گراف است. گرههای گراف را بـه دو مجموعه مجزای B,A تقسـیم مـیکنـیم بـه طوریکـه داشـته باشیم، B=V–A باشد. مقدار این رابطه کسـری از اتصـالات بـین B,A با توجه به اتصالات جداگانه B,A میباشد.

مقدار cut بین B,A به صورت رابطه (5) است:

و مقدار association بدین صورت است:

وزن بین گره v و i است. رابطه (6) برای نرمـال کـردن اندازه خوشهها(اجتماعات) بکار میرود. این روش را معمولا بـرای گرافهای وزندار استفاده مـیکننـد کـه البتـه قابـل تعمـیم بـه گرافهای بدونوزن نیز هست ( بـا در نظـر گـرفتن وزن یـک در صورت وجود لبه و صفر در صورت عدم وجود لبه).

حال از دو رابطه اخیر برای تعریف برش نرمال شده استفاده می-کنیم.

همانطور که در رابطه ( (7 میبینیم این رابطه فقط شـامل دو اجتماع میباشد، که نیاز به تعمیم برای پیـدا نمـودن اجتماعـات دیگــر دارد. بــدین صــورت کــه همــین روال را بــر روی اجتمــاع کوچکتر ایجاد شده اجرا نماییم تا زمـانی کـه بـه بهتـرین مقـدار

4

ماژولاریتی دست پیدا نماییم.
یکی از مهمترین روشها، روش تجمعی میباشـد. ایـن روش بـر این حقیقت بنـا شـده کـه گـرههـای یـک اجتمـاع ویژگـیهـای مشترکی دارند و میتوان از این ویژگیهای مشترک برای گـروه-بنــدی اســتفاده کــرد. در برابــر روشهــای تقســیمکننــده، روش تجمعی در ابتدا همه گرهها را جدا از هـم و غیـر متصـل در نظـر میگیرد و آنها را بر اساس ویژگیهای مشـترک بـه هـم متصـل میکند تا به اجتماعات برسد. در واقع نحوه عملکرد ایـن رویکـرد بدین صورت است که لبههای بین اجتماعات خود به خود حـذف شده و تنها لبههای داخل اجتماع باقی میمانند.[12]

از جمله روشهای دیگر روش بیشینهسازی ماژولاریتی میباشد، جستجو برای یافتن ماژولاریتی بهینه(یا بیشـینه) از نـوع مسـائل بسیار سخت میباشد. چرا که فضـای تقسـیمبنـدیهـایی کـه از گراف امکانپذیر است با بزرگ شدن اندازه گـراف بـه سـرعت در حــال افــزایش اســت. بــه همــین دلیــل رویکردهــای جســتجوی مکاشفهای بـرای محـدود کـردن فضـای جسـتجو الزامـی اسـت. در[13][14] نیومن روشی بر پایه ادغـام کـردن اجتماعـات ارائـه کرده است بطوری که ماژولاریتی بیشینه شود.

از جمله روشهـای دیگـر در ایـن زمینـه روشهـای مبتنـی بـر الگــوریتمهــای تکــاملی هســتند. روشهــای مختلفــی در حــوزه الگوریتمهای تکاملی بـر روی تشـخیص اجتماعـات انجـام شـده اســت. تــارگین و بینگــل[15] 17 روشــی ارائــه کردنــد کــه از ماژولاریتی بـرای سـنجش اسـتفاده مـیکنـد. در ایـن روش هـر کروموزوم کل گرههای موجود در شبکه را شامل میشود. در ابتدا به هر گره به صورت تصادفی یک اجتماع نسبت داده مـیشـود و سپس crossover که تغییراتی روی آن صورت گرفته، انجام مـی شود. گاهی نیز mutation گرههای دو اجتماع را جابجـا مـیکنـد اعمال میشود و در نهایت هر کروموزوم توسط معیار مـاژولاریتی سنجیده میشود.

روشهای دیگری نیز در خصوص تشخیص اجتماعات وجود دارد که ما در اینجا به این چند روش اشاره کردیم کـه در ایـن مقالـه نیز تا حدودی اسـتفاده شـده اسـت. در [16] بـه الگـوریتمهـای دیگری برای تشخیص اجتماعات اشاره شده است.

-4 روش پیشنهادی

با توجه به اینکه اکثر روشهای تشـخیص اجتماعـات پایـه روی جنبههای خاصـی از دادههـا تمرکـز مـی کننـد، در نتیجـه روی مجموعه دادههای خاصی کارآمـد مـیباشـند. بـه همـین دلیـل، نیازمند روشهایی هستیم که بتوانـد بـا اسـتفاده از ترکیـب ایـن الگوریتمها و گرفتن نقاط قوت هر یک، نتایج بهینهتری را تولیـد نماید . در واقع هدف اصلی تشخیص ترکیبی اجتماعات جستجوی نتایج بهتر، مطمئنتر و مستحکمتر، با اسـتفاده از ترکیـب نتـایج حاصل از چندین الگوریتم پایه میباشد.[5]

بنابراین تشخیص ترکیبی اجتماعات با ترکیب نتایج بدست آمده از الگوریتمهای پایه درصدد پیدا نمودن نتایج دقیقتر، مطمئنتـر و پایدارتر از نتایج بدست آمده قبلی میباشد. همانطوری کـه در »شکل(«(1 مشاهده میشود، انباره داده نشان داده شـده در ایـن شکل در اصل همان گراف ما خواهد بود، که از ارتباطات موجـود در شبکه اجتماعی مورد بررسی ایجاد شده اسـت. مجموعـه ایـن ارتباطات در نهایت یک گـراف و از آن یـک مـاتریس همبسـتگی ایجاد میگردد که در صورت وجود ارتباط بین گـرههـا یـک و در غیر اینصورت صفر منظـور مـیگـردد. بـا اعمـال الگـوریتمهـای متفاوت بر روی این ماتریس همبستگی و گرفتن نتایج متفـاوت و در بعضی موارد یکسان میتوان از روش ترکیبی ترکیبی اسـتفاده نمود. بدینصورت که اگر گرهای در چند نتیجه مختلف جزء یـک اجتماع باشد احتمـال قرارگیـری آن گـره در آن اجتمـاع بیشـتر خواهــد بــود، در نهایــت بــا ترکیــب نتــایج اولیــه یــک مــاتریس همبستگی دیگری ایجاد خواهـد شـد کـه یـک گـراف وزندار از نتایج ما میباشد، از مجموع نتایج کمـک مـیگیـریم تـا بـه یـک نتیجه بهتر، دقیقتر، پایدارتری برسیم.

ماتریس همبستگی ایجاد شده برآیندی از تمامی روشهای اولیه خواهد بود، در این ماتریس بـرای هـر یـال در گـراف مـورد نظـر عددی منظور میشود که این عـدد مقـدار وابسـتگی آن یـال بـه گرهای که با آن در تماس میباشد را نشان مـیدهـد. بـه عبـارت دیگر اجماع روشهای مختلف در مورد اینکه آیا این دو نود با هم در ارتباط هستند یا خیر را نشان خواهد داد. یالهای که ارتبـاط ضعیف دارند، در الگوریتم تشخیص ترکیبی اجتماعات سیاست

5

شکل(:(1 الگوریتم پیشنهادی برای تشخیص ترکیبی اجتماعات

حذف آنها اتخاذ میگردد که به دقیق در نهایت با اعمال یکـی از الگـوریتمهـای سلسـله مراتبـی بـرای

اســتخراج نتــایج نهــایی بــر روی آن مــاتریس وزندار، تشــخیص اجتماعات کاملتر و دقیقتری را خواهیم داشت.

از نظر هزینه اجرایی، هزینه اجرایی آن نیز برابر با بدترین حالت اجرای یک الگوریتم از بین تمام الگوریتمهای تشخیص اجتماعات خواهد بود، چرا که تعـداد الگـوریتمهـای مـورد بررسـی در ایـن فرایند ترکیبی در نهایت محدود خواهند بود.

-1-4 ارزیابی روش پیشنهادی

در این مقاله چهار روش مختلف تشخیص اجتماعات با اسـتفاده از زبان Matlab پیادهسازی شده است، که درصدد آن هستیم که با ترکیب این چهار روش با استفاه از خوشهبندی ترکیبی به یـک خوشهبندی یا اجتماعات دقیـقتـری نسـبت بـه تـکتـک نتـایج برسیم. از مزایای این روش میتوان به مقیـاسپـذیری بـالای آن اشاره نمود بدین معنـا کـه هـر چـه تعـداد روشهـای مـا بـرای تشخیص اجتماعات بیشتر باشد نتایج بهتری را در خوشـهبنـدی ترکیبی به ارمغان میآورد و نیز هر روش را بدون محدودیت و بـا تغییر شرط اتمام آن میتوان استفاده نمود، چرا که ما در خوشه-بندی ترکیبی به نوع روش نگاه نمـیکنـیم بلکـه نتیجـه روش را مورد بررسی قرار میدهیم و با بررسی نتایج بدست آمده از تـک-تک روشها یک خوشهبندی دقیقتری را ارائه میدهیم.

در اینجا به بررسی این چهار الگـوریتم پیـادهسـازی شـده بـرای تشخیص اجتماعات مـیپـردازیم کـه تـکتـک بـه چـه صـورتی اجتماعات را بدست میآورند. کلیه این روشها از روی ماتریس