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