بخشی از مقاله
مروری بر کاوش اتصالات در شبکه های اجتماعی
چکیده
رشد روزافزون شبکه های کامپیوتری و اینترنت باعث ظهور شبکه های اجتماعی در دنیای امروزی شده است. این شبکهها نشانی از جامعه-ی واقعی را به دنبال دارند و دارای تأثیر متقابل بر یکدیگرند. بررسی رفتار کاربران موضوع مهمی در هر سیستم مورد استفاده میباشد تا بهتوان بر اساس آن تصمیم گیری نمود. این رفتار در غالب گروهها و زیر گروههای معینی موجود و البته در لوای دادههای حجیم کاربران پنهان میباشد. به دلیل رواج و گسترش شبکه های اجتماعی و اهمیت دادههای عظیم و موجود در این شبکهها کاوش اتصالات به یک چالش اصلی در آنالیز شبکه های اجتماعی تبدیلشده است که زمینه را برای تخمین اتصالات و ایجاد سیستمهای پیشنهاد گر فراهم مینمایید. کاوش اتصالات تکنیکهای داده کاوی هستند که در زمان ساخت مدلهای توصیفی یا تخمینی به طور دقیق به اتصالات توجه دارند. وظایف کاوش اتصالات بر رتبه بندی موجودیت، کشف گروه، کلاس بندی جامع، تخمین اتصالات و کشف زیر گروه تمرکز دارد. این مقاله به بررسی کاوش اتصالات در دهه اخیر پرداخته است، بدین منظور ساختار اتصالات و دو وظیفه اصلی کاوش اتصالات که مربوط به موجودیتها و اتصالات است موردبررسی قرارگرفته است.
واژههای کلیدی
دادهکاوی، شبکه های اجتماعی، تخمین اتصالات، شناسایی موجودیت
-1 مقدمه
اتصالات (لینک) یا بهصورت عامتر ارتباطات در بین نمونه دادههای موجود در همهجا هستند. [1] این اتصالات اغلب نشان دهنده الگوهایی هستند که بر ویژگیهایی از نمونه دادهها مثل ارزش، رتبه و طبقهبندی اشاره دارند. در بیشتر موارد اتصالات قابلمشاهده نیستند و به همین دلیل ما به تخمین اتصالات جذب میشویم. اتصالات قادر به نمایش شبکه های همگن و یا شبکه های ناهمگن هستند که شبکه های همگن دارای یک نوع موجودیت مجرد و یک نوع اتصال هستند ولی شبکه های ناهمگن دارای چندین نوع موجودیت و چندین نوع اتصال هستند. برای شبکه های همگن بهترین مثال میتواند شبکه های اجتماعی باشد که افراد به آن متصل شده و میتوانند با استفاده از اتصالات از نوع دوستی باهم در ارتباط بوده و از اطلاعات به اشتراک گذاشتهشده توسط دیگر موجودیتهایی که با آن ها اتصال دوستی دارند استفاده نمایند. مثال برای شبکه های ناهمگن اتصالاتی که در دامنههای پزشکی بین بیماران، بیماری و مداوا وجود دارد را میتواند در نظر گرفت[2] .کاوش اتصالات تکنیکهای داده کاوی هستند که در زمان ساخت مدلهای توصیفی یا تخمینی بهطور دقیق به اتصالات توجه دارند
-2 کارهای گذشته
کاوش اتصالات حوزهی تحقیقانی به نسبت جدید و نهفتهای است که در تقاطع تجزیهوتحلیل اتصالات، ابرمتن و کاوش وب، آموزشهای رابطهای و برنامهنویسی منطقی استقرایی و کاوش گراف است. کاوش اتصالات نشان دهنده مجموعهای مهم و ضروری از روشهای ساخت برنامههای کاربردی مفید از داده کاوی در طیف گستردهای از حوزههای واقعی و مهم است، بهویژه آنهایی که مربوط به تشخیص رویدادهای پیچیده از دادههای بهشدت ساختیافته هستند.[3]
کاوش اتصالات هم چالشها وهم فرصتها را نشان میدهد. این چالش به دلیل ناکافی بودن تکنیکهای داده کاوی برای دادههای غیر مرتبط برای مشکلات مشابه با دادههای مرتبط به وجود آمده است.
معروفترین مثال از بهرهبرداری از ساختار لینک استفاده از لینک برای بهبود نتایج بازیابی اطلاعات است. معیار رتبه صفحه و هاب و درجه اقتدار اساس ساختار لینک از وب هستند. این الگوریتمها بر اساس رابطه رجوع در میان صفحات وب هستندارتباط نزدیکی بین اتصالات و ابرمتن و کلاسبندی صفحه وب وجود دارد. این کار ریشه در بازیابی اطلاعات1 جامعه دارد. مجموعه ابرمتنها دارای یک ساختار غنی برای بهبود دقت کلاسبندی مورداستفاده قرار میگیرد. ابرمتنها علاوه بر کلمات دارای لینکهای ورودی لینک خروجی هستند. با استفاده از اطلاعات اتصالات نتایج طبقهبندی بهتر میتوان به دست آورد.[4]
در کاوش اتصالات تمامی اتصالات موجود بهصورت گراف یا شبکه نمایش داده میشود. میتوان شبکهای ساخت که گرههای آن کاربران و لبهها نشان دهنده شرکت کاربران در اتفاقات مشترک است. این نوع نمایش اجازه اجرای آنالیزهای مبتنی بر کاربران را میدهد همچنین این ارتباطات را در قالب گراف نیز میتوان نشان داد که در این نوع نمایش اتفاقات گرهها را تشکیل میدهند و لبهها در صورت وجود کاربران مشترک در یک اتفاق هستند. انعطاف در نمایش با گراف از یک ارائه زوج مرتب از گراف پایه ناشی میشود. این بخش بهعنوان یک مرحله در امر داده کاوی محسوب نمیشود ولی ارائه انتخابشده میتواند تأثیر به سزایی در کیفیت استنباط آماری که میتواند ساخته شود داشته باشد .[3]
-3 کاوش اتصالات
بهمنظور کاوش اتصالات مراحل زیر باید انجام شود.
1. شناسایی موجودیتها
2. رتبهبندی موجودیتها بر اساس اتصالات
3. طبقهبندی موجودیتها بر اساس اتصالات
4. خوشهبندی موجودیتها بر اساس اتصالات
5. تخمین اتصالات بر اساس اتصالات
-1.3 شناسایی موجودیتها
شامل شناسایی مجموعهای از موجودیتها در یک دامنه است. هدف تعیین منابع دادهها است تا بتوان به همان موجودیتها در دنیای واقعی مراجعه شود. نمونهای از این مشکل در پایگاه دادهها در پردازش زبان طبیعی و مدیریت اطلاعات شخصی و فیلدها وجود دارد. در عمومیترین شکلها مشکل با چندین متغیر تعریف شده است .[4]
3.2. رتبه بندی موجودیتها بر اساس اتصالات
شاید مهمترین وظیفه کاوش اتصالات رتبهبندی موجودیت بر اساس اتصال است (LBR)2 که تمرکز بر آنالیز اتصالات دارد . هدف (LBR) کنترل ساختار اتصال یک گراف است تا بتواند مجموعهای از موجودیتها را توسط گراف اولویتدهی نماید یا مرتب نماید. اهمیت صفحات وب بر اساس اهمیت محتوی آنها است که به علاقهمندیها و دانش و گرایشها و رفتار کاربران بستگی دارد ولی برای به دست آوردن اهمیت صفحات وب بهصورت اتوماتیک باید رتبه صفحه وب را به دست آورد.[1] برای به دست آوردن رتبه صفحات وب روشهای مختلف محاسبه رتبه برای هر صفحه وب بر اساس گراف وجود دارد.
درروش PAGE RANK برای محاسبه رتبه صفحات وب از الگوریتم (1) استفاده شده است.[5]
مدلهای رتبه دهی صفحه وب موجسوار با عنوان گام تصادفی HITS3 که در آن موجسوار (کاربر) بهطور تصادفی انتخاب میکند و پسازآن اتصالات را دنبال میکند و گاهی اوقات به یک صفحه جدید جهش میکند و یک پیمایش جدید از ساختار اتصال را آغاز میکند. رتبه دادهشده به یک صفحه وب بهصورت کسری از زمان است کهموج سوار بهصورت تصادفی در آن صفحه سپری کرده است. این رتبه را میتواند با محاسبه توزیع حالت پایدارتر از فرآیندهای تصادفی تعیین کرد. درروش دیگر فرآیند کمی پیچیده تراست مدلسازی از وب با ترکیب دو نوع از صفحات وب مراکز و مقامات فرض میشود . مراکز صفحات وبی هستند که به بسیاری از صفحات معتبر پیوند میباشد و مقامات صفحات وبی هستند که توسط بسیاری از مراکز اتصالات شدهاند. به هر صفحه در وب یک مرکز و یک نمره نفوذ داده میشود. این نمرات بر اساس یک الگوریتم تکرارشونده که نمرات یک صفحه را بر اساس بروز رسانی نمرات صفحاتی که در مجاورت آنها هستند محاسبه میکند .[6]
تمامی تحقیقات انجامشده بر اساس الگوریتمهای مطرحشده PAGE RANK و الگوریتم HITS است. جدول 1 تلاشهای انجامشده برای رتبهبندی موجودیتها در مقالات مختلف گردآوریشده است.
جدول:1 الگوریتمهای رتبهبندی موجودیت
-2.
3.3 کلاسبندی موجودیتها بر اساس اتصال
در ابتدا کلاسبندی موجودیتها با استفاده از ماشینهای یادگیر قدیمی انجام میشد ولی به دلیل ناهمگن بودن ساختار بسیاری از دادهها از این روش استفاده نمیشود. روش دیگر کلاسبندی بر اساس اتصال )LBC( است. گراف داده G=(O,L) مجموعهای متشکل از موجودیتهای که با O نمایش دادهشده است توسط یک اتصال L وصل هستند. اکنون باید اعضای O از مجموعهای محدود از مقادیر طبقهبندیشده برچسبگذاری شوند. قابلیت تشخیص LBC که میتواند آن را از کلاسبندیهای قبلی متفاوت سازد این است که در بسیاری موارد برچسبها مرتبط با موجودیت ها هستند. چالش اصلی طراحی الگوریتمی برای کلاسبندیهای اشتراکی یا دستهجمعی است که بتواند این همبستگی و اتصال را در بین موجودیتهای طبقهبندیشده موجود در گراف به دست آورد. اکثر تلاشهای انجامشده در زمینه کلاسبندی بر اساس LBC است.
فیلد تصادفی نامعلوم (CRF)4که از چارچوبی برای ساخت مدلهای احتمالاتی برای بخشبندی و برچسبگذاری دادههای متوالی استفاده میکند که با گسترش حداکثر مدلهای آنتروپی سنتی برای LBC در موارد محدودی که در آن گراف دادهها زنجیرهای است .[7]
درروش دیگری برای کلاسبندی دادههای رابطهای یک فرصت منحصربهفرد برای بهبود صحت کلاس بندی مدلهای آماری را ارائه میدهند. اگر دو جسم باهم ارتباط دارند، استنتاج چیزی در مورد یک شیء میتواند به استنتاج درباره دیگری نیز کمک نماید. این روش با استفاده از طبقهبندی ساده بیزی در مد تکرارشونده میپردازد، که با بهروزرسانی پویا ویژگیهای
