بخشی از مقاله
چکیده
در سالهای گذشته، شبکههای تعاملی با توجه به یالهای ارتباطی که میان گرههای آن وجود دارد مورد توجه زیادی قرار گرفته است. تشخیص جامعه یکی از چالشهای اصلی برای تجزیه و تحلیل اینگونه شبکهها است. جامعه زیرگرافی از یک گراف است که تعداد ارتباطهای بین اعضاء آن زیرگراف، نسبت به تعداد ارتباطهایی که آن را به بقیه گراف متصل میکند، بیشتر است. هدف اکثر الگوریتمهای تشخیص جامعه، تقسیمبندی گراف به چند زیرگراف همبند است که هر گره باید به یک جامعه متعلق بوده و به دیگر جوامع تعلق نداشته باشد.
جامعهبندی گرهها بر اساس شباهتهای موجود در بین آنها انجام میشود. کلید اصلی جامعهبندی صحیح، استفاده از معیار شباهت مناسب برای تفکیک گرهها است. در این مقاله از یک معیار شباهت ترکیبی برای جامعهبندی گرهها استفاده شده است. این معیار بر اساس ترکیب وزندار معیار شباهتهای ساختاری، کسینوسی و همینگ ایجاد شده است. نتایج مقایسات نشاندهنده عملکرد بهتر روش پیشنهادی در مقایسه با موارد مشابه است.
.1 مقدمه
بسیاری از مجموعه دادههایی که از حوزههای مختلف جهان واقعی نشات میگیرند، میتوانند به صورت شبکههای ارتباطی - تعاملی - ظاهر شوند. یک شبکه ارتباطی ساختاری است که موجودیتهای درون آن با یکدیگر ارتباط داشته، از جمله اعضای یک حزب سیاسی که دارای ارتباطات درون حزبی میباشند .[1]با رشد شبکههای اجتماعی، کاربران زیادی به اینگونه شبکهها جذب شدهاند. این شبکهها محل تبادل اطلاعات بسیار زیادی بین افراد هستند. با توجه به این نکته که رفتار و تعاملات افراد تنها بر اساس ویژگیهای شخصی آنان نیست - بلکه تعاملات آنها با دیگران بر رفتارشان تاثیرگذار است - ، تجزیه و تحلیل شبکههای ارتباطی بسیار مورد توجه قرار گرفته است. شبکههایی مانند فیسبوک، توییتر و لینکداین از جمله شبکههای ارتباطی بزرگ هستند .[2]
یکی از مسائل بسیار مهم در تجزیه و تحلیل شبکههای ارتباطی، شناسایی ساختارهای موجود در آن است. واضحترین ساختار درون شبکه ارتباطی، ساختار جامعه است، در نتیجه مسئله تشخیص جامعه، یکی از معمولترین تحقیقات در شبکهها است. تشخیص و شناسایی جوامع موجود، به درک ساختار کلی شبکه و تقسیمبندی فعالیتهایی که در آن صورت میپذیرند، میانجامد .[3] سادهترین روش مطالعه شبکههای ارتباطی، نگاشت آنها بر تئوری گراف در ریاضیات است. از دیدگاه ریاضی، یک گراف G که با نماد G - V, E - نشان داده میشود، از دو مجموعه مجزا به نامهای، مجموعه گرهها - V - و مجموعه یالها E ⊂ - - V × V تشکیل شده است. هر یال از مجموعه E، دو گره از گراف را به یکدیگر وصل میکند .[4]
در این نگاشت، موجودیتهای شبکه - بهطور مثال افراد - بهصورت گرههای گراف و روابط بین موجودیتها بهصورت یالهای گراف تعریف میشوند. روابط میتواند یکطرفه یا دوطرفه باشد. روابط یکطرفه به یالهای جهتدار و روابط دوطرفه به یالهای بدونجهت در گراف نگاشت میشوند. با توجه به نگاشت شبکه به یک گراف، مسئله تشخیص جامعه در واقع خوشهبندی ارتباطات یک گراف است .[5] از نگاه بیرون به مسئله، جامعهبندی مانند خوشهبندی است.
اما در نگاه دقیقتر جامعهبندی یک نوع خوشهبندی خاص است - خوشهبندی گراف بر اساس یال - ، و با خوشهبندی محض متفاوت است. در مفهوم خوشهبندی، نمونههای داده بر اساس شباهت بین ویژگیهای خود داده، خوشهبندی میشوند - خوشهبندی گراف بر اساس ویژگیهای گره - . اما جامعهبندی بر اساس ارتباطات گرهها - یالها - انجام میشود و معیار شباهت، وابسته به همین ارتباطات است .[6] تاکنون هیچ تعریفی برای مفهوم جامعه به صورت عمومی مورد پذیرش قرار نگرفته است .
اما به طور کلی جامعه زیرگرافی از یک گراف است که تعداد یالهای بین اعضاء در زیر گراف، نسبت به تعداد یالهایی که زیرگراف را به بقیه گراف متصل میکند، بیشتر است - با فرض همبند بودن زیرگراف - .[7] از دیدگاه ریاضی، گراف H - V1, E1 - را زیرگراف G - V, E - است اگر و فقط اگر V1 ⊂ V و E1 ⊂ E آنگاه H ⊂ G است .[8] در شکل 1 یک زیرگراف بهصورت خطچین از بقیه گراف متمایز شده است و میتواند یک جامعه باشد.
هدف جامعهبندی، گردآوری گرهها در گروههای مشخص و مجزّا به نام جامعه است. زیرگرافهای تشخیص دادهشده بیانگر جامعههای موجود در گراف هستند . دستهبندی نمونه دادهها در جوامع موجود، بر اساس شباهتهای موجود در بین آنها انجام میشود. با توجه به این رویکرد دستهبندی، هر جامعه شامل مجموعهای از گرهها است که وجه اشتراک بیشتری با یکدیگر، نسبت به بقیه گرهها دارند. کاربردهای جامعهبندی در فعالیتهای مانند سیستمهای پیشنهاددهنده، بهینهسازی موتورهای جستجو و پیشبینی رفتار گروهی جوامع میباشد.
یکی از مسائل مهم در تشخیص زیرگرافها، تعیین میزان شباهت بین گرهها است. اگر شباهت بین گرههای یک گراف بهدرستی اندازهگیری شود موجب بهبود دقت و کیفیت جامعهبندی خواهد شد. معیارهای شباهت متفاوتی برای این کار ارائه شدهاند. اساس معیار شباهت در جامعهبندی، ارتباطات هر گره با گرههای دیگر است .[9] در این مقاله روشی برای جامعهبندی گرافهای بدون جهت، بر اساس الگوریتم IsoFdp ارائه شده است.
در این روش با تغییر معیار شباهت، از یک معیار ترکیبی برای جامعهبندی گرهها استفاده شده است. این معیار بر اساس ترکیب وزندار معیار شباهتهای ساختاری، کسینوسی و همینگ ایجاد شده است. ساختار ادامه مقاله به این شرح است: بخش دوم مروری بر کارهای گذشته این حوزه است. روش پیشنهادی در بخش سوم توضیح داده میشود. بخش چهارم ارزیابی روش پیشنهادی است و نتیجهگیری در بخش پنجم ذکر شده است.
.2 مروری بر ادبیات پیشین
یک دستهبندی کلی روشهای تشخیص جامعه بر اساس نوع گراف - جهتدار و بدونجهت - است. در این مقاله، اساس کار بر پایه گرافهای بدون جهت است. الگوریتم گیروان و نیومن که در [10] معرفی شده است، یکی از روشهای خوشهبندی مورد استفاده برای شناسایی جوامع است. بینابینی گره، به عنوان یک معیار مرکزیت و قابلیت نفوذ گرهها مورد مطالعه قرار گرفته است. این معیار تاثیر گره بر جریان اطلاعات بین گرهها، به خصوص در مواردی که جریان اطلاعات عمدتا در کوتاهترین مسیر در دسترس است را بیان میکند. الگوریتم گیروان و نیومن این تعریف را به یال گسترش داد.
بینابینی یک یال به عنوان تعداد دفعاتی که آن یال در کوتاهترین مسیر بین هر جفت از گرهها حادث میشود، تعریف میشود. اگر بیش از یک کوتاهترین مسیر بین یک جفت از گرهها وجود داشته باشد، به هر یک از مسیرها یک وزن مساوی اختصاص داده میشود، به طوری که وزن کل تمام مسیرها برابر واحد است. در این الگوریتم بیان شده که یالهای انسانی جوامع، بینابینی یال، بالایی - حداقل یکی از آنها - دارند. با از بین بردن این یالها، گروهها از یکدیگر جداشده و بنابراین ساختار جامعه در شبکه شکل میگیرد.
نتیجه نهایی الگوریتم گیروان و نیومن یک دندوگرام1 است. همانطور که الگوریتم گیروان و نیومن اجرا میشود، دندوگرام از بالا به پایین تولید میشود. برگها در دندوگرام گرههای فردی هستند. در مقاله [11]، یک روش خوشهبندی جدید برای تشخیص ساختار جامعه در شبکه معرفی میشود که استفاده از آن برای تجزیه و تحلیل برخی از شبکههای اجتماعی، مناسب است. در این روش، افراد و روابط آنها توسط گراف وزندار نشان داده شده است. این روش در مقایسه با روشهای موجود، دارای دو ویژگی برجسته است:
- ایجاد درختان سلسله مراتبی بسیار کوچکتر که به وضوح خوشههای معنیدار را نمایش میدهند.
- تامین همپوشانی خوشهها که بازتابی از پیچیدگیهای دنیای واقعی است.
در مقاله [12] یک استراتژی برای بهبود الگوریتمهای تشخیص جامعه موجود را با اضافهکردن یک مرحله پیشپردازش که در آن به یالها با توجه به مرکزیتشان در توپولوژی شبکه وزن داده میشود، پیشنهاد شده است. در این روش، مرکزیت یال نشاندهنده همکاری آن در تراگذاری گراف است. محاسبه مرکزیت یال با انجام پیادهرویهای متعدد تصادفی با طول محدود بر روی شبکه انجام میشود که باعث میشود، محاسبات مرکزیت یال در شبکههایی در مقیاس بزرگ نیز عملی شود.
در [13] روشی بهنام Fdp ارائه شده است. این روش بر اساس DBSCAN کار میکند. روش DBSCAN نقاط را به سه دسته نقاط هسته، نقاط مرز و نقاط نویز تقسیم میکند. تقسیم نقاط توسط پارامترهای Eps و MinPts انجام میشود. Eps شعاع همسایگی هر نقطه را در مجموعه داده مشخص میکند. نقاطی که در این شعاع قرار میگیرند، نقاط همسایه خواهند بود. نقاطی که بیش از MinPts همسایه دارند به عنوان نقاط هسته، شناخته میشوند.
