تشخیص افراد خبره در شبکه های اجتماعی براساس خوشه بندی اشیاء اجتماعی و ماژولاریتی

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

مقاله 5، دوره 9، بهار و تابستان 1395، شهریور 1395، صفحه 66-79   

نویسندگان

سمانه حسن زاده^{* 1}؛ ملیحه ابراهیمی نژاد²؛ مهرداد جلالی³

¹دپارتمان مهندسی کامپیوتر فناوری اطلاعات، موسسه آموزش عالی اقبال لاهوری، مشهد،ایران

²دپارتمان مهندسی کامپیوتر، دانشکده 17 شهریور کرج، دانشگاه فنی و حرفه ای استان البرز، ایران

³دپارتمان مهندسی کامپیوتر، دانشگاه آزاد اسلامی ، دانشکده فنی و مهندسی، مشهد، ایران

چکیده

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

کلیدواژه‌ها

پیدا کردن متخصص؛ استخراج جوامع؛ الگوریتم EWKM؛ ماژولاریتی؛ الگوریتم Topsis

اصل مقاله

با رایج تر شدن شبکه های اجتماعی نظیر فیس بوک  تجزیه و تحلیل داده های شبکه به یکی از موضوعات حائز اهمیت در حوزه داده کاوی تبدیل شده است. تجزیه و تحلیل شبکه های اجتماعی علاوه بر درک عمیق ساختار شبکه، باعث کشف ارتباطاتی مانند روابط دوستی، تجاری یا علایق مشترک میان افراد خواهد شد که منجر به ایجاد گروه های منسجم در این شبکه ها می شود. با در اختیار داشتن چنین گروه هایی، دسترسی به افراد متخصص در هر زمینه نیز امکان پذیر خواهد بود[1], [2].

 

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

در این تحقیق، برای استخراج متخصص ترین افراد در هر جامعه، ابتدا جوامع را از دو دیدگاه معنایی[3–5] و ساختاری [6][7] مشخص می کنیم و سپس با استفاده از الگوریتم [8]Topsis، براساس معیارهای درجه، قدرت و بینابینی به هر کاربر در شبکه رتبه ای اختصاص می دهیم و در نهایت کاربران با بالاترین رتبه ها را به عنوان متخصصین در آن زمینه معرفی می کنیم. ساختار مقاله در ادامه به این شرح است: در بخش 2 مروری بر کارهای محققان در این حوزه داریم. در بخش 3 روش ماژولاریتی توضیح داده شده است. در بخش 4 الگوریتم پیشنهادی را معرفی می‌کنیم. نتایج پیاده سازی روش پیشنهادی بر روی شبکه های اجتماعی واقعی در بخش 5 بیان می‌شود. بخش 6 شامل نتیجه گیری و کارهای آینده می باشد.

 

2- مروری بر کارهای گذشته

2-1- روش‌های استخراج جامعه

بطور کلی، کارهای انجام شده در زمینه تشخیص جوامع را در دو صورت کلی می توان دسته بندی کرد، دسته اول تنها بر ساختار توپولوژی یا الگوهای ارتباطی تمرکز دارند بدون اینکه به موضوعات اشتراکی بین اعضاء توجه کنند و دسته دوم به موضوعات اشتراکی بین اعضاء توجه می کنند. در هر زمینه کارهای بسیاری انجام شده است. البته گروهی از محققین ترکیبی از این دو روش را استفاده کرده اند که مسلما نتایج حاصل از آن دقت بیشتری نسبت به دو روش ابتدا دارد. دسته اول را نیز  می توان در دو بخش روش های مبتنی بر بهینه سازی و روش های اکتشافی تقسیم کرد[9][10]. روش های مبتنی بر بهینه سازی شامل روش های طیفی و روش های مبتنی بر جستجوی محلی است. هدف روش های طیفی به حداقل رساندن تابع برش است. Ruan و همکارش در سال 2007 برای استخراج جوامع، یک الگوریتم طیفی پیشنهاد داده اند[10], [11]. در حالی که هدف روش های مبتنی بر جستجوی محلی، بهینه سازی تابع هدف مانند ماژولاریتی است. تابع ماژولاریتی، برای ارزیابی صلاحیت یک بخش خاصی از شبکه استفاده می شود. در اکثر کارهای انجام شده معمولا از ماژولاریتی برای ارزیابی صحت کارشان استفاده می کنند[12], [13]. روش های اکتشافی اغلب، الگوریتم های خوشه بندی گراف را مبتنی بر مفروضات حسی طراحی می کنند . Jin و همکارانش در سال 2011، از الگوریتم نیومن[13], [14] برای کشف جوامع استفاده کردند، مزیت کار این محققین استفاده از چندین منبع ناهمگون بود[13]. روش های خوشه بندی گراف نیز روی ساختار توپولوژی تمرکز دارند[15], [16]. Yunhong و همکارانش در سال 2012 از یک روش معنایی در تحلیل شبکه های اجتماعی استفاده کردند و بر این اساس نیز خبره ترین شخص را در شبکه معرفی کردند[17].

