بخشی از مقاله
چکیده
مسئله تخمین شباهت در بسیاری از علوم و زمینهها کاربرد دارد. برای مثال علوم داده کاوی، وب کاوی، خوشه بندی، موتورهای جستجو و شبکههای اجتماعی نیاز به تعریف و پیادهسازی شباهت دارند. در شبکه های اجتماعی تخمین شباهت بین کاربران یکی از مسائل مطرح در این زمینه است و کاربردهای زیادی دارد. در این تحقیق با هدف افزایش دقت در تخمین شباهت بین کاربران شبکه های اجتماعی، الگویی جدید جهت ترکیب الگوریتمهای ساختاری و غیرساختاری ارائه شده است. در بخش ارزیابی، الگوریتم های ساختاری SRank، P-Rank و SimRank توسط الگوی پیشنهادی با الگوریتم غیرساختاری 1OF ترکیب شده و بر روی بخشی از مجموعه داده شبکه اجتماعی توئیتر پیادهسازی میشوند. نتایج ارزیابی نشان دهندهی دقت بالای الگوریتم حاصل از ترکیب SRank و OF توسط الگوی پیشنهادی در تخمین شباهت بین کاربران است.
-1 مقدمه
امروزه شبکههای اجتماعی جایگاه و نقش مهمی در زندگی روزمره افراد پیدا کرده است. اولین شبکه اجتماعی در سال 1997 در ایالات متحده امریکا ایجاد گردید که کاربران آن قادر به ساختن پروفایل شخصی و برقراری ارتباط با یکدیگر بودند .[1] پس از آن شبکههای اجتماعی دیگری با موضوعات متفاوتی در سراسر جهان ایجاد شدند. شبکههای اجتماعی امکان اشتراک اطلاعات، ایدهها، علایق، فعالیتها و وقایع زندگی را برای کاربران خود فراهم میکنند. برخی از شبکههای اجتماعی عبارتند از Facebook، Twitter ، LinkedIn، Google Plus+ و غیره است.
ساختار شبکههای اجتماعی به صورت گراف است که از گره و پیوندهای تشکیل شده است. گرهها نشان دهنده افراد، سازمان و یا سایر موجودیتهایی2 هستند که تعاملاتی3 را آغاز و یا دریافت میکنند و پیوندها نشان دهندهی تعاملات، همکاری4 و یا نفوذ5 گرهها بر یکدیگر هستند. نمونهای از این پیوندها عبارتند از قیمتها، ایدهها، تبادلات مالی، رابطه دوستی و خویشاوندی، تجارت، تبلیغات، پیوندهای وب، سرایت بیماری و یا مسیرهای هواپیمایی و غیره است. گراف شبکههای اجتماعی ساختار کاملاً پویا دارند و با گذشت زمان با اضافه و حذف شدن گرهها و پیوندها تغییر مییابد. شناسایی مکانیزمی که این تغییرات را پیشبینی و استنتاج نماید، یکی از مسائل مطرح در این زمینه است.
تخمین شباهت بین کاربران و پیشبینی پیوندهایی که ممکن است در آینده نزدیک بین آنها ایجاد شوند یکی از موضوعات مطرح در زمینه شبکههای اجتماعی است. شباهت در شبکههای اجتماعی بر اساس معیارهای از پیش تعیین شده تعریف و محاسبه میگردد. در این مقاله، شباهت به این صورت تعریف میشود «.کاربرانی که از نظر معیار از پیش تعیین شده مشابه هستند را یک رتبه یکسان اختصاص داده میشود و یا آنها را درون یک خوشه قرار داده میشود.»
این معیار می تواند یکی از خصوصیات پروفایل کاربران همچون سن، تحصیلات، محل تحصیل، محل زندگی و غیره است. موقعیت شبکهای کاربران در گراف شبکه اجتماعی نیز نوعی معیار برای تعیین شباهت کاربران است. در سیستمهای پیشنهاد دهنده6 مجموعه ای از پرس-وجوهای از پیش تعیین شده توسط کاربران پاسخ داده می شود؛ پاسخ کاربران برداری از اولویتها برای هر کاربر ایجاد میکند و برای معیار شباهت کاربران از این بردار اولویت استفاده میگردد.
در شبکه های اجتماعی، پیدا کردن میزان شباهت افراد کاربرد بسیاری دارد. برای مثال پیدا کردن مسیر برای گسترش اخبار، عقاید، نظریهها و دیدگاههای سیاسی با یافتن کاربران مشابه امکانپذیر است. یافتن انجمنها و صفحات مورد علاقه کاربر، دوستان هم فکر و عقیده نیز نیاز به یافتن کاربران مشابه دارد. در سیستمهای پیشنهاد دهنده برای یافتن آیتمهای مورد علاقه کاربر نیاز به یافتن شباهت بین علایق کاربر و آیتمهای موجود است. امروزه از شبکه های اجتماعی برای تبلیغ محصولات و بازاریابی استفاده میشود. تبلیغ محصولات نیز نیاز به یافتن کاربرانی است که علایق و سلیقه هایشان مشابه با محصول مورد نظر است .[2] تشخیص رهبران7 و پیروان8 در شبکههای اجتماعی یکی دیگر از کاربردهای تخمین شباهت در شبکه های اجتماعی است .[3]
-2 روشهای تخمین شباهت کاربران شبکههای اجتماعی
کاربران شبکههای اجتماعی به صورت کلی دارای دو خصوصیت ساختاری و غیرساختاری هستند. خصوصیات ساختاری و یا شبکهای به معنای موقعیت قرارگیری کاربر در گراف شبکه است. از خصوصیات ساختاری میتوان به درجه رأس9، تعداد مثلثات10 ، ضریب خوشه بندی11، مرکزیت بردار12 و طول متوسط کوتاه ترین مسیر13 اشاره نمود .[3] خصوصیات ساختاری گراف شبکه اجتماعی به صورت ماتریس مجاورت نمایش داده میشود.
خصوصیات غیرساختاری و یا پروفایلی به معنای اطلاعات دستهبندی شده14 موجود در پروفایل کاربر است. پروفایل کاربر در شبکههای اجتماعی شامل اولویتها، سلایق، رویدادهای زندگی و غیره است. یکی از ویژگیهای بارز اطلاعات دستهبندی شده مرتب نبودن مقادیر فیلدهای آن است. از دیگر خصوصیت بارز پروفایل کاربران شبکههای اجتماعی، کامل نبودن آن است زیرا تکمیل اطلاعات پروفایل کاربران شبکههای اجتماعی در اختیار کاربر است. بسیاری از کاربران اطلاعات پروفایل را کامل وارد نمیکنند و یا اشتباه وارد میکنند. الگوریتمهای تخمین شباهت، با توجه به خصوصیات ساختاری و یا غیرساختاری، سعی در پیدا کردن میزان شباهت بین کاربران مینماید و از این دیدگاه به سه دسته اصلی تقسیم میگردند:
. الگوریتمهایی که تنها با در نظر گرفتن خصوصیات ساختاری کاربران سعی در تخمین میزان شباهت بین کاربران می نماید.
. الگوریتمهایی که تنها با در نظر گرفتن خصوصیات غیرساختاری کاربران و اطلاعات دستهبندی شده موجود در پروفایل کاربران عمل تخمین شباهت را انجام می دهند.
. الگوریتمهایی که با در نظر گرفتن خصوصیات ساختاری و غیرساختاری سعی در تخمین میزان شباهت کاربران نموده است.
با گسترش شبکه های اجتماعی و اهمیت یافتن مسئله شباهت در آنها، ابتدا الگوریتم های دسته اول پا به عرصه نهادند و تعداد زیادی از این الگوریتمها معرفی گردید. اما تنها استفاده از این دسته از الگوریتمها برای تعیین شباهت کاربران کافی نیست. زیرا بسیاری از کاربران از نظر شبکهای هیچ شباهتی ندارند، لیکن از نظر خصوصیات معنایی شباهت دارند. بنابراین الگوریتمهای دسته دوم با ایده گرفتن از مسئله شباهت در دادههای پیوسته و اعمال آن بر دادههای دستهبندی شده موجود در پروفایل کاربران ایجاد گردید.
بر اساس اصل هوموفیلی، در شبکه های اجتماعی بیشتر افرادی که خصوصیات پروفایلی مشابه دارند، از نظر ساختاری نیز به هم متصلتر هستند .[4] به همین دلیل در سالهای اخیر سعی بر ترکیب این دو نوع الگوریتم برای افزایش میزان دقت تخمین شباهت شده است و چالش اصلی در این نوع الگوریتمها ترکیب موثر این دو نوع الگوریتم به منظور بهبود نتایج است. زیرا شباهت ساختاری و غیرساختاری دو مسئله کاملاً مستقلی هستند و هر کدام سهم متمایزی در تعیین شباهت دارند. در این مقاله بررسی شباهت کاربران شبکه های اجتماعی با استفاده از ترکیب موثر شباهت ساختاری و غیرساختاری کاربران انجام خواهد گرفت.
-3 کارهای مرتبط
در زمینه تخمین شباهت بین کاربران شبکههای اجتماعی با استفاده از خصوصیات ساختاری، تحقیقات زیادی انجام شده است 2]و5و6و7و8 و.[9 همچنین در زمینه شباهت غیرساختاری کاربران نیز تحقیقاتی انجام شده است. 10]و[11 اما در نظر گرفتن هم خصوصیات ساختاری و هم خصوصیات غیرساختاری کاربران در تخمین شباهت بین آنان و پیشبینی پیوندهای جدید در بین آنها مسئهای جدید است و در این زمینه تحقیقات کمی انجام شده است.
در [12] روشی برای تعیین شباهت کاربران با استفاده از خصوصیات ساختاری و غیر ساختاری آنها ارائه شده است. در قسمت شباهت غیرساختاری از روش OF استفاده شده است. مزیت مقاله [ 12] نسبت به سایر مقالهها این است که ساختار پروفایل کاربران را به صورت مجموعهای از آیتمها در نظر میگیرد و آیتمهای چندگانه همانند تحصیلات را نیز پیشتیبانی مینماید. در قسمت شباهت ساختاری از روش NS استفاده شده است.
در مقاله [12] برای استنباط مقادیر پروفایل وارد نشده از روش رایگیری اکثریت15 استفاده شده است. در پایان، نتایج بر روی گراف شبکههای اجتماعی جهتدار Youtube و بدون جهت Facebook ارزیابی و مقایسه شده است. در مقاله [12] یک الگوریتم واحد جهت اندازهگیری شباهت ساختاری و غیرساختاری ارائه نشده است و تنها همبستگی بین شباهت ساختاری و غیرساختاری را بیان میکند. در [13] الگوریتم Random Walk with restart معرفی شده است.
در این مقاله با استفاده از خصوصیات گرهها و پیوندهای موجود شروع به یادگیری یک دستهبندی میکند تا گرههای موجودی که پیوندی با آنها ندارد را در گروه گرههای مثبت و یا منفی قرار دهد. گرههای مثبت گرههایی هستند که ممکن است در آینده، پیوندی بین گره مبدأ و یکی از گرههای مثبت برقرار گردد. ابتدا یک الگوریتم یادگیرنده با توجه به خصوصیات دو گره به پیوند بین آنها یک رتبه اختصاص میدهد. سپس الگوریتم Random Walk با توجه به رتبههای ایجاد شده شروع به حرکت در گراف میکند. به بیان دیگر الگوریتم Random Walk توسط رتبه پیوندها تحت تاثیر قرار میگیرد و بیشتر تمایل به حرکت در پیوندهایی دارد که رتبه آنها بیشتر است. در این روش، خصوصیات گرهها و پیوندها بایستی از قبل مشخص باشد بنابراین به-کارگیری این روش در شبکههای واقعی امکانپذیر نیست.
یکی از کاربردهای مهم تخمین شباهت خوشهبندی کاربران است. در [14] الگوریتم SA-cluster معرفی شده است که پس از تخمین شباهت با استفاده از خصوصیات ساختاری و غیرساختاری کاربران، آنها را درون خوشه مناسب قرار میدهد. کاربران درون یک خوشه رتبه یکسانی دارند و نمیتوان رتبه مجزا به کاربران درون یک خوشه اختصاص داد. در مقاله [14] اطلاعات پروفایل کاربران را به صورت اطلاعات دسته بندی شده در نظر نمیگیرد و تنها یک خصوصیت برای پروفایل کاربران در نظر گرفته است.
-4 شباهت ساختاری
در بخش شباهت ساختاری الگوی پیشنهادی این تحقیق از الگوریتمهای SRank، SimRank و P-Rank استفاده شده است. الگوریتمهای SimRank و P-Rank بر پایهی همسایگان گره عمل میکنند و الگوریتم SRank بر پایهی مسیرهای کوتاه بین دو گره عمل میکند. در ادامه الگوریتمهای فوق شرح داده خواهند شد. ایده اصلی الگوریتم SRank به این صورت بیان میشود: «دو گره در یک گراف جهتدار در صورتی با یکدیگر مشابهاند که از طریق چندین مسیر با طول کوتاه به یکدیگر متصل باشند.« به طور دقیقتر شباهت بین دو گره a و b در یک گراف توسط دو شرط زیر تحت تاثیر قرار میگیرد:
. تعداد مسیرهای کوتاه از a به b
. طول مسیرهای کوتاه از a به b
برای محاسبه شباهت بر اساس SRank، ابتدا بایستی مقدار دسترسی تعریف و محاسبه شود. Pp ماتریس احتمال انتقال با ابعاد N*N در گراف G است. طول این ماتریس p است. مقدار دسترسی از گره a به گره b به صورت رابطه - 1 - تعریف میشود.
