کشف جوامع در شبکه‌های اجتماعی با استفاده از کاوش الگوی تکرارشونده

مجله فناوری اطلاعات در طراحی مهندسی

مقاله 9، دوره 8، پائیز و زمستان 1394، اسفند 1394، صفحه 23-41

نویسندگان

سید احمد موسوی¹؛ مهرداد جلالی²؛ نگین میثاقیان^{* 1}

¹گروه کامپیوتر

²دانشگاه آزاد اسلامی، مشهد

چکیده

امروزه وب سایت‌های شبکه های اجتماعی به یک منبع غنی از داده های ناهمگون مبدل شده است؛ از این رو تجزیه و تحلیل این داده‌ها می‌تواند منجر به کشف اطلاعات و روابط ناشناخته در این شبکه‌ها شود. کشف جامعه متشکل از گره های «مشابه» یک چالش مهم در زمینه تجزیه و تحلیل داده های شبکه های اجتماعی است، و به طور گسترده ای در زمینه ساختار گرافی در این شبکه‌ها مورد مطالعه قرار گرفته است. شبکه های اجتماعی اینترنتی علاوه بر ساختار گرافی، حاوی اطلاعات مفیدی از کاربران درون شبکه می‌باشند؛ که استفاده از این اطلاعات می‌تواند منجر به بهبود کیفت کشف جوامع گردد.
در این مقاله یک روش به منظور کشف جامعه ارائه شده است که علاوه بر اطلاعات ارتباطی بین گره­ها از اطلاعات محتوایی به منظور ارتقا کیفیت کشف جوامع استفاده می‌گردد. این روش یک رویکرد جدید مبتنی بر الگوی تکرار شونده و بر اساس عملیات کاربران در شبکه است و به طور خاص، بر روی شبکه­های اجتماعی اینترنتی که در آن کاربران عملیات مورد علاقه خود را انتخاب می­کنند، اجرا می‌شود. ابتدا، بر اساس علایق و یا فعالیت های کاربران در شبکه، تعدادی جوامع کوچک متشکل از کاربران مشابه را کشف می کنیم و سپس با استفاده از ارتباطات اجتماعی هر جامعه را گسترش می دهیم. نتایج ارزیابی‌ F-measure بر روی دو مجموعه داده­ دنیای واقعی (بلاگ کاتالوگ و فلیکر) نشان می‌دهد که روش پیشنهادی منجر به بهبود کیفیت کشف جوامع می­شود. 

کلیدواژه‌ها

شبکه‌های اجتماعی؛ کشف جامعه؛ کاوش الگوی تکرارشونده

اصل مقاله

1-     مقدمه

بیش از دو دهه است که شبکه­های اجتماعی در زمینه تجزیه و تحلیل تعاملات بین بازیگران و تعیین الگوهای ساختاری مهم در ارتباطات مورد مطالعه قرار گرفته­اند [1]، شبکه­های اجتماعی را می­توان در زمینه­های مختلفی در نظر گرفت، سیستم‌هایی مانند فیس‌بوک[1] که به صراحت برای تعاملات اجتماعی طراحی شده است، و یا در شرایط دیگر مثل فلیکر[2] که برای سرویس‌های مختلف مانند اشتراک گذاری محتوا طراحی شده و اجازه تعامل اجتماعی را در یک سطح گسترده برای کاربران خود فراهم می‌کند. یک شبکه اجتماعی، غالباً دریک گراف بیان می­شود (شکل 1)، که در آن رأس‌ها، بازیگران و یال­ها نشانگر ارتباط میان آن­هاست [1-3] و می‌تواند در علوم گوناگون از جمله جامعه شناسی، زیست شناسی، پزشکی، شیمی، بازاریابی و علوم کامپیوتر و غیره در نظر گرفته شود. پس واضح است که مفهوم شبکه­های اجتماعی به صورت خاص به شبکه­های اجتماعی اینترنتی مثل فیس‌بوک، فلیکر، توییتر[3] و... محدود نمی‌شود. هدف ما در این مقاله صرفاً تجزیه و تحلیل شبکه­های اجتماعی اینترنتی و کشف جوامع در این شبکه‌ها می‌باشد.

وب سایت‌های شبکه اجتماعی، از طریق اینترنت توانایی منحصر به فردی برای برقراری ارتباطات و تعاملات افرادی که از لحاظ جغرافیایی پراکنده می‌باشند، را داشته، و آن‌ها را به حالت‌های مختلف با یکدیگر ارتباط داده و اجازه تعامل و اشتراک گذاری اطلاعات با افراد مختلف از جمله همکاران، آشنایان، خانواده، دوستان، طرفداران، فعالان و غیره را می‌دهد [4]. استفاده از شبکه­های اجتماعی علاوه بر فراهم­سازی ارتباطات افراد، امکان به­روز رسانی هر یک از موارد دوست داشتن، دوست نداشتن، نمایه‌ها، به اشتراک گذاری اطلاعات شخصی و عمومی را به کاربران می‌دهد [5]. بنابراین گره­ها در این نوع شبکه­ها علاوه بر ارتباطات، شامل اطلاعات دیگر از جمله فعالیت­های انجام شده توسط گره نیز هستند.

 

شکل 1) یک نمونه از شبکه اجتماعی

 

 

ساختار شبکه­های اجتماعی، شاخص خوبی برای پیش بینی اقدامات بالقوه کاربران است. بنابراین ما در شبکه­های اجتماعی اینترنتی علاوه بر ارتباطاتی که بین کاربران وجود دارد، عملیات مختلفی نیز خواهیم داشت؛ که معمولاً کاربران این عملیات را به سلیقه و تمایل خود انتخاب می‌کنند، و این سلایق کاربران است که ساختار تکاملی شبکه را می‌سازد.

یکی از چالش‌های اساسی در زمینه تجزیه و تحلیل شبکه­های اجتماعی، کشف خودکار جوامع است [6]. جوامع به عنوان گروه­ها، خوشه­ها، زیرگروه­های منسجم و یا ماژول‌ها در زمینه­های مختلف دیده می‌شوند؛ پیدا کردن جامعه در یک شبکه اجتماعی، شناسایی مجموعه­ای از گره‌هاست که بیشتر از دیگر گره­های درون شبکه با یکدیگر ارتباط برقرار می‌کنند. همزمان با توسعه سریع وب در دنیای مجازی، وب سایت‌های شبکه اجتماعی در اشکال جدیدی طراحی شده‌اند و مردم را به همکاری و ارتباطات با دیگران قادر می‌سازند. تشخیص جامعه در این وب سایت‌ها نیز می‌تواند، دیگر وظایف محاسبات اجتماعی را تسهیل کند و در بسیاری از برنامه های کاربردی استفاده شود؛ به عنوان نمونه، به گروه بندی مشتریان با منافع مشابه در رسانه­های اجتماعی، توصیه­های کارآمد کالاها، سیستم‌های پیشنهاد دهنده که در برنامه­های رسانه­های اجتماعی بسیار رایج است و طبقه بندی گره­ها می‌توان اشاره نمود. ساختار جوامع می‌تواند به منظور فشرده­سازی شبکه­ها مورد استفاده قرار گیرد و به جای تحلیل گره­ها به صورت منفرد، به تحلیل گره­های مشابه یا همان جوامع پرداخت. در این مقاله،  یک روش به منظور کشف جامعه در وب سایت‌های شبکه اجتماعی پیشنهاد می‌شود، این روش با تکیه بر اطلاعات دوستی بین کاربران و عملیاتی که هر کاربر در شبکه انجام می‌دهد به شناسایی جوامع می‌پردازد.