2-2- روش های تشخیص افراد خبره

پیدا کردن متخصصین در یک زمینه خاص اغلب مورد توجه افراد در بسیاری از حوزه های مختلف مانند دانشگاه و صنعت می باشد. کارهای بسیاری در این زمینه انجام شده است برخی از این روش ها در ادامه توضیح داده شده است.

 

2-2-1- مدل های  زبانی آماری

مدل های زبانی،  معمولا توجه بسیاری از متخصصین را به دلیل اینکه مبتنی بر روش های آماری است  به خود جلب کرده است. در این مدل عمدتا دو روش زیر مورد استفاده قرار می گیرد[18], [19][20]:

• مدل زبانی ابتدایی
• مدل زبانی وزن دار

در روش مدل زبانی ابتدایی، ایده اصلی آن تخمین زدن یک مدل برای هر موضوع است و سپس این موضوعات را براساس Likelihood رتبه بندی می کنند. چندین روش مختلف برای محاسبه Likelihood ممکن است استفاده شود. در[21] گروهی از محققین از یک موضوع معین با استفاده از یک مدل احتمالی برای تشخیص یک متخصص استفاده کردند که به صورت  بیان شد.

 

(1)             

 

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

                  (2)                      

(3)             

 

برای هر متخصص مجموعه ای از مستندات وجود دارد که با ، نشان داده است.

مدل زبانی ابتدایی که در بالا بیان شد تنها رابطه بین یک پرس و جو و یک سند را در نظر می گیرد ولی اعتبار و نفوذ سند را در نظر نمی گیرد. در روش مدل زبانی وزن دار، اعتبار موضوعات را نیز در نظر می گیرد. به عنوان مثال اگر دو سند  A و B داشته باشیم که سند A مربوط به نویسنده a و سند B مربوط به نویسنده b است و هر دو سند محتوای مشابهی دارند یعنی . اما اعتبار این دو سند متفاوت است . اما در این روش این مسئله را با دادن وزنی به هر سند در نظر می گیرد.

(4)              

2-2-2- مدل های پیشرفته

در  مدل های پیشرفته معمولا از یکی از دو روش زیر استفاده می شود[18], [19]:

• مدل متخصص- موضوع
• مدل ترکیبی

در مدل متخصص- موضوع،  هر کاندید به صورت یک مجموع وزنی از چندین موضوع نشان داده شده است ( زیرا هر متخصص ممکن است دانشی از چندین موضوع داشته باشد). بنابراین پرس و جوهای متفاوت از موضوعات مختلف ممکن است برای یک کاندید تولید شود. مدل متخصص- موضوع در شکل (1) نشان داده شده است[18].

 

 

شکل 1  نمایش گرافیکی از مدل متخصص-موضوع[18]

که در آن کاندید  و پرس و جوی ، از موضوع  مستقل هستند.

(5)

که در آن ، احتمال اینکه موضوع  مربوط به کاندید  است را نشان می دهد و ، احتمال اینکه پرس و جو  مربوط به موضوع  است را نشان می دهد. در شکل (1) ،M تعداد کاندید،N تعداد موضوعات تولید شده بوسیله کاندید  و  تعداد کلمات یک پرس و جو می باشد. در مدل ترکیبی، برای بهبود امتیاز بندی از یک پرس و جو مشخص در یک کاندید، از یک مدل ترکیبی برای جمع کردن امتیازاتی از مدل زبان و مدل متخصص-موضوع استفاده می شود.

 (6)    

نتایج تحقیقات انجام شده قبلی نشان می دهد که مدل های ترکیبی دقت بیشتری دارند[18].

 

2-2-3- سایر روش ها

Jin و همکارانش، از اندازه گیری درجه و بینابینی برای پیدا کردن متخصصان هر گروه استفاده کردند. یک عضو با درجه بالا یعنی ارتباطات محکم و بسیاری با متخصصان دیگر در گروه دارد و یک عضو با بینابینی بالا یعنی نقش مهمی  برای ارتباط برقرار کردن با متخصصان دیگر در گروه دارد و یک عضو با درجه و بینابینی بالا یعنی شخص خیلی مهمی در گروه خواهد بود[13][22].

