بخشی از مقاله
چکیده:
بسیاری از ساختارهای پیچیده را میتوان بهصورت یک شبکه در نظر گرفت. جادهها، پایگاههای اینترنتی، شبکههای اجتماعی، ارتباطات سازمانی، روابط خویشاوندی، تبادل نامهای الکترونیک، تماسهای تلفنی و تراکنشهای مالی تنها چند نمونه از این شبکهها هستند .یکی از مهمترین فعالیتهایی که در رابطه با این تحقیقات مطرحشده، پیدا کردن گروههایی از افراد است که ممکن است بیشتر از سایرین باهم در ارتباط باشند که این مسئله تحت عنوان تشخیص ساختار جوامع در شبکههای اجتماعی، شناخته میشود.
روشهای متعددی با پیادهسازی مختلف وجود دارند که هرکدام دارای نقاط ضعف و قوت میباشند. برخی از این نقاط ضعف عبارتاند از: زمان اجرای زیاد، حساسیت به شرایط اولیه، نیاز به تعیین مقادیر پارامترهای مختلف، عدم کارایی در گرافهای بااتصال کم و عدم امکان مقیاسپذیری. در الگوریتم پیشنهادی NDOCD تکنیک خوشهبندی گرهها را جهت شناسایی اتصالات جوامع بکار گرفته و بهطور تکراری همه اتصالات تعیینکننده جوامع را حذف و شبکه را به یک شبکه با مولفه های کوچکتر تقسیم میکند.
تجزیه شبکه و بهینهسازی تکنیک خوشهبندی گره بهطور مشترک برای ساخت یک الگوریتم کارا و باصرفه ازلحاظ زمانی بکار میرود. نتایج بررسیها نشان میدهد که الگوریتم طراحیشده در جریان تحقیقات این مقاله ازلحاظ کارایی و زمان اجرا دارای برتری مشهودی بر اکثر الگوریتمهای مطرحشده قبلی در این زمینه است.
-1 مقدمه
تحلیل شبکههای اجتماعی، روشی برای بررسی نظم و سازمان موجود در روابط انسانها در اجتماع است. روشی که تحلیل شبکههای اجتماعی در اختیارمان قرار میدهد، اجازه میدهد که بتوانیم بهطور دقیق و کمی، الگوهایی را که در میان روابط مردم در اجتماع وجود دارد را تشخیص داده، ویژگیهای این الگوها را مورداندازهگیری قرار دهیم و آنها را به شکلی که برای تحلیلهای خودکار مناسب است درآوریم.
انواع متفاوتی از شبکههای پیچیده موجود هستند که میتوان مثالهایی مانند شبکههای اجتماعی، شبکههای زیستی و شبکههایی که بخشهایی از اینترنت را در برمیگیرند یا شبکههای وبی را در نظر گرفت.
خوشهبندی مشتریان وب که علایق و سلایق مشترکی دارند و یا ازلحاظ جغرافیایی نزدیک به هم هستند، ممکن است باعث ارتقا و بهبود کیفیت خدمات ارائهشده به آنها شود، به این دلیل که هر خوشهای از مشتریان، میتواند توسط یک کارگزار وقفشده، مورد خدمترسانی قرار میگیرد.
گرههایی که دارای موقعیت مرکزی در خوشهها هستند، یعنی تعداد بسیار زیاد و قابلتوجهی از ارتباطات را با سایر اعضای گروه دارا میباشند، ممکن است بتوانند نقش مهم کنترلکننده یا هدایتکننده و برقرارکننده استحکام و ثبات و پایداری در جامعه را به عهده بگیرند، درحالیکه گرههایی که در مرزهای جوامع قرارگرفتهاند، ممکن است بتوانند نقش واسط را در بین جوامع مختلف بر عهده بگیرند و روابط بین این جوامع را رهبری و هدایت کنند و مراقب مراوداتی که بین جوامع مختلف صورت میگیرند نیز باشند. لذا تشخیص نوع گرهها نیز بسیار مفید است.
تشخیص جوامع در علوم کامپیوتر نیز یک موضوع مهم محسوب میشود. بهعنوانمثال در محاسبات موازی، دانستن اینکه بهترین روش برای تخصیص وظایف بین پردازندههای مختلف بهگونهای که باعث شود که این پردازندهها کمترین ارتباطات ممکن بین یکدیگر را لازم داشته باشند و همچنین سرعت انجام محاسبات نیز بسیار بالا باشد، چگونه است بسیار حیاتی است.
بحث تشخیص تشکلها در شبکهها دارای کاربردهای عملی زیادی در دنیای واقعی است که برای مثال میتوان از: تشخیص گروهها در شبکههای اجتماعی مجازی، تبلیغات هدفمند، دستهبندی صفحات وب، طبقهبندی اسناد، رصد کاربران در شبکههای تلفن همراه و بسیار موارد دیگر نام برد.
این مقاله مشتمل بر شش بخش میباشد که در ادامهی مقدمه، در بخش دوم به بررسی و تحلیل روشهای ارائهشده در این حوزه خواهیم پرداخت. در بخش سوم، روشهای پیشنهادی ارائه خواهد شد و در بخش چهارم نتایج حاصل از اجرای آنها بر روی مجموعه دادههای آزمایشی، به همراه تحلیل آورده شده است. در بخش پنجم به معرفی روش پیشنهادی و در بخش ششم به آزمایشها، ارزیابیها و جمعبندی نتایج خواهیم پرداخت.
-2 ادبیات تحقیق
شبکه اجتماعی به این صورت تعریف میشود که یک مجموعهای از نهادهای اجتماعی که شامل مردم و سازمانها که بهوسیله مجموعهای از روابط معنیدار اجتماعی به هم متصلاند و باهم در به اشتراک گذاشتن ارزشها تعامل دارند
»شبکههای اجتماعی« را در سادهترین تقسیمبندی میتوان در دو گروه عمومی و خاص قرارداد. در شبکههای اجتماعی عمومی کاربران اینترنتی باانگیزهها و اهداف مختلف حضور دارند و شبکهسازی مجازیشان را از طریق این وبسایتها دنبال میکنند، ولی شبکههای اجتماعی خاص حول موضوعی ویژه شکلگرفتهاند و تعداد کاربرانشان نیز کمتر است. فیسبوک، اورکات و مای اسپیس مهمترین شبکههای اجتماعی عمومی در دنیای اینترنت هستند. در شبکههای اجتماعی عمومی هر نوع کاربری حضور دارد و اغلب دوستان و آشنایان آنلاین را میتوان در آنها پیدا کرد، تعداد کاربران معروفت ترین این نوع شبکهها اغلب به چند صد میلیون نفر میرسد.
علاوه بر اینها، شبکههای اجتماعی خاصی نیز وجود دارد که بر محوریت موضوعی مشخص فعالیت میکنند. بهعنوانمثال »لست اف.ام - Last.fm - « جمله معروفترین آنهاست که علاقهمندان به موسیقی را گرد هم جمع کرده، یا »گودریدز« که شبکهی اجتماعی مخصوص علاقهمندان به کتاب است و »فلیکر« که وب سایتی برای علاقه مندان به عکاسی است. گاهی نیز فعالیت شبکههای اجتماعی بر محوریت کاربران متعلق به کشور یا زبان یا نژاد یا دین خاصی متمرکز است. دربارهی موضوعات مختلف، شبکههای اجتماعی خاص ایجادشده است که از طرفداران یک تیم فوتبال تا فارغالتحصیلان یک دانشگاه را شامل میشود. حتی دربارهی سگها و گربهها نیز شبکههای اجتماعی راهاندازی شده است و صاحبان آنها میتوانند با حضور در این وبسایتها برای حیواناتشان پروفایل ایجاد کنند.
شبکههای اجتماعی با اهدافی از قبیل سازماندهی انواع گروههای اجتماعی مجازی - با تکیهبر اشتراکات مختلف و رسیدن به هدف مشترکغالباً سیاسی، اجتماعی و فرهنگی در دنیای واقعی - ، توسعه مشارکتهای اجتماعی، به اشتراک گذاشتن علاقهمندیها توسط اعضا - از مهمترین کارکردهای شبکههای اجتماعی است که بدون آن، شبکه اجتماعی معنا ندارد .کاربران دغدغهها و علایق و دلمشغولیهای خود را با یکدیگر به اشتراک میگذارند - ، ایجاد محتوا توسط اعضا - برخلاف سایر رسانهها، تعامل و تأثیرگذاری مخاطبان در تولید و انتخاب محتوای دلخواه زیاد است و قدرت انتخاب بیشتری دارند - ، تبلیغات هدفمند اینترنتی - این سایتها یکی از منابع مهم کسب درامد هستند. از این طریق که کاربران شبکههای اجتماعی علاقهمندیهای خود را در سایت اعلام میکنند و شرکتهای تبلیغاتی با آگاهی از این علاقهمندیها برای آنها آگهی میفرستند .بسیاری از شرکتها هم خود در شبکههای اجتماعی صفحه شخصی دارند و با مشتریان خود و سایر شرکتها ارتباط برقرار میکنند - ایجاد میشوند.
منظور از تحلیل شبکهها، مطالعه و تجزیهوتحلیل آنهاست. برای تحلیل شبکهها روشهای مختلفی وجود دارد. این روشها در ابتدا ریشه در جامعهشناسی و ریاضی - نظریه گراف - داشتند؛ اما امروزه علاوه بر این دو رشته در سایر علوم هم مورداستفاده قرار میگیرد
با استفاده از تحلیل شبکههای اجتماعی میتوانیم به اطلاعات مفیدی مثل میانگین دوستان یک فرد در یک شبکهی دوستی، یا میانگین فاصله دو نفر دریک شبکهی همکاران دست پیدا کنیم. بنابراین اصلیترین هدف این روش، کشف و تفسیر الگوی پیوندهای اجتماعی بین کنشگران است.کاربرد آن بهعنوانمثال، شیوع بیماری مسری را بین افراد در نظر میگیریم. سعی داریم از کمهزینهترین روشها برای جلوگیری از شیوع بیماری استفاده کنیم.
معیارهای اندازهگیری در تحلیل شبکههای اجتماعی
: Betweenness تعداد افرادی در شبکه که یک شخص بهطور غیرمستقیم از طریق خطوط مستقیم آنها متصل شده است.
: Closeness تنوع مجموعه کوتاهترین مسیرها بین هر فرد و دیگر افراد در شبکه.
:Centrality degree محاسبه میزان پیوندهایی که فرد با دیگر افراد در شبکه دارد.
: Centralization تفاوت بین تعداد پیوندها برای هر گره تقسیمشده توسط بیشترین مجموع تفاوتها؛ یعنی در یک شبکه همیشه گرههایی وجود دارند که نسبت به دیگر گرهها تعداد پیوندهای بیشتری دارند. در شبکهای دچار عدم تمرکز است تفاوت کمی بین پیوندهای هر گره وجود دارد.
: Cohesion اشاره به درجهای دارد که افراد بهطور مستقیم باهمدیگر ارتباط دارند.
:Path length مسافت بین هر دو گره در یک شبکه را میگویند، میانگین Path length درواقع میانگین مسافتهای بین تمامی جفت گرهها است.
:Structural hole تعداد کمی از افراد که اگر از گروه خارج شوند گروه از همدیگر جدا میشوند و اتصالات قطع میشود.
روشهای نمایش شبکههای اجتماعی
- 1 روش توصیفی که از طریق نمایش گراف، امکانپذیر میباشد.
- 2 رویههای تحلیلی که معمولا مبتنی بر تجزیهوتحلیل ماتریس مجاورت است.
- 3 روشهای آماری، مبتنی بر توزیع احتمال
در شبکههای اجتماعی بعضی گرهها ویژگیهای متفاوتی دارند. این گرهها بر اساس نوع ارتباطشان با سایر گرههای شبکه به چند دسته تقسیم میشوند
انواع گرهها بر اساس نوع ارتباط بین آنها عبارتاند از:
گره ستاره : گرههایی را که ارتباطات زیادی در شبکههای اجتماعی دارند را گره ستاره مینامند. درواقع در شبکههای بدون جهت، یک معیار شناسایی این گرهها درجه آنها است.
گره مجزا: گرههایی که ارتباطی با سایر گرهها ندارند و یا میزان رابطه بین آنها خیلی کم میباشد. این گرهها معمولا نقش موثری در تشخیص اجتماع ندارند.
گره پل: این گرهها نقش واسطه رابین دو گره دیگر بازی میکنند. درواقع رابط میان دو گره هستند. چنانچه ممکن است دو گره رابطه مستقیمی باهم نداشته باشند ولی از طریق گره پل بهصورت غیرمستقیم به هم متصل میشوند. در بعضی موارد این گرهها در مرز بین گرهها قرار دارند.
همچنین میتوان مجموعهای از گرهها را بر اساس میزان پیوستگیشان به چند دسته تقسیم کرد. این تقسیمبندی میتواند میزان درهم تنیدگی گرههای یک گراف را نشان دهد.
گره های کاملا پیوسته: مجموعهای از گرهها که شامل حداقل سه گره هستند و همه آنها بهطور کامل باهم ارتباط دارند.
گره های شبه پیوسته: گرههایی که چگالی اتصال آنها زیاد است ولی کاملا پیوسته نیستند.
گره های کاملا پیوسته و دارای همپوشانی: در بعضی از گرافها زیرمجموعهای از گرههای گراف دارای چند پیوستگی کامل هستند که باهم همپوشانی دارند.
تعریف جامعه بهطورکلی اینگونه بیان میشود که جامعه زیر گرافی از یک گراف است که تعداد ارتباط بین اعضای آن زیرگراف، نسبت به تعداد ارتباطاتی که آنها را به بقیهی گراف متصل میکند، بیشتر است.