بخش­های بعدی مقاله به صورت زیر سازماندهی شده است:. در بخش 2 به معرفی کارهای مرتبط می‌پردازیم. سپس یک چارچوب برای کشف جامعه را در بخش 3 معرفی خواهیم کرد؛ و با آزمایشات تجربی در بخش 4 نشان می‌دهیم رویکرد ما در زمینه کشف جامعه اینترنتی موثر می‌باشد؛ و در نهایت برخی از بحث‌ها و توصیه‌ها برای کارهای آینده و همچنین نتیجه گیری را در بخش 6 بیان می­کنیم.

2-     کارهای مرتبط

مشکل تشخیص جامعه با توجه به اهمیت آن در شبکه­های اجتماعی تاکنون به طور گسترده [7-20]، مورد مطالعه قرار گرفته است. این روش‌ها بر اساس خوشه بندی‌های مبتنی بر تراکم، پارتیشن بندی حداقل-برش، مبتنی بر آمار و استنتاج، مبتنی بر معیارهای تجزیه و تحلیل شبکه­های اجتماعی، روش‌های مبتنی بر کلیک و غیره جوامع را شناسایی می­کنند، این روش‌ها فقط بر روی ارتباطات و ساختار گرافی شبکه­های اجتماعی تمرکز می‌کنند و تعاملات و علاقه‌مندی کاربران و تأثیر نفوذ کاربران در شبکه­های اجتماعی اینترنتی را در نظر نمی­گیرند. برخی از کارهای اخیر، نشان داده است که استفاده از محتوای گره یا لبه در شبکه­های اجتماعی می‌تواند در بهبود کیفیت کشف جوامع و افراد مهم در شبکه، مفید باشد [7-12, 15]. بعضی از این روش­ها اجازه نمی‌دهند کاربران در جوامع مختلف عضو باشند، و این یک مشکل به حساب می‌آید، البته برخی محققان نیز بر این باورند که در کاربردهایی بهتر است هر گره تنها به یک جامعه متعلق باشد، با این حال اکثر کاربردها به همپوشانی گره‌ها نیاز دارند. برای حل این چالش محققان در پژوهش‌هایی دیگر روش‌های مبتنی بر مدل احتمالی بیزین را پیشنهاد داده‌اند [21-23] این مدل‌ها برای اعضای جامعه اجازه همپوشانی را می‌دهند ولی در این روش‌ها بیش از حد به ساختار گراف شبکه برای کشف جامعه تکیه دارند. برخی کارها نیز با بهره گیری از عملیات کاربران به کشف افراد با نفوذ در شبکه­های اجتماعی اینترنتی پرداخته‌اند [7, 8, 12].

در این مقاله روشی ارائه می‌شود که به منظور کشف جامعه، علاوه بر ساختار گرافی از محتوای شبکه­های اجتماعی نیز استفاده می‌کند، همچنین اجازه همپوشانی به جوامع در این روش داده می‌شود. در این روش ابتدا گره­های مهم شبکه استخراج می‌شوند سپس حول این گره‌ها جوامع شکل می‌گیرند. در ادامه به برخی از کارهای مرتبط با روش پیشنهادی اشاره می‌نماییم. گویال[4] و همکاران، یک الگوریتم برای استخراج رهبران با استفاده از تأثیرگذاری گره‌ها روی یکدیگر، با فرض اینکه یک شبکه اجتماعی شامل یک گراف و یک جدول عملیات می‌باشد، ارائه داده‌اند؛ که گراف، ارتباط دوستی بین کاربران را نشان می‌دهد و جدول عملیات نشان دهنده عملیات انجام شده توسط هر کاربر می‌باشد. در این روش با استفاده از الگوریتم الگوی تکرار شونده SWF جدول عملیات پویش شده و در یک ماتریس نگاشت می‌شود، و در نهایت افراد مهم شبکه (رهبران) استخراج می‌شوند. در این روش رهبران، در یک عمل خاص به عنوان رهبر شناسایی می‌شوند و افرادی هستند که آن عمل خاص را زودتر از دوستان خود انجام داده‌اند؛ مفهوم گراف انتشار اولین بار در این روش ارائه شد که با ایجاد این گراف برای هر عمل در شبکه، کاربری به عنوان رهبر شناسایی می‌شود. دو حد آستانه اطمینان[5] و صحت[6] برای تشخیص یک رهبر واقعی از یک رهبر غیرواقعی در نظر گرفته شده است [8].

عدنان[7] و همکاران با استفاده از مفهوم الگوی تکرار شونده بسته، به شناسایی جوامع در شبکه­های اجتماعی می‌پردازند. با فرض اینکه یک مجموعه E داریم که شامل n گره است،  هر گره  با یک مجموعه داده  در ارتباط است که عملیات مربوط به این موجودیت را نشان می‌دهد، بنابراین برای هر موجودیت یک مجموعه داده تراکنشی وجود دارد. با استفاده از الگوی تکرار شونده بسته، می‌توان این مجموعه داده را به یک بردار ویژگی تبدیل نمود، حال این بردار ویژگی می‌تواند به عنوان یک نماینده مؤثر برای عملیات انجام شده توسط گره مربوطه در نظر گرفته شود. شباهت بردارهای ویژگی که نشان دهنده عملیات گره‌ها می‌باشد، توسط روش‌های اندازه گیری شباهت مثل دات پروداکت[8] محاسبه می‌شود. هنگامی که اندازه گیری فاصله و شباهت را داشته باشیم می‌توانیم با بسیاری از روش‌های استاندارد خوشه بندی، جوامع را شناسایی کنیم [7].

برخی تحقیقات انجام شده نیز ابتدا به کشف رهبران در شبکه می‌پردازند و سپس حول این رهبران جوامع را گسترش می‌دهند. به عنوان نمونه کاناویتی[9]  در مقاله ای به منظور کشف جامعه، ابتدا K رهبر را با استفاده از متریک‌های مرکزیت استخراج می‌کند؛ که در این مقاله از درجه نزدیکی، بینابینی و درجه مرکزیت استفاده شده است. سپس همسایگان مرتبط با هر رهبر، یک جامعه کوچک را تشکیل می‌دهد. به این صورت که گره‌های معمولی (پیرو)، به نزدیک‌ترین رهبر منتسب می‌شوند، و جامعه مربوط به آن‌ها مشخص می‌گردد[11]. ربانی خراسگانی[10] و همکاران نیز در روش خود ابتدا رهبران و افراد معتبر را بر اساس متریک‌های تحلیل شبکه­های اجتماعی، بدست می‌آورند. متریک‌های مورد استفاده در این مقاله درجه مرکزیت و بینابینی می‌باشند. حال برای هر گره غیر رهبر بررسی می‌کند که چقدر عضویت (شباهت) به هر رهبر دارد، پس هر گره نسبت به هر رهبر دارای یک وزن می‌باشد. حال یک رای گیری بین گره­های همسایه گره مربوطه می‌شود و در نهایت آن گره به یک رهبر اختصاص داده می‌شود. بنابراین یک جامعه خواهیم داشت که رهبر مشخصی دارد؛ رهبر در این جامعه دوباره با استفاده از متریک‌های مذکور به دست می‌آید و هر گره دوباره برای تعیین رهبر بررسی می‌گردد. این مراحل را تا زمانی که به یک همگرایی (رهبر در هر مرحله تغییر نکند) برسیم، ادامه می‌دهیم. از الگوریتم K-means در خوشه بندی، به منظور ارائه این روش الهام گرفته شده است. برای تخمین مقدار K روش‌هایی نیز در این مقاله ارائه شده‌اند[10]. دونگ یوان لو[11]  و همکاران [12]، پژوهشی روی شبکه اجتماعی فلیکر و شبکه های همانند آن که سرویس اشتراک گذاری فایل‌هاست، انجام داده‌اند و با استفاده از چند عامل حجم طرفدار[12]، پوشش طرفدار[13] و به هنگام بودن طرفدار[14]، افراد معتبر (رهبر) را شناسایی می‌کنند. حجم طرفدار، به تعداد عکس‌های پسندیده شده توسط دیگر اعضا برای عضو مورد نظر گفته می‌شود. پوشش طرفدار، نشان دهنده چگونگی گستردگی یک عضو تایید شده است، این تنها تعداد طرفداران یک عضو نمی‌باشد؛ بلکه درجه نفوذ اولیه این طرفداران را در نظر می‌گیرد. به عنوان مکمل حجم طرفدار، برای جلوگیری از تعصب ناشی از طرفداران، که به عکس‌های یک عضو خاص دارند؛ این عامل در نظر گرفته می‌شود. افرادی که طرفدارانی بانفوذ (طرفداران پر طرفدار)، دارند وزن بیشتری از این عامل خواهند داشت. به هنگام بودن طرفدار، به حساسیت زمانی اقدامات طرفداران یک عضو اشاره می‌کند. یک عضو با حجم طرفدار بالا، پوشش طرفدار بالا و دریافت بیشتر طرفداران اخیر به احتمال زیاد مهارت و اعتبار بیشتری در شبکه خواهد داشت. همچنین در این تحقیق چالش تغییرات شبکه های اجتماعی که به تبع آن افراد معتبر و جوامع تغییر می‌کنند، را مدنظر قرار داده و برای آن راه حلی ارائه می‌دهد.

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

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