Moreira و همکارش، در روش حسگر چندگانه، برای یافتن متخصص ترین افراد در هر موضوع، هنگامی که کاربر موضوع مورد علاقه خود را بیان می کند در مرحله ابتدا، سیستم همه نویسندگانی که این موضوع، در چکیده و عنوان مقالات آن ها موجود است را بازیابی می کند و سپس با استفاده از سه سنسور، اطلاعات مورد نظر را از آن ها استخراج می کند. این سه سنسور عبارتند از: سنسور متنی، که وظیفه آن محاسبه تعداد تکرار موضوع در مقالات آن نویسنده است و سنسور پروفایل، که تعداد سندهای منتشر شده از آن نویسنده را محاسبه می کند و سنسور Citation، تعداد نویسندگان همکار را محاسبه می کند. براساس امتیازات کسب شده از هر سنسور متخصصین در آن موضوع معرفی می شوند اما گاهی اوقات ممکن است نتایج مختلفی از سه سنسور حاصل شود برای رفع این مشکل از تئوری دمپستر- شافر همراه با آنتروپی شانون استفاده شده است تا لیست نهایی از متخصصین، دقیق تر و قابل اعتمادتر باشد[23].

 

3- روش حداکثر ماژولاریتی

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

   (7)

 

که در آن:

• ، رئوس در این خوشه هستند.
• ، تعداد ارتیاطات بین رئوس را نشان می دهد.
•  
• ، جامعه ای که راس ، به آن اختصاص داده می شود.
• ، جامعه  را نشان می دهد.
• ، مساوی یک است اگر  باشد در غیر این صورت مساوی صفر است.

در روش سنتی ماژولاریتی، در ابتدا هر راس را به عنوان یک جامعه در نظر می گیرد و تغییرات ، محاسبه می شود و سپس بزرگترین آن ها انتخاب می شود و ادغام جوامع انجام می شود. سه ساختار داده برای این منظور نگهداری می شود:1) ماتریس پراکنده  ، که حاوی جوامع   با حداقل یک همکاری می باشد. 2) ماتریس H، که شامل بزرگترین عنصر از هر سطر ماتریس  ، همراه با برچسب های جوامع  می باشد .3) آرایه  . مقدار دهی اولیه برای  و  به صورت زیر است:

(8)

 

                            (9)

قوانین به روز رسانی برای ماتریس ، به صورت زیر است:

     (10)

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

چارچوب روش پیشنهادی در شکل (4) نمایش داده شده است. این چارچوب برای تشخیص متخصص ترین افراد در هر جامعه، شامل 3 بخش کلی زیر می باشد:

1-  آماده سازی مجموعه داده : هدف این بخش، استخراج داده های مورد نیاز از صفحات وب و پاکسازی داده ها می باشد.

2-   

لیست

سیاه

 

خزنده صفحه وب

 

 

 

استخراج  اشیاء اجتماعی

 

DBLP

 

استخراج  روابط بین کاربران و اشیاء اجتماعی

 

خوشه بندی  اشیاء اجتماعی

 

دسته بندی اعضاء درگیر در  اشیاء اجتماعی

 

استخراج  جوامع برچسب دار

 

استخراج  متخصص ترین افراد در هر زمینه

 

مدل سازی داده های شبکه اجتماعی

استخراج جوامع : هدف این بخش، دسته بندی اشیاء اجتماعی و سپس دسته بندی اعضاء درگیر در آن ها می باشد.

3-  استخراج متخصص ترین افراد در هر زمینه : در این بخش، افراد براساس ویژگی هایشان در هر زمینه موضوعی رتبه بندی می شوند و سپس افراد با بالاترین رتبه به عنوان متخصص ترین افراد معرفی می شوند.

 

 

 

 

 

 

شکل 4 چارچوب روش پیشنهادی

 

 

4-1- آماده سازی مجموعه داده 

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

             (11)                             

که در آن:

، مجموعه ای از کاربران درگیر، در فعالیتهای اجتماعی هستند و ، مجموعه ای از اشیاء اجتماعی و ، مجموعه ای از لبه هاست که ارتباطاتی که در در  موجود است را نشان می دهد.

                (12)         

4-2- استخراج جوامع برچسب دار

4-2-1- استخراج اشیاء اجتماعی

