بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
تحلیلی بر روشهای تشخیص همبستگی های همپوشان در شبکه های اجتماعی
چکیده
گرافها نقش مهمی را در سیستمهای پیچیده ایفا میکنند از شبکههای کامپیوتری گرفته تا حوزههای بیولوژی و جامعـه شناسـی. در واقع هر رابطه M:N در اصطلاح پایگاه دادهای میتواند به عنوان گراف ارائه شود. بـا توجـه بـه محبوبیـت و گسـترش روز افـزون شبکههای اجتماعی آنلاین، تجزیه و تحلیل آنها مورد توجه بسیاری از پژوهشگران در حوزههای مختلف علمی قرار گرفته است اعـم از جامعه شناسی، بازاریابی و غیره. در این تحقیق ابتدا گراف کاوی در حوزههای مختلف نرم افزار، تصویر، سبد کـالا و... بررسـی و گراف کاوی در شبکههای اجتماعی انتخاب شده است. سپس روشهای مطرح شده در حوزههای مختلف گـراف کـاوی شـبکههـای اجتماعی شامل شناسایی میزان نفوذ پذیری، مدلها، متریکها و پویاییها، شناخت روابـط و تعـاملات گروهـی، انتشـار اطلاعـات، روشهای مختلف تشخیص همبستگیها در گراف کاوی در نظر گرفته شده است.
شبکههای اجتماعی شامل چندین همبستگی میباشند که هر همبستگی با مجموعهای از نودهایی تعریف میشود که ارتباطات در داخل همبستگی فشرده تر از همبستگیهای دیگر میباشد. روشهای متفاوتی در این زمینه ارائه شدهاند اما آنچه حائز اهمیت است نادیده گرفتن همپوشانی همبستگیهای میباشد. هدف از ارائـه ایـن مقالـه، تحلیـل روشهـای مطـرح شـده در حـوزه تشـخیص همبستگیهای همپوشان میباشد. یکی از مشکلات این الگوریتمها پیچیدگی زمانی آنهاست که در گرافهایی با مقیاس بزرگ نمود پیدا میکند. با توجه به اینکه برای گراف کاوی از ماتریس مجاورتی استفاده میشود بنابراین نمیتوان به زمان کمتر از O(n2) دسـت یافت. اگرچه با ظهور الگوریتمهای معنایی شاید بتوان تا حدودی این زمان را تقلیل داد.
کلمات کلیدی
شبکههای اجتماعی، گراف کاوی، همبستگی، همبستگیهای همپوشان.
-1 مقدمه
امروزه تجزیه و تحلیل شبکههای اجتماعی مورد توجه بسیاری از پژوهشگران در حوزههای مختلف قرار گرفته است کـه یکـی از عوامـل آن محبوبیـت روز افزون شبکههای اجتماعی در فضـای مجـازی مـیباشـد. در دسـترس بـودن دادههای شبکههای اجتماعی آنلاین و ساختار گراف گونه آنها روند تحقیقات در این زمینه را نیز تسهیل نموده است.
شبکههای اجتماعی را میتوان از جنبههای متفـاوت ماننـد روانشناسـی، جامعه شناسی، اهـداف تجـاری و تبلیغـاتی تجزیـه و تحلیـل نمـود. یکـی از روشهای تحلیل این شبکهها داده کاوی است. علم داده کاوی انسان را قـادر میسازد که حجم عظیمی از دادهها را مورد پردازش عمیق قرار دهـد و کلیـه نظمهایی که در عمق داده وجود دارند را تشـخیص نمـوده و جهـت اسـتفاده عرضه نماید.
گراف کاوی یکی از تکنیک های داده کاوی می باشد که امروزه به دلیل کاربرد در حوزههای مختلف اعم از زیست شناسی، شبکههای کامپیوتری، وب، اشکالزدایی نرم افزاری و غیره بسیار مـورد اسـتفاده قـرار گرفتـه اسـت. در ضمن بسیاری از انواع جدید دادهها ماننـد XML را نیـز مـیتـوان در قالـب گراف ارائه نمود.[1-9] گراف مجموعهای از گرههـایی مـیباشـد کـه توسـط یالها به یکدیگر متصل میشوند. در خیلی از زمینهها دادهها ساختاری گـراف گونه دارند اعم از شبکههـای کـامپیوتری کـه شـامل تعـدادی مسـیریاب یـا کامپیوتر میباشند که توسط رسانههای انتقال به یکدیگر متصل شده و تبـادل داده بین آنها وجود دارد در چنین ساختاری مسیریاب یا کامپیوترهـا نودهـای یک گراف و اتصال بین آنها یالهای گراف را تشکیل میدهند، شـبکههـای اجتماعی که شامل افرادی میباشند که به دلایل کاری، خویشاوندی یا مـوارد دیگر با یکدیگر ارتباط دارند یا شبکههای زیستی که پـروتئینهـا بایـد بـرای انجام برخی از کنشهای زیستی با یکدیگر همکاری نمایند. در این زمینهها و خیلی موارد دیگر گرافها ساختار اصلی دادهها را تشکیل میدهند.اگرچه در گراف کاوی شبکههای اجتماعی، مباحث اصـلی و پایـه ماننـد بهبود الگوریتمهای جستجو در گراف، کاهش هزینههای محاسباتی و مواردی از این قبیل مورد بررسی قرار گرفتهاند اما آنچه محققان علـوم مختلـف را بـه این حوزه ترغیب نموده است مفاهیم جامعه شناسی میباشد.
موضوعات اصلی مطرح شده در گراف کاوی شبکههای اجتماعی:[9]
· تشخیص همبستگیها: یکی از مهمترین ویژگیها در هر شبکه اجتماعی تشخیص وابستگیهاست. انسانهـا موجـوداتی اجتمـاعی هسـتند و بـر حسب علایق خود به گروههایی اجتماعی ملحـق مـیشـوند. از ایـن رو تشخیص همبستگیها در یک گروه در شناخت علایق یک جامعه بسیار موثر است.
· شناسایی میزان نفوذ پذیری: در این موضوع محققـان بـه دنبـال پاسـخ دادن به چنین سوالاتی هستند، چه فردی در یک شبکه اجتماعی موثرتر است یا نفوذ کدام یک از صفحات وب در اینترنت بیشتر است.
· مدلها، متریکها و پویاییها: این موضـوع از ایـن جنبـه مـورد علاقـه میباشد؛ استفاده از اطلاعات جغرافیایی، چگونگی شکلگیری شبکهها و چگونگی پردازش مجموعه حجیم دادهها بطور موثر.
· شناخت روابط و تعاملات گروهی: این موضوع که مبتنی بر تحلیل محل و موقعیت میباشد از سه دیدگاه مطرح میشود: شـناخت روابـط از ایـن جهت که کاربران چگونه تعامل دارند، چگونه تیمهای مناسـب را شـکل میدهند و کاربران یک شبکه اجتماعی چه کسانی هستند.
· انتشار اطلاعات: این موضوع قابل توجـه افـرادی اسـت کـه بـه دلایـل تجاری قصد ارسال تبلیغات درست به مردم را دارند. یکی دیگر از مـوارد بررسی شبکههای اجتماعی از این دیدگاه، دنبال کردن این اسـت کـه چه نوع اطلاعاتی از طریق یک شبکه مشخص و به چـه کسـی ارسـال میشود.
یکی از ساختارهای کلیدی در شبکههای اجتماعی آنلایـن و هـر شـبکه اجتماعی، همبستگی است. در سالهای اخیر مطالعه این ساختار مـورد توجـه محققان علوم مختلف قرار گرفته است. شبکههـای اجتمـاعی شـامل چنـدین همبستگی میباشند که هـر همبسـتگی بـا مجموعـهای از نودهـایی تعریـف میشود کـه تعـاملات بـین آنهـا در داخـل همبسـتگی فشـرده تـر از سـایر همبستگیها میباشد.
اکثر روشهای ارائه شـده بـرای تشـخیص همبسـتگی در شـبکههـای اجتماعی بر روی خوشههای مجـزا کـار مـیکننـد یعنـی هـر نـود بـه یـک همبستگی واحد نسبت داده میشود.[10-15] همانطور که میدانـیم افـراد در شبکههای اجتماعی مختلف فعالیت دارند از این رو همپوشـانی همبسـتگیهـا باید مورد توجه قرار گیرد. بطور مثال یک شخص ممکن است با چندین گروه اجتماعی در ارتباط باشد مانند گروه دوستان، اقوام، همکاران و در عین حال با گروههای دیگر مانند گروههای علمی هم در ارتباط باشد. این مسـئله هـم در شبکههای زیستی مطرح اسـت بطوریکـه یـک ژن ممکـن اسـت متعلـق بـه گـروههــای متفــاوتی باشــد.[16] در ایـن زمینــه روشهــای متفــاوتی مطــرح شدهاندکه کار آنها شناسایی خوشـههـایی اسـت کـه الزامـا جـدا از یکـدیگر نمیباشند زیرا نودهایی وجود دارند که متعلق به بیش از یک خوشـه هسـتند. هدف از ارائه این تحقیق بررسی روشهای موجود در زمینه همبستگی کـاوی و تشخیص همپوشانی این همبستگیها است. روند انجام تحقیق در شکل (1) نمایش داده شده است.
شکل(:(1روند انجام تحقیق
-2 گراف کاوی
گراف کاوی نوع خاصی از دادهکاوی است که برای حوزههایی کـه دادههـای آنها بصورت گراف ارائه میشوند، مناسب میباشد. یکی از کاربردهای گـراف کاوی در تجزیـه و تحلیـل شـبکههـای اجتمـاعی تشـخیص گـروههـایی بـا ویژگیهای مشابه میباشـد. کـه در ایـن تحقیـق چنـین گـروههـایی بـا نـام همبستگی مطرح شدهاند. منظور از همبستگی گروههایی شـامل چنـدین نـود میباشد بطوریکه اعضای یک گروه دارای ارتبـاط بیشـتری نسـبت بـه سـایر گروهها میباشند. در واقع چگالی یا تراکم پیوندها در داخل همبستگیها بیشتر از خارج همبستگیها میباشد.
تشخیص همبستگی که جزء روشهای خوشه بندی محسوب مـیشـود یکی از مباحث مهم در علوم کامپیوتر میباشد. در شکل (2) سه همبستگی بـا اشکال هندسی دایره، مربع و مثلث آورده شده است که نود 6 یک نود مشترک است و متعلق به همبستگی دایره شکل و مربع شکل میباشد.
شکل(:(2 نمونهای از همبستگیها[17]
در ارتباط با موضوع تشخیص همبستگی یا خوشههـا بـه مجموعـهای از خوشـــههـــای یافـــت شـــده یـــک پوشـــش گفتـــه مـــیشـــود شـــامل که در آن هر نود ممکن است متعلق به بیش از یک خوشه باشد. برای هر نود i یک فاکتور تعلق در ارتباط با همبستگی ارائـه می شود به طوری که Aic
معیاریست برای اریابی میزان تعلق نود i و خوشه c و باید شرایط فرمول((1 و (2) برقرار باشد:
و | c | بیانگر تعداد خوشههـا یـا همبسـتگیهاسـت. همپوشـانی بـین دو همبستگی مجموعهای از نودهایی است که بـین آنهـا بـه اشـتراک گذاشـته میشود(فرمول ( .((3
بطورکلی نتایجی که الگوریتمهای تشخیص همبستگیهـای همپوشـان ایجاد میکنند، میتواند در زمره یکی از دو نوع غیرفازی و فازی قرار گیرند. در نوع غیرفازی رابطه بین یک نود و یک خوشه باینری است. یعنـی نـود i یـا متعلق به خوشه c میباشد یا نمیباشد. در نوع فازی، هر نـود بـا یـک درجـه تعلق با یک همبستگی در ارتباط میباشد. البتـه بـا داشـتن یـک حـد آسـتانه میتوان نوع فازی را به راحتی به نوع غیر فازی تبـدیل نمـود. خروجـی اکثـر الگوریتمها از نوع غیر فازی میباشد. در بخش بعدی الگوریتمهای تشخیص همبستگیهای همپوشان بررسی شدهاند.
-3 الگوریتمها
ساختارهای همبستگی یا ماژولار به عنوان یکی از ویژگیهای مهم شبکههای اجتمــاعی در دنیــای واقعــی محســوب مــیشــوند. گذشــته از تعریــف مــبهم همبستگی، تکنیکهای بیشماری برای تشخیص کـارا و مـوثر همبسـتگیهـا ارائه شدهاند. کار عمده این روشها تشخیص همبسـتگیهـای جـدا از هـم و بدون همپوشانی است. اگرچه همانطور که در شبکههای اجتمـاعی در دنیـای واقعی مشهود است، افراد در گروههای متفاوتی عضو هستند. بطور مثال، یـک شخص معمولا با چندین گروه اجتماعی مانند خانواده، دوستان و همکـاران در ارتباط میباشد. یک محقق میتواند در حوزههای مختلـف اجتمـاعی فعالیـت داشته باشد. در ضمن در شبکههای اجتماعی آنلاین، تعداد گروههایی که یک فرد میتواند به آنها تعلق داشته باشد، نامحدود است.
بنابراین همپوشانی در شبکههای اجتمـاعی یکـی از ویژگـیهـای مهـم محسوب میشود. به همین دلیل، رشد قابل تـوجهی در ارائـه الگـوریتمهـای تشخیص همبستگیهای همپوشان اتفاق افتاده اسـت کـه کـار عمـده آنهـا شناسایی مجموعهای از خوشههایی است که لزوما جـدا از هـم نمـیباشـند و نودهایی وجود دارند که متعلق به بیش از یک خوشه میباشند. همانطور که در شـکل ( 3) مشـخص شـده اسـت روشهـای تشـخیص همبستگیهای همپوشان در شش گروه مطالعه و بررسی شدهاند:[18]
روشهای مبتنی بر گروههای کامل: در روشهـای مبتنـی گـروه کامل فرض بر این اسـت کـه یـک همبسـتگی شـامل مجموعـههـای همپوشانی از زیرگرافهای کاملا متصل است و تشخیص همبستگیهـا با جستجو برای گروههای مجاور انجام میشود. روش کار بـدین ترتیـب است که در ابتدا همه گروهها با اندازه k در یک شبکه شناسایی میشوند و سپس یک گراف جدید ساخته میشود. در گراف ایجاد شـده هـر نـود بیانگر یکی از گروهها با اندازه k میباشد. دو نود در صورتی با هم ارتباط دارند اگر گروهها k-1 عضو را به اشتراک بگذارند. مولفههای متصـل در گراف شناسایی میشـوند بطوریکـه گـروههـا همبسـتگیهـا را تشـکیل میدهند. از آنجایی که یک نود میتواند بطور همزمان در چندین