ما یک رویکرد جدید به منظور کشف جامعه، با استفاده از اجرای الگوریتم کاوش الگوی تکرار شونده [28] روی مجموعه عملیات کاربران و اجرای الگوریتم طبقه بندی روی مجموعه ارتباطات بین کاربران، ارائه می‌دهیم. روش ارائه شده به طور خاص روی وب سایت‌های شبکه­های اجتماعی اجرا می‌شود. ما فرض می‌کنیم که جامعه از تعدادی رهبر و تعدادی پیرو (در تشریح مراحل توضیح داده خواهند شد) تشکیل شده است. به طور خلاصه در این روش سعی می‌شود که ابتدا گروه­های کوچکی از کاربران استخراج شوند، به طوری که کاربران عضو هر گروه از نظر عملکرد در شبکه مشابه باشند؛ سپس کاربرانی که در همسایگی این گروه­ها قرار دارند به عنوان پیروان این گروه­ها شناسایی شوند. در ادامه خلاصه­ای از مراحل روش پیشنهادی را بیان خواهیم کرد. این روش به منظور کشف جامعه در شبکه­های اجتماعی، از چهار مرحله اصلی تشکیل شده است (شکل 2) که عبارتند از:

1. پیش پردازش داده­ها
2. استخراج گروه­های همگن (کاوش الگوی تکرار شونده کاربری)
3. تایید گروه­های همگن به عنوان جوامع کوچک
4. گسترش جوامع کوچک

 

• مرحله اول) در صورت نیاز پیش پردازشی روی مجموعه داده انجام می‌شود، تا ورودی‌ها، شامل جدول عملیات-کاربر و جدول همسایگی متناسب با الگوریتم آماده شوند. در این مرحله، مقدار سه حد آستانه مورد نیاز الگوریتم نیز، با توجه به اطلاعات شبکه تخمین زده می‌شوند. این حد آستانه‌ها α، β و ¥ در مراحل مورد استفاده شرح داده خواهند شد.
• مرحله دوم) با اجرای الگوریتم کاوش الگوی تکرار شونده روی جدول عملیات-کاربر، الگو های حداکثر[15] استخراج می‌شوند. هر الگوی استخراج شده، شامل دنباله‌ای از کاربران است که عملکرد مشابهی در شبکه داشته‌اند. ما هر دنباله از این کاربران را یک گروه همگن[16] می‌نامیم. ¥ به عنوان حد آستانه پشتیبان[17] الگوریتم کاوش الگوی تکرار شونده در این مرحله استفاده می‌شود.

 

 

 

 

 

 

 

 

شکل 2:  مراحل کشف جامعه در روش پیشنهادی

 

• مرحله سوم) کاربران عضو هر گروه همگن، افرادی با عملکرد و یا سلایق مشابه در شبکه را نشان می‌دهد اما ممکن است افراد درون هر گروه در گراف اجتماعی پراکنده باشند و گروه‌های منسجمی تشکیل نگردد. افراد درون این گروه‌ها در صورتی می‌توانند به عنوان اعضای آن گروه ایفای نقش کنند که با یکدیگر مرتبط باشند. این ارتباط، الزاماً به معنی اتصال مستقیم و وجود لبه بین گره­ها نیست و ممکن است ارتباط با گره­های واسط، تا یک حد آستانه نیز مورد قبول باشد، این حد آستانه را β می‌نامیم. خروجی این مرحله، گروه‌هایی از کاربران است که در هر کدام از آن‌ها تعدادی از کاربران مشابه و مرتبط عضو هستند، هر یک از این گروه­ها را یک جامعه کوچک می‌نامیم.
• مرحله چهارم) جوامع کوچک استخراج شده از مرحله قبل، اغلب تعداد کمی از کاربران را پوشش می‌دهند، هدف از این مرحله گسترش جوامع استخراج شده است. ما هر جامعه کوچک را به عنوان هسته­ای از یک جامعه، و افرادی که در همسایگی آن‌ها هستند را به عنوان پیروان این جوامع کوچک در نظر می‌گیریم. بنابراین جوامع کوچک با توجه به ارتباطات توسعه می‌یابند و به جوامع با اندازه ­های مورد قبول تبدیل می‌شوند، از ورودی α نیز به عنوان حد آستانه در این مرحله استفاده خواهد شد.

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

3-1-     مرحله اول: پیش پردازش داده­ها

به عنوان ورودی روش پیشنهادی به یک جدول عملیات-کاربر و یک جدول همسایگی (گراف) نیاز خواهیم داشت. جدول عملیات-کاربر، عملیات انجام شده توسط کاربران به ازای هر عمل ممکن در شبکه را نشان می‌دهد، و جدول همسایگی حاوی ارتباطات دوستی بین کاربران است. معمولاً این جدول را به صورت یک گراف (شکل 3) نمایش می‌دهیم.

• گراف دوستی بین کاربران

 

شکل 3: روابط دوستی بین کاربران

 

• جدول عملیات-کاربر