اشیاء اجتماعی در واقع موضوعات به اشتراک گذاشته

بین افراد می باشد. در این مرحله، در ابتدا محتوای اشیاء اجتماعی به صورت جفت های ، نمایش داده می شود که در آن ، کلمه و ، اندازه  است. برای نشان دادن هر شی از مدل فضا بردار استفاده می شود[3].

(13)  

که در آن

• ، تعداد کل اشیاء اجتماعی است.
• ، تعداد کل کلمات موجود بعد از پاک سازی است.

مقدار ، با توجه به الگوریتم ، محاسبه می شود. به مجموع کل کلمات منحصر به فرد در کل اشیاء اجتماعی بعد گفته می شود. در نهایت، همه اشیاء اجتماعی بوسیله ماتریس ، مشخص می شود که  تعداد اشیاء اجتماعی و  تعداد کل ابعاد می باشد.

4-2-2- خوشه بندی اشیاء اجتماعی

براساس محتوای اشیاء اجتماعی به دست آمده از مرحله قبل، با استفاده از الگوریتم EWKM[24]، اشیاء اجتماعی در خوشه هایی دسته بندی می شوند. این الگوریتم نسخه ای از الگوریتم[25], [26] K-means است با این تفاوت که علاوه بر ایجاد خوشه ها، وزنی را به هر بعد اختصاص می دهد. الگوریتم1، روند این الگوریتم را نمایش می دهد.

الگوریتم 1: الگوریتم EWKM : برای خوشه بندی اشیاء اجتماعی براساس محتوای اشیاء[3], [24]

ورودی: ماتریس  و تعداد خوشه ها K=7. 

خروجی: خوشه هایی از اشیاء اجتماعی و وزن ابعاد برای هر خوشه.

1. k  نقطه به عنوان مراکز اولیه خوشه ها به طور تصادفی انتخاب می شود و در ابتدا ماتریس وزن ابعاد با مقدار  مقدار دهی می شود.
2. گام های 3 تا 5، تا زمانی که مراکز خوشه ها تغییری نمی کنند و یا تا رسیدن به حداکثر تکرار و یا تا رسیدن به حداقل مقدار تابع هدف و یا تا رسیدن به حداکثر وزن اجرا می شوند.
3. نقاط را به هر یک  از k خوشه به نحوی اختصاص می یابند که فاصله نقاط تا مراکز  خوشه ها  حداقل شود.
4. مراکز خوشه ها با استفاده از نقاطی که به هر خوشه اختصاص یافته اند به روز آوری می شوند.
5. ماتریس وزن ابعاد به روز آوری می شود.
6. پایان.

 

 

 علاوه بر خوشه ها، وزن تمام ابعاد در خوشه ها  مشخص می شود و کلماتی که دارای بیشترین وزن هستند  برای برچسب گذاری خوشه های استخراج شده، انتخاب می شوند.

4-2-3- دسته بندی اعضاء درگیر در اشیاء اجتماعی

در این بخش با توجه به خوشه های اشیاء اجتماعی که از مرحله ی خوشه بندی اشیاء اجتماعی بدست آوردیم و همچنین با توجه به ارتباط بین کاربران که در بخش مدل سازی مشخص کردیم، کاربران در گیر  را در خوشه هایی دسته بندی می کنیم. هر خوشه یک زیر گراف بدون جهت از گراف اصلی است که توسط یک ماتریس نمایش داده می شود. سطر و ستون های این ماتریس مشخص کننده کاربرانی است که با هم در آن خوشه در ارتباط هستند و محتوای هر سلول این ماتریس، نشان دهنده تعداد همکاری های بین دو کاربر درآن  خوشه می باشد.

 

شکل 5  تخصیص کاربران به خوشه ها براساس خوشه بندی اشیاء اجتماعی

در شکل (5)، نحوه ی تخصیص کاربران به خوشه ها نمایش داده شده است.

4-2-4- خوشه بندی کاربران