چارچوب ارائه شده در این مقاله بر روی وب سایت‌های شبکه­های اجتماعی متمرکز شده است، معمولاً در این وب سایت‌ها، مجموعه عملیات مجازی وجود دارد که هر کدام از کاربران می‌توانند به انتخاب و سلیقه خود برخی یا همه آن‌ها را انجام دهند. به عنوان نمونه در شبکه اجتماعی دلیشز[18] کاربران روی منابع مختلف موجود در شبکه برچسب‌های مختلف می‌زنند، در این شبکه اجتماعی، برچسب‌های مختلف یا منابع می‌تواند به عنوان عملیات مجاز در شبکه قلمداد شود. به عنوان مثالی دیگر یک شبکه اجتماعی کتاب، مثل گودریدز[19] را در نظر بگیرید. کاربران در این شبکه، کتاب یا کتاب‌های مورد علاقه خود را انتخاب و مطالعه می‌کنند و به آن امتیاز می‌دهند، در اینجا نیز مجموعه کتاب‌های موجود در شبکه همان عملیات مجاز برای کاربران خواهد بود. به عنوان مثال سوم، در شبکه اجتماعی موسیقی همانند لست اف ام[20] کاربران، هنرمند مورد علاقه خود را انتخاب می‌نمایند یا روی موسیقی‌های ارائه شده از هنرمندان مختلف برچسب می‌زنند، در اینجا مجموعه هنرمندان می‌تواند به عنوان مجموعه عملیات شبکه باشد. در شبکه‌هایی همچون فیس‌بوک، توییتر، یوتیوب و... نیز می‌توان از دیدگاه­های مختلف عملیات مجاز در شبکه را در نظر گرفت. نکته­ای که در رابطه با عملیات مجاز حائز اهمیت می‌باشد این است که بایستی عملیاتی در شبکه انتخاب ‌شود که کاربران در انجام آن مختار باشند، به عنوان مثال عملیاتی همچون ورود[21] یا خروج[22] نمی‌تواند به عنوان عملیات در جدول عملیات-کاربر قرار بگیرد، چرا که همه کاربران این عملیات را انجام خواهند داد.  

شکل 4، فایل عملیات را که معمولاً به صورت یک سه تایی (کاربر، عمل، زمان) می‌باشد را نشان می‌دهد که برای ساخت جدول عملیات-کاربر تنها از ستون کاربر و عمل استفاده می‌شود.

 

 

 

 

 

 

 

 

 

شکل 4: ایجاد جدول عملیات-کاربر از فایل عملیات

• اهداف مرحله اول

ü      آماده سازی جدول همسایگی (معمولاً نیاز به پیش پردازش ندارد)

ü      آماده سازی جدول عملیات-کاربر

ü      علاوه بر آماده سازی ورودی روش پیشنهادی، مقادیر حد آستانه α، β و ¥ نیز در این مرحله تخمین زده می‌شوند، بهتر است این حد آستانه­ها توسط یک متخصص و با توجه به اندازه شبکه اجتماعی، تعداد گره­ها، تعداد لبه­ها و تعداد عملیات درون شبکه تخمین زده شود. هر کدام از این حد آستانه­ها در مراحل مربوطه شرح داده می‌شوند.

3-2-      مرحله دوم: کاوش الگوی تکرار شونده کاربری

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

 

• پیاده سازی مرحله الگوی تکرار شونده کاربری

فرض کنید الگوریتم کاوش الگوی تکرار شونده، روی جدول عملیات-کاربر اجرا شود (شکل 4). خروجی، دنباله­ای از کاربران خواهد بود که در عملیات مشابهی با یکدیگر دیده شده‌اند (به تعداد حد آستانه یا بیشتر). با توجه به حد آستانه پشتیبان ¥،  الگوریتم‌ کاوش الگوی تکرار شونده روی این جدول اجرا خواهد شد و “الگوهای حداکثر” [35] کاوش می‌شوند. دقت داشته باشید الگوهای حداکثرِ تک قلمی هرس می‌شوند. الگوی حداکثر در شکل 4 در صورتی که  باشد، خواهد بود و نشان می‌دهد این دو کاربر در انجام 2 یا بیشتر از 2 عمل در شبکه شباهت داشته‌اند. می‌توان از الگوریتم‌های تکرار شونده شناخته شده­ای همچون Apriori [29] بهره جست.

 

 

 

شکل 5: اجرای الگوریتم الگوی تکرار شونده روی جدول عملیات-کاربر

 

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

 

• اهداف مرحله دوم

ü      خروجی این مرحله پس از اجرای الگوریتم کاوش الگوی تکرار شونده، دنباله‌هایی از کاربران است؛  هر دنباله را یک گروه همگن می‌نامیم. هر گروه همگن شامل دو یا چند کاربر است، و نشان می‌دهد که کاربران عضو آن به تعداد حد آستانه ¥ یا بیشتر از آن عملیات مشابه انجام داده‌اند؛ بنابراین می‌توان گفت کاربران درون هر گروه از نظر انجام عملیات هم سلیقه و همسو می‌باشند.

 

3-3-      مرحله سوم: تایید جوامع کوچک

همان طور که مشخص است هر گروه همگن، شامل کاربرانی است که از نظر انجام عملیات به یکدیگر شباهت دارند؛ اما ممکن است این کاربران در گراف اجتماعی درجه جدایی زیادی داشته باشند، به عبارت دیگر کاربران درون هر گروه نامتراکم و پراکنده باشند. مناسب است اعضای هر گروه تا حدودی در گراف اجتماعی به هم مرتبط و نزدیک باشند، تا به عنوان یک گروه منسجم تایید شوند. هدف از این مرحله نیز شکستن گروه­های نامتراکم به چند گروه یا حذف آن‌ها و تایید گروه­های منسجم است. منظور از گروه منسجم و متراکم گروهی است که کاربران درون آن به هم مرتبط باشند. البته این ارتباط در همه شبکه­ها الزاماً به معنای اتصال مستقیم (وجود لبه) بین گره­ها نیست، بلکه ارتباط با گره­های واسط تا یک حد آستانه، نیز مورد قبول می‌باشد؛ تعداد مجاز این واسط‌ها را حد آستانه β مشخص می‌کند. 

حد آستانه β: این حد آستانه تعیین می‌کند که بین دو گره در گراف اجتماعی، حداکثر چند لبه باشد تا آن دو گره را مرتبط بنامیم؛ مقدار حد آستانه β را یک متخصص تعیین می‌کند. این مقدار ثابت در نظر گرفته نشده است چرا که  شبکه­ها با اندازه­های مختلفی وجود دارند. با این حال با اجرای روش پیشنهادی روی چندین مجموعه داده واقعی و آزمون- خطا، مناسب‌ترین مقدار β را کوچک‌تر یا مساوی3  ( ) یافتیم.

در این مرحله اگر کاربران درون هر دنباله استخراج شده از مرحله قبل، با حد آستانه β به هم مرتبط شوند به عنوان یک جامعه کوچک تایید می‌شوند؛ در غیر این صورت گروه هرس می‌شود یا به چند گروه کوچک‌تر تبدیل می‌گردد. خروجی این مرحله گروه‌هایی از کاربران را نشان می‌دهد که کاربران درون هر کدام از آن‌ها علاوه بر اینکه به تعداد ¥ یا بیشتر از آن خصوصیات مشابه دارند، در گراف اجتماعی شبکه نیز، حداکثر به تعداد β از هم فاصله داشته‌اند؛ ما هر یک از این گروه­ها را یک “جامعه کوچک” می‌نامیم. سؤالی که در اینجا پیش می‌آید این است که این تئوری، چگونه با کمترین پیچیدگی زمانی قابل پیاده سازی می‌باشد؟ چرا که بین دو گره در یک گراف، ممکن است چندین مسیر وجود داشته باشد. برای تحقق هدف این مرحله باید همه مسیرهای بین دو گره، به منظور یافتن کوتاه‌ترین مسیر بررسی شود و در صورتی که فاصله کوتاه‌ترین مسیر بین دو گره کمتر یا مساوی β باشد، گروه تایید خواهد شد. این در حالی است که الگوی تولید شده از مرحله دوم می‌تواند به تعداد گره­های درون شبکه نیز باشد، و هیچ محدودیتی در طول دنباله­های استخراج شده در الگوریتم‌های کاوش الگوی تکرار شونده نخواهد بود. از سوی دیگر هدف ما یافتن کوتاه‌ترین مسیر بین چندین گره، در یک گرافِ بدون وزن است که پیچیدگی زمانی کمی داشته باشد.

• پیاده سازی مرحله تایید جوامع کوچک (گروه های همگن)

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

 

 

 

 

 

 

 

شکل 6:  مرحله تایید گروه همگن به عنوان یک جامعه منسجم

 

 در این مثال قصد داریم با توجه به حد آستانه β، صحت ارتباط بین گره 2 و گره 5 را بررسی کنیم (که در مرحله قبل به عنوان یک گروه همگن استخراج شدند). اگر حد آستانه β را در این مثال 2 فرض کنیم (=2β)، در صورتی این دو گره به عنوان یک گروه در این مرحله تایید می‌شوند که بین کوتاه‌ترین مسیر ارتباطی آن‌ها، حداکثر دو گره واسط وجود داشته باشد. در گام اول هر گره عضو گروه، نام خود را در حافظه خود ذخیره می‌کند؛ حافظه دیگر گره­ها در گام اول خالی می‌باشد. در گام دوم همه گره­های عضو گروه، حافظه خود را برای همسایگانشان ارسال می‌کنند. همسایگان پیام‌ها را دریافت و با حافظه خود ادغام می‌کنند. در اینجا متغیری به نام step خواهیم داشت که به ازای هر گامِ ارسال، یک واحد به آن اضافه می‌شود. حداکثر مقدار مجاز برای step برابر مقدار حد آستانه β می‌باشد. پس از اینکه step به این مقدار رسید حافظه گره­ها بررسی می‌شود و در صورتی که حافظه تنها یک گره، حاوی نام گره­های درون گروه بود (در اینجا 2 و 5 اعضای گروه هستند)، این گره­ها با حد آستانه β با هم مرتبط هستند. پس در گام دوم مقدار step برابر 1 می‌شود، با بررسی حافظه گره­ها در گام سوم، صحت ارتباط دو گره با حد آستانه 2 تایید می‌شود. اگر در حافظه هیچ یک از گره­ها، دنباله کامل نبود، گروه حذف خواهد شد. به عنوان مثال در اینجا در صورتی که =1β باشد گروه متشکل از گره­های 2 و 5 هرس می‌شوند. برای دیگر جوامع کوچک کشف شده (در اینجا گره­های 1 و 6) این مراحل را انجام می‌دهیم.

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

• اهداف مرحله سوم

ü      هر گروه­ دو یا چندکاربره به منظور صحت ارتباط بین اعضایش، با توجه به حد آستانه β مورد بررسی قرار می‌گیرند. در صورت صحت ارتباط بین اعضا، گروه، بدون تغییر به مرحله بعد ارسال می‌شود، در غیر این صورت حذف می‌گردد.

ü       خروجی این مرحله گروه‌هایی از کاربران را نشان می‌دهد که کاربران درون هر گروه، به تعداد ¥ یا بیشتر از آن خصوصیات مشابه در شبکه دارند، و در گراف اجتماعی شبکه حداکثر به تعداد β از هم فاصله داشته‌اند، ما این گروه­ها را جوامع کوچک می‌نامیم.

3-4-      مرحله چهارم: گسترش جوامع کوچک

هر جامعه کوچک را می‌توان مجموعه­ای از رهبرانی (افرادی که معمولاً مهارت بیشتری در زمینه خاصی دارند، و یا در یک شبکه اجتماعی افراد تحت تأثیر آن‌ها قرار می‌گیرند، به عنوان رهبر شناخته می‌شوند [30] ) دانست که در برخی عملیات شبکه می‌توانند به عنوان انتشار دهنده آن عملیات ایفای نقش کنند. کاربرانی که در همسایگی یک جامعه کوچک هستند، به دلیل روابط نزدیکی که با افراد درون جامعه دارند، با احتمال بیشتری به آن‌ها شباهت خواهند داشت؛ افراد به طور مستقیم تحت تأثیر همسایگان خود هستند. به عنوان مثال فرض کنید یک کاربر در یک شبکه اجتماعی اینترنتی عملی را انجام می‌دهد، حال دوستان این فرد قادر خواهند بود، انجام آن عمل خاص توسط این کاربر را مشاهده کنند؛ این شانسی است که آن‌ها نیز به شخصه بتوانند آن عمل را انجام دهند. حال فرض کنید از این افراد، تعدادی این عمل را انجام می‌دهند؛ دوستان مشترک این افراد با توده­ای از کاربران در ارتباط هستند که یک عمل خاص را انجام داده‌اند، بنابراین برای انجام آن عمل وسوسه‌ی بیشتری خواهند داشت[31]. این انتشار انجام عمل، پایه و اساس بازاریابی ویروسی در اینترنت می‌باشد. حال کل عملیات مجاز در شبکه را در نظر بگیرید، و افراد هم سلیقه­ای که تعداد زیادی عملیات مشابه در شبکه انجام داده‌اند؛ بنابراین توده­ای از افراد را تشکیل می‌دهند که انتشار دهنده این عملیات مشابه هستند. بنابراین می‌توان گفت با گسترش جوامع کوچک، افرادی مشابه و یا افرادی که احتمالاً در آینده در یک سمت و سو حرکت می‌کنند، شناسایی خواهند شد.

ما فرض می‌کنیم همسایگان هر جامعه کوچک، از پیروان آن جامعه خواهد بود؛ از این رو جوامع استخراج شده از مرحله قبل را توسعه داده و متناسب با حد آستانه α به جوامع با اندازه­های مورد قبول می‌رسیم. برای این کار، از الگوریتمی مشابه الگوریتم‌های طبقه بندی استفاده می‌کنیم. گره‌هایی که جامعه مشخصی ندارند به عنوان پیروان جوامع، به نزدیک‌ترین جامعه کوچک انتساب داده می‌شوند، به عبارت دیگر هر گره غیر رهبر به جامعه ای منتسب می‌شود که رای بیشتری را از آن جامعه داشته باشد. در ادامه به روش پیشنهاد شده به منظور گسترش جوامع اشاره می­شود.

 

• پیاده سازی مرحله گسترش جوامع کوچک

پس از اجرای مرحله سوم، گروه­های کوچکی از کاربران استخراج می‌شوند که از آن‌ها به عنوان جوامع کوچک یاد می‌شود. هر جامعه کوچک شامل گره‌هایی (کاربرانی) است که از نظر انجام عملیات در شبکه به یکدیگر مشابه بوده‌اند. همان طور که گفته شد افراد ممکن است تحت تأثیر همسایگان خود قرار گیرند، حال آنکه اگر تعداد همسایگان بیشتری از یک گره، عملیات مشابهی را انجام دهند این تأثیر گذاری بیشتر خواهد شد. این روش از دو حد آستانه α و µ به منظور گسترش گروه­های استخراج شده، استفاده می‌کند.

حد آستانه µ: این حد آستانه در این الگوریتم تعیین می‌کند که چه تعداد همسایگان یک گره، عضو یک جامعه باشند تا گره مذکور عضو آن جامعه شناسایی گردد. مقدار این حد آستانه یک عدد بین 0 تا 1 خواهد بود.

حد آستانه α: این حد آستانه نشان می‌دهد که افراد عضو یک جامعه تا چه سطحی از همسایگان خود را به عنوان پیروان خود بپذیرند. هر چه مقدار این حد آستانه بزرگ‌تر باشد تعداد افراد عضو جوامع پس از مرحله گسترش، بیشتر خواهد بود.

ü      پیاده سازی