هدف از این بخش، به دست آوردن جوامع از طریق تقسیم بندی هر خوشه به ناحیه هایی براساس میزان ارتباط آن هاست. کاربران در هر خوشه اغلب با قدرت های متفاوتی با هم در ارتباط هستند. کاربرانی که ارتباط بیشتری با هم دارند، باعث به وجود آمدن اتصال قوی تری بین آن ها خواهد شد، همچنین اتصالات ضعیف تر مربوط به کاربرانی است که ارتباطات کمتری با یکدیگر دارند. در این تحقیق از روش حداکثر ماژولاریتی، جهت تجزیه و تحلیل ساختار گراف ارتباطی و مشخص کردن جوامع در هر خوشه استفاده شده است. ساختار این جوامع طوری است که گره های داخل هر جامعه دارای اتصال قوی تری نسبت به اتصال گره های خارج از آن جامعه می باشند.الگوریتم 2، الگوریتم این روش ، که برای هر خوشه مورد استفاده قرار گرفته است در زیر توصیف شده است.

 

 

 

 

 

 

 

 

 

 

 

 

الگوریتم 2 : الگوریتم حداکثر ماژولاریتی[3]

ورودی: P خوشه p=1,2,3,….

خروجی: جوامع برچسب گذاری شده

1. مقادیر اولیه  و  بر طبق فرمول8 و 9 محاسبه می شود.
2. گام های 3 تا 7 ، تا زمانی که تعداد جوامع جاری بزرگتر از یک است اجرا می شود.
3. برای هر ردیف از ماتریس ، گام 4 اجرا می شود.
4. H با بزرگترین عناصر ایجاد می شود.
5. بزرگترین ، از H انتخاب می شود.
6. جوامع مشابه با هم یکی می شوند.
7. ماتریس ، به روز رسانی می شود.
8. پایان

 

 

3-4 پیدا کردن متخصص ترین افراد

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

در این مرحله جوامعی که دارای یک موضوع هستند استخراج می شوند و سپس در هر جامعه، برای تمامی نودها مقادیر بینابینی، درجه و قدرت محاسبه می شود و با توجه به این سه ویژگی برای تعیین متخصص ترین افراد در هر جامعه، از الگوریتم [26]Topsis استفاده شده است. در نهایت، الگوریتم 3، روش پیشنهادی برای کشف متخصص ترین افراد در شبکه های همکاری را نمایش می دهد.

الگوریتم 3: الگوریتم روش پیشنهادی

ورودی: مجموعه داده شبکه اجتماعی

خروجی: متخصص ترین افراد در هر جامعه برچسب گذاری شده ، جوامع برچسب گذاری شده

1. خزنده صفحه وب، برای استخراج اطلاعات مورد نظر از صفحات وب اجرا می شود.
2. عملیات پاک سازی بر روی مجموعه داده ورودی اعمال می شود.
3. داده های شبکه اجتماعی مدل سازی می شود.
4. ماتریس اشیاء اجتماعی ایجاد می شود.
5. الگوریتم EWKM، برای خوشه بندی اشیاء اجتماعی اجرا می شود.
6. کاربران براساس خوشه بندی اشیاء اجتماعی از مرحله 5 و روابط بین کاربران از مرحله 3، در خوشه های مجزایی قرار می گیرند.
7. الگوریتمModularity، برای هر خوشه از مرحله 6 اجرا می شود.
8. جوامع با برچسب برای تعیین متخصص ترین افراد از لیست جوامع انتخاب می شود.
9. الگوریتم Topsis برای تعیین متخصص ترین افراد در هر گروه اجرا می شود.
10. پایان

 

- پیچیدگی زمانی الگوریتم پیشنهادی

پیجیدگی زمانی الگوریتم پیشنهادی به الگوریتم خزنده صفحه وب، EWKM، الگوریتم ماژولاریتی و الگوریتم Topsis وابسته است. پیچیدگی زمانی هر یک از این الگوریتم ها در جدول زیر بیان شده است:

جدول 1  پیچیدگی زمانی الگوریتم های استفاده شده  در روش پیشنهادی

نام الگوریتم	پیچیدگی زمانی	توضیحات
خزنده صفحه وب		: تعداد اشیاء اجتماعی
EWKM		: تعداد اشیاء اجتماعی، : تعداد کلمات کلیدی در همه اشیاء اجتماعی، : تعداد خوشه های در نظر گرفته برای خوشه بندی اشیاء اجتماعی، : تعداد تکرار
الگوریتم Modularity		: تعداد خوشه های در نظر گرفته برای خوشه بندی اشیاء اجتماعی ، : تعداد کاربران در جامعه  ام.
Topsis		، تعداد ویژگی های در نظر گرفته برای هر کاربر، : تعداد کاربران در جامعه  ام.

 

پیچیدگی زمانی الگوریتم خزنده صفحه وب و Topsis نسبت به دیگر الگوریتم ها قابل چشم پوشی است. بنابراین پیچیدگی زمانی الگوریتم پیشنهادی برای تشخیص متخصص ترین افراد در هر جامعه برابر  می باشد.