در این روش گره­های معمولی (گره‌های غیر رهبر)، به جامعه­ای منتسب می‌شود که همسایگان بیشتری از گره­های عضو آن جامعه خاص، داشته باشند بنابراین ممکن است جوامع همپوشانی داشته باشند، همچنین برخی گره‌ها که پس از رای گیری به جامعه خاصی منتسب نمی‌شوند Outlier شناخته می‌شوند.

برای درک بهتر این الگوریتم، دو جامعه کوچک  و  را در گراف اجتماعی  شکل 7 در نظر بگیرید، هر دو جامعه از دو عضو در گراف تشکیل شده‌اند.

 

 

شکل 7: روش رای گیری

 

اگر حد آستانه =0.6 µ باشد بدین معنی است که هر کاربر برای عضویت در هر یک از جوامع  یا  به همسایگی 60 درصد از گره­های این جوامع یعنی هر دو گره در هر گام نیاز دارند، چرا که این دو جامعه در گام اول تنها از دو گره تشکیل شده است (شکل 8).

ü      در گام اول که α=1 است، گره­های 7 و 9 به گروه  و گره 2 به گروه  می‌پیوندند.

ü      در گام دوم α=2 است و گره 3 به گروه  می‌پیوندد (در اینجا 60 درصد همسایگی برای جامعه G1 که از 3 گره تشکیل شده است، همسایگی 2 گره خواهد بود)؛ گروه  بدون تغییر باقی خواهد ماند، چرا که هیچ گره ای با 60 درصد از گروه  در ارتباط نیست.

ü      در گام سوم α=3 است ولی گره 4 به گروه  نمی‌پیوندد، چرا که گره 4 با 60 درصد از گره­های گروه  در ارتباط نیست؛ بنابراین هر دو گروه بدون تغییر باقی خواهند ماند.

 

 

شکل 8: پیاده سازی روش رای گیری و گسترش جوامع

 

به طور کلی روش پیشنهاد شده به منظور کشف یک جامعه سعی دارد ابتدا تعدادی از گره­های مشابه را به عنوان هسته (رهبران) جامعه، شناسایی کند و سپس این هسته را در گراف اجتماعی، با استفاده از ارتباطات، گسترش داده (پیروان)، و تعداد بیشتری از گره­ها را به عنوان جامعه پوشش دهد (شکل 9)

 

شکل 9: چگونگی ایجاد جوامع در روش پیشنهادی

 

• اهداف مرحله چهارم

ü      در این مرحله به هدف اصلی روش پیشنهادی، یعنی استخراج جوامع می‌رسیم. این جوامع شامل گره‌هایی هستند، که از نظر عملیات مشابه و تا حدودی مرتبط هستند.

4-     ارزیابی

روش‌های متعدد کشف ساختار جامعه ، ارزیابی این روش‌ها را به یک چالش مهم در این زمینه تبدیل کرده است. ارزیابی الگوریتم، اساساً بدین معناست که الگوریتم مورد نظر به منظور حل یک مشکل خاص نسبت به دیگر روش‌ها در آن مشکل خاص تایید شود. در این مورد یعنی”کشف جامعه“ در ساختار شبکه­های اجتماعی، مسئله کاملاً روشن است و هدف نهایی همه الگوریتم‌ها در این زمینه شناسایی گره­های مشابه به عنوان جامعه می‌باشد. یکی از دلایل اصلی که ارزیابی روش‌های استخراج جامعه را با مشکل مواجه نموده است، این است که یک تعریف واضح و روشن از ساختار جامعه در یک شبکه دنیای واقعی وجود ندارد و ممکن است هر الگوریتم نسبت به کاربرد استفاده شده شباهت بین گره­ها را محاسبه کند.

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

4-1-     معیارهای ارزیابی:

 متخصصان حوزه شبکه­های اجتماعی برخی معیارهای ارزیابی استاندارد را معرفی نموده‌اند که می‌توان به منظور ارزیابی از آن‌ها بهره جست. یکی از این معیارها معیار F-measure می‌باشد که به منظور ارزیابی روش پیشنهادی از آن استفاده می‌شود. این معیار شامل دو فاکتور اصلی دقت[23] و فراخواندن[24] است که از رابطه زیر بدست می‌آید [32].

 

1)     

 

2)     

 

 

3)     

 

4-2-     مجموعه داده

به منظور ارزیابی روش پیشنهادی از مجموعه داده شبکه اجتماعی فلیکر وبلاگ کاتالوگ[25] استفاده شده است.

 

4-2-1- مجموعه داده فلیکر[26]

فلیکر[27] یکی از بزرگ‌ترین سایت‌های اشتراک گذاری تصویر و ویدئو، خدمات وب و جوامع اینترنتی می‌باشد، که توسط  لادیکارپ[28] در سال ۲۰۰۴ ایجاد شد و در سال ۲۰۰۵ توسط یاهو خریداری گردید. هر کاربر در این شبکه اجتماعی می‌تواند تصاویر خود را به اشتراک بگذارد و عضو گروه­های مختلف شود. گروه فلیکر را هر عضو از این سایت می‌تواند بسازد. سازنده‌ی یک گروه فلیکر، توانایی نظارت و تعیین محدودیت‌های گروه را دارد. گروه‌ها یک راه برقراری ارتباط بین اعضای فلیکر پیرامون عکس و فیلم است. با انتخاب گروه، گاهی اوقات هنگام ورود به سامانه پیامی خصوصی به کاربر ارسال می‌شود. کاربران می‌توانند روی تصاویر و فایل‌های به اشتراک گذاشته شده دیگر کاربران برچسب بزنند. مجموعه داده­های زیادی از این شبکه انتشار یافته است، مجموعه داده ای که در این مقاله استفاده می‌شود در سال 2012 ارائه شده است و شامل بیش از 35000 کاربر است. این مجموعه داده به دلیل وجود فایل گروه بندی شده کاربران (برچسب کلاس)، مناسب ارزیابی الگوریتم‌های کشف جامعه و طبقه بندی می‌باشد و اطلاعات زیر را شامل می‌شود:

• روابط: اطلاعات روابط دوستی (بدون جهت) بین کاربران
• محتوای ایجاد شده توسط کاربران: برچسب‌های مجموعه تصاویر هر کاربر، جمع آوری شده است.
• گروه: گروه‌هایی که هر کاربر عضو آن است، ذخیره شده است.

 

4-2-2- مجموعه داده بلاگ کاتالوگ[29]

بلاگ کاتالوگ یک شبکه اجتماعی و یکی از بهترین مکان‌ها برای پیدا کردن وبلاگ‌ها و وبلاگ نویسان می‌باشد، که در آن کاربران قادر خواهند بود که وبلاگ‌های خود را معرفی نمایند، و یادداشت‌های روزانه عمومی و خصوصی خود را در آن ذخیره کنند. همچنین این کاربران می‌توانند دوستان خود را در این شبکه داشته باشند. مجموعه داده ای که در این پژوهش از این شبکه مورد استفاده قرار گرفته است، شامل 90000 کاربر است. از آنجا که این مجموعه داده شامل اطلاعات گروه بندی کاربران است، مناسب برای ارزیابی الگوریتم‌های کشف جامعه و طبقه بندی خواهد بود. این مجموعه داده شامل اطلاعات زیر است:

• روابط: اطلاعات روابط دوستی (بدون جهت)  بین کاربران
• محتوای ایجاد شده توسط کاربران: برچسب‌هایی که کاربران برای وبلاگ‌های خود در نظر گرفته‌اند.
• گروه: هر کاربر نسبت به برچسب‌هایی که برای وبلاگ خود قرار داده است، گروه بندی شده است.

 

4-3-     نتایج

با اجرای روش‌های مختلف کشف جامعه روی دو مجموعه داده فلیکر و بلاگ کاتالوگ جوامع را شناسایی نمودیم، نتایج در نمودارهای شکل 11و شکل 13(به ترتیب نتایج مجموعه داده فلیکر و بلاگ کاتالوگ) ارائه شده است. در این نمودارها میانگین مقادیر سه پارامتر دقت، فراخواندن و معیار F نشان داده شده است. هر یک از این میله‌ها نشان دهنده یک روش کشف جامعه می‌باشد، سه میله اول روش پیشنهاد شده با مقادیر مختلف Alpha  را نشان می‌دهد. میله چهارم یک روش کشف جوامع مبتنی بر پیمانه­ای [33] ، میله پنجم مبتنی بر خوشه بندی [34] و میله ششم و هفتم دو روش مبتنی بر رهبر-پیرو [35,10] را نشان می‌دهد. دلیل انتخاب دو روش مبتنی بر پیمانه ای و مبتنی بر خوشه بندی به منظور مقایسه با روش پیشنهادی این بود که نشان دهیم استفاده از محتوا در کشف جوامع در روش پیشنهادی به چه میزان موثر بوده است، چرا که در این دو روش تنها از ساختار گرافی شبکه به منظور کشف جوامع استفاده می‌شود. اما دو روش مبتنی بر رهبر و پیرو (میله ششم و هفتم) که می‌توان گفت مشابه روش پیشنهادی عمل می‌کنند (ابتدا گره­های رهبر بر اساس معیارهای شبکه شناسایی می‌شوند سپس حول هر رهبر جوامع استخراج می‌شوند)، با این تفاوت که در روش پیشنهاد شده مجموعه ای از کاربران مشابه از نظر عملکرد در شبکه به عنوان رهبران یک جامعه شناسایی می‌شوند در حالی که در دو روش مذکور رهبران بر اساس ساختار گرافی شبکه شناسایی می‌شوند (هر جامعه تنها یک رهبر خواهد داشت) سپس حول این رهبران جوامع استخراج می‌شوند.

نمودار میله­ای دو بعدی شکل 10 میانگین تعداد افراد درون جوامع در روش‌های مختلف را روی مجموعه داده فلیکر نشان می‌دهد. میله هشتم میانگین تعداد افراد درون جامعه در گروه بندی ایده آل (Ground Truth) است (همان طور که در بخش معرفی این مجموعه داده گفته شد، این مجموعه داده شامل اطلاعات گروه بندی کاربران (جامعه) نیز می‌باشد. در این گروه بندی 201 گروه مجزا مشخص شده است که به طور میانگین در هر گروه 3688 کاربر عضو می‌باشد).

 

 

شکل 10) میانگین تعداد افراد درون جوامع در روش‌های مختلف کشف جامعه روی مجموعه داده فلیکر

 

همان طور که در شکل 10 مشخص است هر چه مقدار α در روش پیشنهادی بیشتر شده است، میانگین تعداد افراد درون جامعه نیز افزایش می‌یابد.

 

شکل 11) میانگین معیار F-measure در روش‌های مختلف کشف جامعه روی مجموعه داده فلیکر

 

خلاصه‌ی نتایج روی مجموعه داده فلیکر (شکل 11)، نشان می‌دهد، روش پیشنهادی نسبت به دیگر روش‌ها از انعطاف پذیری بیشتری برخوردار است، چرا که با مقادیر مختلف حد آستانه α، مقادیر متفاوتی برای سه معیار دقت، فراخوانی و معیار F بدست آمده است. در اجرای روش پیشنهادی با مقدار 1=α، دقت شناسایی جوامع بیشتر از اجرای روش پیشنهادی با دیگر مقادیر برای α بوده است، اما در این صورت تعداد افراد درون جوامع کمتر از 2=α و 3=α خواهد بود. شکل 10 و شکل 11 به خوبی نشان می‌دهد که  مقادیر دقت و فراخوانی رابطه مستقیم با میانگین تعداد افراد درون جوامع خواهد داشت. هر چه تعداد افراد درون جامعه افزایش یابد، مقدار α افزایش می‌یابد؛ که اگر مقدار دقت کاهش چشم گیری نداشته باشد؛ متعاقباً مقدار معیار F نیز افزایش می‌یابد. همان طور که مشاهده می‌کنید، اجرای روش پیشنهادی روی این مجموعه داده، در مقدار معیار F، نسبت به دیگر روش‌ها (جز یک روش)، به مراتب بهتر بوده است.

در ادامه همین مقایسه روی مجموعه داده بلاگ کاتالوگ اجرا شده است. همان طور که در بخش معرفی این مجموعه داده گفته شد، این مجموعه داده نیز شامل اطلاعات گروه بندی کاربران می‌باشد. در این گروه بندی، 319 گروه مجزا مشخص شده است که به طور میانگین در هر گروه 842 کاربر عضو می‌باشد (البته گروه‌هایی که حداقل بیش از 10 کاربر دارند)

 

 

شکل 12) میانگین تعداد افراد درون جوامع در روش‌های مختلف کشف جامعه روی مجموعه داده بلاگ کاتالوگ

 

 

 

شکل 13) میانگین معیار F-measure در روش‌های مختلف کشف جامعه روی مجموعه داده بلاگ کاتالوگ

 

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

به طور کلی می‌توان گفت که روش پیشنهادی با توجه به پارامتر های ورودی نتایج مختلفی روی مجموعه داده‌ها خواهد داشت، با این حال با ارائه نتایج روی دو مجموعه داده نشان دادیم که روش پیشنهادی علاوه بر انعطاف پذیری (تنظیم پارامترها با توجه به نیاز در کاربردها)، به طور نسبی کیفیت جوامع (معیار F شامل دقت و فراخوانی) را نیز افزایش می‌دهد.

5-     مقایسه پیچیدگی زمانی روش پیشنهادی

در این بخش پیچیدگی زمانی روش پیشنهادی و تعدادی از روش­های دیگر، محاسبه گردیده است. در جدول 1 نمادهای مورد استفاده لیست شده­اند.

جدول 1: نمادهای مورد استفاده

 

 

 

 

در جدول 2 نتایج حاصل از محاسبه پیچیدگی زمانی و سایر پارامترهای مقایسه نشان داده شده است. با توجه به نتایج می­توان دریافت که روش پیشنهادی پیچیدگی زمانی بالایی نسبت به دیگر روش ها دارد چرا که در این روش علاوه بر ساختار گراف از محتویات(عملیات کاربران) نیز استفاده می شود تا دقت جوامع کشف شده افزایش یابد. به عنوان کارهای آینده می توان با استفاده از هرس نمودن گره­ها و الگوریتم های مختلف کاوش الگوی تکرار شونده پیچیدگی زمانی و زمان اجرایی این روش را بهینه نمود.

جدول 2: مقایسه پیچیدگی زمانی

 

 

 

 

 

 

 

6-     نتیجه­گیری

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