5-ارزیابی روش پیشنهادی

5-1- مجموعه داده مورد آزمایش

در ابتدا از مجموعه داده DBLP ، به عنوان مجموعه داده پایه استفاده شده است.[28]DBLP، یک وب سایت مرجع کامپیوتر می باشد که توسط دانشگاه تریر درکشور آلمان ایجاد شده است. DBLP یک پایگاه داده مرجع برای رشته کامپیوتر می باشد و از حدود سال1980 وجود دارد. این پایگاه داده تا تاریخ اکتبر 2013 بیش از 2.3 میلیون مقاله رشته کامپیوتر را لیست کرده است. البته این پایگاه داده معمولا مقالات چاپ شده در کنفرانس ها و مجلات معتبر خاصی را در نظر می گیرد. مثلا ممکن است شخصی 30 مقاله داشته باشد ولی فقط 10 مقاله از آن شخص در این پایگاه داده قرار گرفته باشد. به هر حال این پایگاه داده می تواند مرجع مناسب و معتبری برای تشخیص اعتبار کنفرانس ها، مجلات و یا حتی سطح علمی افراد باشد. این مجموعه داده حاوی Article, Inproceedings, Proceedings,Bookو ookست حاوی هفته بروز رسانی می شودست. این  و Thesis می باشد. در این مقاله تنها مجموعه ی Articleها در نظر گرفته شده است. اطلاعات موجود در این مجموعه داده عنوان مقاله، نام نویسندگان، نام مجله، سال انتشار و آدرس مقاله می باشد. با توجه به اطلاعات موجود در مجموعه داده و نداشتن چکیده مقالات و کلمات کلیدی،  با استفاده  از  بخش خزنده  اطلاعات مورد نظر استخراج شده و در پایگاه داده، قرار داده شده است. در این مجموعه داده، مقالات، اشیاء اجتماعی و نویسندگان کاربران درگیر در اشیاء اجتماعی هستند.

- معیار ارزیابی

برای بررسی صحت و کارایی، از معیار بازیابی اطلاعات P@n استفاده شده است[23].

P@n: یکی از معیارهای ارزیابی است که دقت را در n رتبه اول ارزیابی می کند و به صورت زیر محاسبه می گردد.

                  (14)

5-3- نتایج آزمایش