همه روش‌های کشف جوامع دارای مزایا و معایب خاص خود هستند. از مزایا روش پیشنهادی می‌توان به بهبود دقت و کیفیت نسبی جوامع، کشف رهبر و جامعه، تنظیم پارامترها به منظور کشف جوامع مناسب در کاربردهای خاص، امکان تشخیص همپوشانی و گره­های Outlier و رویکردی نو در کشف جامعه اشاره نمود. همچنین روش پیشنهادی با برخی چالش‌ها و معایب مواجه می‌باشد از جمله پیچیدگی زمانی (به دلیل استفاده از الگوریتم‌های کاوش الگوی تکرار شونده) و مشکل تعیین پارامترها (روش وابسته به پارامتر) اشاره کرد. با این حال امید است که این روش راهی نو در روش‌های کشف جامعه مبتنی بر ساختار-محتوا باشد.

 از کارهای آتی می­توان به استفاده از الگوریتم‌های نگهداری الگوی تکرار شونده به جای الگوریتم‌های کاوش الگوی تکرار شونده از جمله الگوریتم‌های CAN و CAT [35] که می‌تواند جایگزین مناسبی برای الگوریتم‌هایی همچون Apriori، Fp-Growth در مجموعه داده­های پویا (برخط) باشد، اشاره کرد، این گام باعث می‌شود روش پیشنهاد شده حداقل در مورد کشف رهبران در مقابل داده­های افزایشی انعطاف پذیر گردد. همچنین ممکن است با جایگزین نمودن یک روش رای گیری مناسب‌تر در مرحله چهارم، کیفیت نتایج را بهبود بخشید. به منظور کاهش پیچیدگی زمانی نیز می­توان از روش­های موازی سازی استفاده نمود.

---

[1]Facebook

[2]Flickr

[3]Tweeter

[4] Amit Goyal

[5] Confidence

[6] Genuineness

[7] Muhaimenul Adnan

[8] Dot-Product

[9] Rushed Kanawati

[10] Reihaneh Rabbany Khorasgani

[11] Dongyuan Lu

[12] favor volume

[13] Favor Coverage

[14] Favor timeliness

[15] Maximal Pattern

[16] Homogeneous group

[17] Minimum Support

[18] http://del.icio.us/

[19]  http://GoodReads.com

[20]  LastFm.com

[21] Login

[22] Logout

[23] Precision

[24] Recall

[25] Blogcatalog

[26] http://dmml.asu.edu/users/xufei/datasets.html

[27] www.flicker.com

[28] Ludicorp

[29] http://dmml.asu.edu/users/xufei/datasets.html

مراجع

[1]        C. Charu and R. Aggarwal, " Social Network Data Analytic," Springer Science+Business Media, 2011.

[2]        S. Wasserman and K. Faust, "Social Network Analysis in the Social and Behavioral Sciences," Social Network Analysis: Methods and Applications, 1994.

[3]        M. Coscia, F. Giannott, and D. Pedreschi, "REVIEW A Classification for Community Discovery Methods in Complex Networks," Published online in Wiley Online Library, 2011.

[4]        A. E. Mislove, "Online Social Networks: Measurement, Analysis, and Applications to Distributed Information System," Houston, Texa, 2009.

[5]        M. Sachan, D. Contractor, A. Faruquie, and L. Venkata, "Using Content and Interactions for Discovering Communities in Social Networks," presented at the International World Wide Web Conference Committee, 2012.

[6]        D. Ganley and C. Lampe, "The ties that bind: social network principles in online communities," Decision Support Systems vol. 47, pp. 266-274, 2009.

[7]        M. Muhaimenul Adnan, R. Alhaji, and J. Rokne, " Identifying Social Communities by Frequent Pattern Mining," presented at the 13th International Conference Information Visualisation, 2009.

[8]        A. Goyal, B. Francesco, and L. Laks V. S, "Discovering Leaders from Community Actions," presented at the CIKM, 2008.

[9]        H. Zhuge, "Communities and Emerging Semantics in Semantic Link Network," IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2009.

[10]      R. Khorasgani, J. Chen, and O. R. Zaïane, "Top Leaders Community Detection in Information Network," ACM Transactions on Knowledge Discovery from Data, 2010.

[11]      R. Kanawati, " Leaders Identification For Community Detection in Complex Network," presented at the IEEE International Conference on Social Computing, 2011.

[12]      D. Lu, Q. Li, and S. S. Liao, "A graph-based action network framework to identify prestigious members through member's prestige evolution," Elsevier, 2011.

[13]      N. Pathak, C. DeLong, A. Banerjee, and K. Erickson, "Social topics models for community extraction," in 2nd SNA-KDD Workshop, 2008.

[14]      D. Zhou, E. Manavoglu, L. Li, C. L. Giles, and H. Zha, " Probabilistic models for discovering e-communities," in International Conference on World Wide Web, 2006.

[15]      G. J. Qi, C. C. Aggarwal, and T. Thomas Huang, "Community Detection with Edge Content in Social Media Networks," presented at the 28th International Conference on Data Engineering (ICDE), 2012.

[16]      M. Franz, T. Ward, J. S. McCarley, and W. J. Zhu, "Unsupervised and supervised clustering for topic tracking," presented at the ACM SIGIR Conference, 2001.

[17]      A. Clauset, M. E. J. Newman, and Moore.C, "Finding community structure in very large networks," In Phys. Rev. E 70, 066111, 2004.

[18]      R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, "Trawling the web for emerging cyber-communities," presented at the WWW, 1999.

[19]      J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, "Statistical properties of community structure in large social and information networks," presented at the WWW, 2008.

[20]      V. Satulouri and S. Parthasarathy, "Scalable graph clustering using stochastic flows: Applications to community discovery," presented at the KDD Conference, 2009.

[21]      T. Eliassi-Rad, K. Henderson, S. Papadimitriou, and C. Faloutsos, "A hybrid community discovery framework for complex networks,," presented at the SIAM Conference on Data Mining, 2010.

[22]      J. M. Hofman and C. H. Wiggins, "A bayesian approach to network modularity," Phys Rev Lett 100, 2008.

[23]      A. Clauset, C. Moore, and M. E. J. Newman, "Hierarchical structure and the prediction of missing links in networks.," Nature vol. 453, pp. 98-101, 2008.

[24]      S. Borgatti, "Identifying sets of key players in a network," Comput Math Organ Theory, vol. 12, pp. 21-34, 2006.

[25]      X. Zhang and D. Dong, "Ways of Identifying the Opinion Leaders in Virtual Communities," International Journal of Business and Management, vol. 3, 2008.

[26]      D. Arroyo, "Discovering Sets of Key Players in Social Networks," in Computational Social Networks Analysis, Trends, Tools and Research Advances, ed Computer and Communication Networks Series.: Springer, 2010.

[27]      L. C. Freeman, Centrality in Social Networks Conceptual Clarification. Printed in the Netherlands: Elsevier Sequoia S.A., Lausanne, 1978.

[28]      W. Jiinlong, X. Conglfu, C. Weidong, and P. Yunhe, "Survey of the Study on Frequent Pattern Mining in Data," presented at the IEEE International Conference on Systems, 2004.

[29]      R. Agrawal, "Fast algorithm for mining association rules in large databases," in 20th International Conference on Very Large Data Bases,VLDB, Santiago, Chile, 1994, pp. 487-499.

[30]      D. Lu, Q. Li, and S. S. Liao, "A graph-based action network framework to identify prestigious members through member's prestige evolution," DECISION SUPPORT SYSTEMS, 2011.

[31]      A. Goyal, B. Francesco, and L. Laks V. S, "Discovering Leaders from Community Actions," in CIKM, 2008.

[32]      H. I. Witten and E. Frank, Data Mining:Practical Machine Learning Tools and Techniques (second edition) 2005.

[33]      A. Clauset, M. E. J. Newman, and C. Moore, "Finding community structure in very large networks," in Phys. Rev., 2004.

[34]      M. Newman and M. Girvan, "Community structure in social and biological networks," Proceedings of the National Academy of Sciences, 2002.

[35]      M. Feng, J. Li, G. Dong, and L. Wong, "Maintenance of Frequent Patterns," Data Mining and Knowledge Discovery, 2009.