پس از استخراج داده های مورد نظر و آماده سازی اشیاء اجتماعی در مرحله خوشه بندی اشیاء اجتماعی وزن کلمات کلیدی محاسبه شده است و در نهایت همه اشیاء اجتماعی بوسیله ماتریس ، مشخص می شوند که  تعداد اشیاء اجتماعی و  تعداد کل کلمات کلیدی است. این ماتریس، به  الگوریتم [24]EWKM ارسال می شود مقدار K=7، در نظر گرفته شده است[3]. بخشی از نتایج در جداول )2( و )3( بیان شده است.

جدول2 برچسب های تخصیص داده شده به  خوشه 4 پس از اجرای الگوریتم EWKM

برچسب	شماره خوشه
Semanticweb, Communication, Mine, Associative rule, vision,Face Recognition,Image,Algorithm classification,clustering, Learning	4

 

جدول(3) برچسب های اختصاص داده شده به دو جامعه نهایی مربوط به موضوع Machine vision،  را نشان می دهد.

جدول 3 برچسب های اختصاص داده شده به جوامع استخراج شده

شماره جامعه	برچسب	موضوع
1200	Face image, Face recognition, Pattern analysis, machine intelligence	Machine vision
1011	Image feature, Clustering algorithm, Image analysis, Image retrieval	Machine vision

در مرحله نهایی برای تعیین متخصص ترین افراد، جوامعی که دارای یک موضوع هستند استخراج می شوند و سپس در هر جامعه، با استفاده از الگوریتم Topsis، براساس معیارهای درجه، قدرت و بینابینی به هر کاربر در جامعه رتبه ای اختصاص داده شد و در پایان کاربران با بالاترین رتبه ها، به عنوان متخصصین در آن زمینه معرفی شدند.

5-4- مقایسه و ارزیابی

برای ارزیابی صحت تحقیق انجام شده، نیاز به مجموعه ای درست از متخصصین در هر موضوع داریم. مجموعه داده استفاده شده شامل 13 موضوع از دامنه علوم کامپیوتر است که بوسیله افراد حاضر در کنفرانس های مهم ساخته شده است[23]. جدول (4)، یک Benchmark ازتعداد متخصصان مربوط به هر موضوع را نشان می دهد.

جدول 4 مشخصات مجموعه داده استفاده شده برای ارزیابی صحت روش پیشنهادی

تعداد نویسندگان	موضوع	تعداد نویسندگان	موضوع
41	Natural Language (NL)	46	Boosting (B)
103	Neural Networks (NN)	176	Computer Vision (CV)
47	Ontology (O)	148	Cryptography (C)
23	Planning (P)	318	DataMining (DM)
326	SemanticWeb (SW)	20	Information Extraction (IE)
85	Support VectorMachines (SVM)	30	Intelligent Agents (IA)
		34	Machine Learning

نتیجه مقایسه روش پیشنهادی با الگوریتم استفاده شده در شکل (7) آورده شده است.

 

 

شکل 7 مقایسه روش پیشنهادی  و روش حسگر چندگانه

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

6- جمع بندی و کارهای آینده

در این تحقیق به معرفی شبکه های اجتماعی، جوامع در شبکه های اجتماعی و تعیین متخصصین در هر جامعه برچسب دار پرداخته شد. در این راستا، برای استخراج جوامع از روشی استفاده شد که علاوه بر در نظر گرفتن ساختار موجود در شبکه، موضوعات به اشتراک گذاشته شده بین افراد را در نظر می گیرد، برای این منظور برای خوشه بندی اشیاء اجتماعی از الگوریتم EWKM استفاده شد این الگوریتم نسخه ای از الگوریتم K-means است با این تفاوت که علاوه بر خوشه بندی، به هر یک از بعدها وزنی اختصاص می دهد که از ابعاد با بیشترین وزن برای برچسب گذاری این خوشه ها استفاده شد، و سپس براساس این خوشه ها، کاربران درگیر در این اشیاء اجتماعی را در خوشه های مجزایی قرار دادیم به منظور دسترسی به جوامع دقیق تر یک تجزیه و تحلیل ساختاری بر روی خوشه ها با استفاده از الگوریتم ماژولاریتی انجام شد و همچنین بعدها با بیشترین وزن در گیر در این خوشه ها به عنوان برچسب جوامع در نظر گرفته شد و در نهایت برای دسترسی به متخصص ترین افراد در هر جامعه با استفاده از الگوریتم Topsis، براساس معیارهای درجه، قدرت و بینابینی به هر کاربر در شبکه رتبه ای اختصاص داده شد و در پایان کاربران با بالاترین رتبه ها، به عنوان متخصصین در آن زمینه معرفی شدند. از جمله موارد برای بهبود کیفیت در نتایج پیشنهادی می توان به موارد زیر اشاره نمود:

استفاده از بانک های اطلاعاتی مرتبط با هستی شناسی، جهت حذف کلمات هم معنی در محتوای استخراج شده از خروجی خزنده صفحه وب و عنوان مقاله.

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

استفاده از برخی اطلاعات نهفته دیگر در مجموعه داده. به عنوان مثال مدت زمان فعالیت یک نویسنده در یک موضوع می تواند به عنوان یک معیار دیگر در تعیین متخصص بودن نویسندگان استفاده شود.

نتایج حاصل از تجزیه و تحلیل شبکه های اجتماعی و تعیین جوامع و متخصصین در هر جامعه می تواند نقش مهمی را در رسیدن افراد به اهدافشان ایفا کند. با توجه به مطالب بیان شده در این مقاله می توانیم در بسیاری از برنامه های کاربردی از این روش استفاده کنیم.

 

 

 

 

 

 

 

 

مراجع

[1]   L. Tang and H. Liu, Community detection and mining in social media, vol. 2, no. 1. Morgan & Claypool Publishers, 2010, pp. 1–137.

[2]   S. Fortunato, “Community detection in graphs,” Physics Reports, vol. 486, no. 3, pp. 75–174, 2010.

[3]   Z. Zhao, S. Feng, Q. Wang, J. Z. Huang, G. J. Williams, and J. Fan, “Topic oriented community detection through social objects and link analysis in social networks,” Knowledge-Based Systems, vol. 26, pp. 164–173, Feb. 2012.

[4]   M. Steyvers and P. Smyth, “Probabilistic author-topic models for information discovery,” … discovery and data mining, no. 1990, pp. 1–10, 2004.

[5]   T. Hofmann, “Probabilistic latent semantic indexing,” Proceedings of the 22nd annual international ACM …, pp. 50–57, 1999.

[6]   S. Jarukasemratana, “Community Detection Algorithm based on Centrality and Node Distance in Scale-Free Networks,” no. May, pp. 258–262, 2013.

[7]   M. Newman, “Fast algorithm for detecting community structure in networks,” Physical review E, no. 2, pp. 1–5, 2004.

[8]   X. Zhu, F. Wang, H. Wang, C. Liang, R. Tang, X. Sun, and J. Li, “TOPSIS method for quality credit evaluation: A case of air-conditioning market in China,” Journal of Computational Science, pp. 1–7, Feb. 2013.

[9]   H. Jiawei, K. Micheline, and P. Jian, Data Mining concepts and techniques. 2012, pp. 452–454.

[10] C. C.Aggarwal, Social Network Data Analytics. 2011, pp. 1–502.

[11] J. Ruan and W. Zhang, “An Efficient Spectral Algorithm for Network Community Discovery and Its Applications to Biological and Social Networks,” Seventh IEEE International Conference on Data Mining (ICDM 2007), pp. 643–648, Oct. 2007.

[12] Y. Kim, S. Son, and H. Jeong, “LinkRank: Finding communities in directed networks,” pp. 1–9, 2009.

[13] J. H. Jin, S. C. Park, and C. U. Pyon, “Finding research trend of convergence technology based on Korean R&D network,” Expert Systems with Applications, vol. 38, no. 12, pp. 15159–15171, Nov. 2011.

[14] S. White and P. Smyth, “A Spectral Clustering Approach To Finding Communities in Graph.,” in SDM, 2005, vol. 5, pp. 76–84.

[15] Y. Zhou, H. Cheng, and J. X. Yu, “Clustering Large Attributed Graphs: An Efficient Incremental Approach,” 2010 IEEE International Conference on Data Mining, pp. 689–698, Dec. 2010.

[16] C. C. Aggarwal and H. Wang, Managing and Mining Graph Data, vol. 40. Boston, MA: Springer US, 2010.

[17] Y. Xu, X. Guo, J. Hao, J. Ma, R. Y. K. Lau, and W. Xu, “Combining social network and semantic concept analysis for personalized academic researcher recommendation,” Decision Support Systems, vol. 54, no. 1, pp. 564–573, Dec. 2012.

[18] F. Breu, S. Guggenbichler, and J. Wollmann, “A Study of Expert Finding on DBLP Bibliography Data,” Vasa, 2008.

[19] H. Deng, I. King, and M. R. Lyu, “Formal models for expert finding on DBLP bibliography data,” in Data Mining, 2008. ICDM’08. Eighth IEEE International Conference on, 2008, pp. 163–172.

[20] J. Zeng, W. K. Cheung, C. Li, and J. Liu, “Coauthor Network Topic Models with Application to Expert Finding,” 2010 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, pp. 366–373, Aug. 2010.

[21] K. Balog, L. Azzopardi, and M. De Rijke, “Formal models for expert finding in enterprise corpora,” … of the 29th annual international ACM …, pp. 43–50, 2006.

[22] G. A. Wang, J. Jiao, A. S. Abrahams, W. Fan, and Z. Zhang, “ExpertRank: A topic-aware expert finding algorithm for online knowledge communities,” Decision Support Systems, vol. 54, no. 3, pp. 1442–1451, Feb. 2013.

[23] C. Moreira and A. Wichert, “Finding Academic Experts on a MultiSensor Approach using Shannon’s Entropy,” Expert Systems with Applications, pp. 1–29, 2013.

[24] L. Jing, M. Ng, and J. Huang, “An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data,” Knowledge and Data Engineering, …, vol. 19, no. 8, pp. 1026–1041, Aug. 2007.

[25] M. El Agha and W. M. Ashour, “Efficient and Fast Initialization Algorithm for K-means Clustering,” International Journal of Intelligent Systems and Applications, vol. 4, no. 1, pp. 21–31, Feb. 2012.

[26] Z.-X. Wang and Y.-Y. Wang, “Evaluation of the provincial competitiveness of the Chinese high-tech industry using an improved TOPSIS method,” Expert Systems with Applications, vol. 41, no. 6, pp. 2824–2831, May 2014.

[27] Z. Gao and N. Jin, “Detecting community structure in complex networks based on K-means clustering and data field theory,” Control and Decision Conference, 2008. CCDC …, pp. 4411–4416, 2008.

[28] “dblp.uni-trier.de.” [Online]. Available: http://dblp.uni-trier.de/xml/. [Accessed: 13-Oct-2013].