بخشی از مقاله
پیشبینی لینک مبتنی بر زمان در شبکه های دوبخشی
چکیده
شناخت هرچه بیشتر مکانیزم رفتاری انسانها در شبکهها، بر فهم ما از نحوه تکامل و رشد شبکهها تاثیر بسزایی دارد. در یک شبکه انلاین رفتار انسانها را میتوان همچون یک گراف دو بخشی user-object در نظر گرفت که در ان کاربران توسط لینکهایی به اشیاء متصل هستند. پشبینی لینک از روشهایی است که توسط ان میتوان رفتار آینده افراد را پیشبینی کرد.در این مقاله پیشبینی لینک از دیدگاه تفکیک زمانی مورد بررسی قرار میگیرد.در تفکیک زمانی نشان میدهیم که دنباله پیمایشات هر فرد را میتوان به چندین دنباله پیمایش با بازه زمانی مختلف تبدیل کرد. همچنین بحث سالخوردگی لینکها رابیان میکنیم و تاثیر گذر زمان بر توانایی لینکها برای پیشبینی لینکهای اینده نشان خواهیم داد. از اطلاعات زمانی برای ساخت شبکه دوبخشی وزن دار زمانی (TWBN) استفاده میکنیم و سپس با استفاده از فیلترهای مشارکتی سعی در ساخت یک سیستم پیشبینی لینک خواهیم داشت.
-1 مقدمه
در سالهای اخیر پویایی انسانها در شبکهها مورد توجه بسیاری از محققین قرار گرفته است. شناخت هرچه بیشتر مکانیزم رفتاری انسانها در شبکهها بر فهم ما از نحوه تکامل و رشد شبکهها تاثیر بسزایی دارد. [1] پشبینیلینک از روشهایی است که توسط ان میتوان رفتار آینده افراد را پیشبینی کرد. در پیشبینی لینک معمولا گرافی با نام گراف مشاهده1 وجود دارد که تکامل شبکه را طی یک دوره خاص نشان میدهد. در این گراف مجموعه بزرگی از یالهای شکل نگرفته وجود دارد وهدف الگوریتمهای پیشبین این است که با توجه به یالها موجود فعلی وزن خاصی را به یالهای ناموجود 2 بدهند.[2] این وزن بیانگر احتمال رخداد این یالها در اینده است و هر چه وزن بالاتر احتمال رخداد هم بالاتر است. ساخت سیستمی که قادر باشد لینکهای اینده را به درستی پیشبینی کند از اهمیت بالایی برخوردار است. برای مدل کردن رفتار انسانها در شبکههای اطلاعاتی، از گرافهای دوبخشی استفاده میشود. یک گراف دوبخشی به صورت سه تایی G(U,O,E) نشان میدهند که این گراف از دوگروه نود UوO تشکیل شده و یالها تنها میتوانند میان این دوگروه نود برقرار میشوند.[3]
از کاربردهای مهم پیشبینیلینک در گرافهای دوبخشی میتوان به بحثهایی همچون پیشنهاد تگ یا انتشار منابع3 نام برد که کاربرد فراوانی در سیستمهای پیشنهاددهنده[4] 4،انتشار در شبکهها[5]5 و بررسی رفتار در شبکههای اجتماعی[5] 6دارد.تحقیقات نشان داده که هر شبکه دوبخشی از تعدادی گروه یا خوشههای کوچکتر تشکیل یافته است.افراد هر خوشه بیشترین ارتباطات را باهم و کمترین ارتباط را با خوشههای دیگر دارند.بررسی شبکه بر اساس خوشهای تشکیل دهنده ان بار اطلاعاتی بیشتری نسبت به بررسی شبکه به صورت واحد دارد. همانطور که در شکل1 میبینید خوشهها با رنگهای مختلف نشان داده شدهاند.لینکهای سیاه بیانگر ارتباطات میان خوشهها هستند.الگوریتم-های خوشهبندی گراف معمولا با حذف این لینکهای سیاه سعی در پیدا کردن خوشهها دارند.اما این لینکها خود حاوی اطلاعات مفیدی از رفتار نودها در شبکهها میباشند.اگر ما بتوانیم اتصالات یک نود را که در طول زمان با دیگر نودها برقرار کرده به چندین زیر مجموعه بر اساس زمانهای مختلف شکلگیریشان تجزیه کنیم، در ان صورت قادر خواهیم بود که از تعداد لینکهای سیاه در شبکه بکاهیم.
ترجیحات افراد در طول زمان تغییر میکنند و در شبکهها لینکهای جدیدرا شکل می دهند. دیتاستهای متناظر با شبکههای اجتماعی معمولا از رکوردهایی که بیانگر سابقه پیمایشات کاربران انها است تشکیل شده است جدول.1هر یک از پیمایشاتٍکاربران در زمان خاصی رخ داده است و دنباله پیمایشات کاربران ممکن است چندین ماه طول کشیده باشد. مسلم است که انتخابهایی که در زمانهای نزدیک بههم صورت گرفتهاند ارتباط بیشتری نسبت به انتخابهایی که در فاصله زمانی طولانیتری ازهم قرار گرفته است دارند. در بسیاری از مقالات بحث بازه زمانی میان پیمایشات نادیده گرفته میشود و پیمایشات کاربران را به عنوان دنباله واحد در نظر میگیرند و تاثیر پیمایشات کاربران را بر هم یکسان میدانند. در این مقاله ما فرض میکنیم دنباله پیمایشات کاربر از چندین دنباله پیمایش مجزا تشکیل شده (مثلا پیمایشاتی را که کاربر در یک ماه پیموده ممکن است به سه پیمایش 10 ، 5 و 15 روزه تفکیک شود ) و این دنبالهها بر حسب زمان، تفکیک میکنیم .
بحث پیشبینیلینک مربوط به پویایی گرافها است و پویایی گرافها با مبحث زمان معنی پیدا میکند.در طول عمر یک شبکه لینکهای زیادی بوجود میایند اما تاثیر همه این لینکها ،در پیشبینی لینکهای اینده یکسان نیست. لینکهایی که در زمانهای اخیر رخ دادهاند (لینک جوان)نسبت به لینکهایی که در گذشتههای دور رخ دادهاند(لینک پیر) از اهمیت بیشتری برخوردار هستند. الگوریتمهایی که قادر باشند تاثیر زمان را در پیشبینی خود بکار برند عملکرد بهتری خواهند داشت.[6] در بحث سالخوردگی، معمولا یالهای گراف بر حسب اختلاف زمان شکلگیریشان با زمان فعلی وزن دار میشوند. این امر موجب میشود که تاثیر رخدادهای اخیر بر اینده بیشتر از رخدادهای گذشته باشد. نتیجه اینکار ساخت گراف دویخشی وزن دار TWBN7 است.در این گراف وزن یالها میزان اهمیت انها در پیشبینی لینکهای اینده است. روشهای زیادی با رویکردهای متفاوت برای حل پیشبینی لینک ارائه شدهاند.که خلاصهای از انها را در بخش2 امده است.در این مقاله ما از رویکرد فیلترهای مشارکتی در جهت ساخت سیستمهای پیشگو استفاده میکنیم.[7] فیلترهای مشارکتی با استفاده از تجربه وب سعی در پیشبینی لینکهای اینده دارند. در این مقاله ما از روش Item-base CF استفاده خواهیم کرد. ایده این روش بر این اصل استوار است که ایتمهایی که کاربر در اینده انتخاب میکند رابطه نزدیکی به ایتمهایی که او قبلا انتخاب کرده دارد. هرچه ارتباط میان یک ایتم با ایتمهای پیموده شده قبلی کاربر بیشتر احتمال انتخاب آن بیشتر است. همانطور که نشان داده خواهد شد ما فیلترهای مشارکتی را بر روی ماتریس مجاورت گراف TWBN اجرا خواهیم کرد.روش پیشنهادی را با روش-
های GRM و Item-base CF و T_ Item-base CFمقایسه می- کنیم. نتایج دلالت بر عملکرد بهتر سیستم پیشنهادی نسبت به روش-های رقیب دارد.
ساختار این مقاله به این صورت است که در بخش 2 تاریخچه گفته میشود بخش 3 تفکیک زمانی و3.1 وزن زمانی در بخش 4 فیلترهای مشارکتی در در بخش 5 ازمایشات بخش 6 نتیجه گیری وبخش 7 منابع است.
-2 تاریخچه
یکی از ویژگیهای مشترک میان همه شبکهها بحث همریختی8 یا شباهت است.طبق این ویژگی نودهای مشابه در یک شبکه، شبیه هم عمل میکنند.این ایده مبنای به وجود امدن بحث پیشبینی لینک است. الگویتمهای پیشبینی لینک با پیدا کردن ویژگیهایی که بهنحوی بیانگر میزان شباهت میان نودها است سعی در پیشبینی اینده دارند. پیشبینیلینک در شبکههای دوبخشی با اهداف مختلفی صورت می-گیرد.گاه هدف از پیشگویی لینک در شبکههای دوبخشی شناخت هر چه بیشتر ارتباطات میان نودهای یک گروه خاص است مثلا درگراف co-authorship هدف پیشبینی همکاری میان محققان است در این مسائل پیشبینیلینک بر روی گرافدو بخشی authorship اعمال و سپس این گرافها را به گرافهای تکبخشی تبدیل میکنند (نودهای نمایش دهنده مقاله را حذف کنیم) . در [8] این کار صورت گرفت.ولی در [9] ثابت شده که استفاده از نمایش تکبخشی موجب ناتوانی در تفسیرصحیح ارتباطات میشود. گاهی اوقات هدف ، پیشبینی لینک میان نودهای گروه user وobject است. برای مثال شبکه متابولیک و شبکه خرید از این دستهاند. [10] با استخراج ویژگیهای تپولوژیکی از ساختار گرافدوبخشی و استفاده از پیشبینیلینک سعی در ساخت یک سیستم پیشنهاددهنده داشت.[11] از تکنیک تخصیص پویای منابع در جهت استخراج ویژگیهای جدید از ساختار گراف بهره جست. [6] ضرائب زمانی را با تکنیک تخصیص پویای منابع ترکیب کرد ونشان داد که عملکرد پیشگویی لینک بهتر از روش قبل است.[3] روش جبر گرافی در جهت پیشبینیلینک استفاده کرد و نشان داد که این روش از سرعت بالایی در حجم زیاد دادهها برخوردار است [12]. از کلاس بند با ناظر جهت ترکیب ویژگیها استفاده کرد و نشان داد دقت پیشبینی افزایش مییابد [14 , 13] . از خوشه بندی برای مقابله با مقیاسپذیری استفاده کرد. هدف این مقالات به کاربردن الگوریتمها و روشهای مختلف در جهت ساخت سیستمی با دقتتر وسریعتر بر روی ماتریس پیمایشات کاربران است.در اکثر این مقالات مبحث بازه زمانی میان پیمایشات نادیده گرفته میشود و پیمایشات کاربران را به عنوان دنباله واحد در نظر میگیرند و همچنین تاثیر پیمایشات کاربران را بر هم، یکسان میدانند.
هدف ما در این مقاله بررسی تاثیر تفکیک زمانی بر عملکرد الگوریتم-های پیشبینیلینک است. ما از فیلترهای مشارکتی در جهت ساخت یک سیستمپیشبینی لینک استفاده میکنیم و نشان خواهیم داد که تفکیک زمانی پیمایشات کاربران میتواند موجب بهبود عملکرد این الگوریتم شود. ما ازمایشات خود را بر روی دیتاست Movielense [15] اعمال و تاثیرات مثبت تفکیک زمانی بر عملکرد الگوریتم پیشبینیلینک را با نمودارها وجداول نشان میدهیم.
-3 تفکیک زمانی و ساخت گراف :TWBN
1-3 تفکیک زمانی:
کاربران در میان منابع موجود در سایتهای اطلاعاتی به دنبال علایق خود میگردند .علایق کاربران در طول زمان تغییر میکند. سابقه پیمایش کاربران در واقع از زیر دنبالههایی تشکیل شده که هر کدام بیانگر علاقه کاربر در یک دوره× خاص است.در جدول 1سابقه پیمایشات پنج کاربر شبکه نشان داده شده است.همانطور که میبیند دنباله پیمایشات یک کاربر در زمانهای متفاوتی رخ میدهد. مثلا پیمایشات کاربر 1 از روز 3 شروع و تا روز 10 ادامه میابد. در این بازه گاهی کاربر در مدت زمان محدودی چندین انتخاب داشته و سپس تا چندین روز بعد انتخاب دیگری ندارد. برای نمونه کاربر 1 از بازه زمانی 3 تا 4 سه انتخاب و از بازه 9 تا 10 دو انتخاب دارد. فاصله زمانی میان این دو بازه به 5 روز میرسد.مسلما ایتمهای انتخاب شده توسط کاربر که در یک بازه بودند را بطه بیشتری نسبت به ایتمهایی که در بازه زمانی متفاوت بوده اند دارند. در شبکههای واقعی اختلاف این بازهها بیشتر است. اگر بتوان ایتمهای پیموده شده نزدیکبه هم را تفکیک کرد بهتر میتوان شباهت میان انها را مشخص کرد. در این مقاله ما دنباله پیمایشات کاربران را به بازههای مختلف تفکیک می-کنیم. برای تفکیک سازی پیمایشات اینگونه عمل میشود که اگر فاصله بین دو انتخاب متوالی کاربر از K روز بیشتر باشد این امر نشان دهنده این است که کاربر علاقهاش عوض شده است. مثلا اگر k=5 در نظر بگیریم پیمایشات کاربر 1 به دو زیر پیمایش تقسیم میشود. بعد از تفکیک سازی سابقه پیمایشات هر کاربر به زیر دنبالههای متناظر، از این زیردنبالهها برای ساخت سطرهای ماتریس پیمایش استفادهمی-کنیم(هر زیر دنباله یک سطر را نشان میدهد). ماتریس پیمایش A[m*n] از mکاربر و n ایتم تشکیل شده است و درایه[i,j] این ماتریس مخالف صفر است اگر کاربر i ، ایتم j را پیموده باشد.سطرهای این ماتریس دنباله پیمایشات کاربران را نشان میدهد.انتخاب اندازه K از اهمیت بالایی برخوردار است. اگر K خیلی کوچک باشد موجب می-شود که ماتریس پیمایش تنک شود. اگرK بزرگ باشد باعث میشود که تفکیک زمانی رخ ندهد .پیدا کردن مقدار مناسب برای K خیلی مهم است.
2-3 ساخت گراف TWBN
با گذشت زمان از ارزش لینکها موجود برای پیشبینی لینکهای اینده کاسته میشود.هرچه فاصله شکل گیری یک لینک با زمان فعلی بیشتر باشد (لینک پیر) تاثیر آن در پیشبینی لینکهای فعلی کمتر خواهد بود و بلعکس. برای اینکه تاثیر گذر زمان را بر لینکها مدل کنیم ،ما از فاصله زمانی در جهت وزندار کردن لینکها استفاده میکنیم. این وزن بیانگر اهمیت لینک در پیشبینی لینکهای اینده است. ما از فرمول ارائه شده در مقاله [6] به عنوان معیاری در جهت وزن دهی لینکها استفاده میکنیم.
در اینجا Tu,i زمانی را که کاربر U، ایتمIرا پیموده وNowTime زمان فعلی را بیان میکند . الگوریتم پیشگو باید یالهای موجود در زمان وNowTime را پیشبینی کند. ضریب تاثیر اختلاف زمانی است و مقدار 0≤ است. یک مقدار ثابت ومقدار ان <1 0< است. اگر زیاد باشد ، بیشتر میشود (تاثیر فاصله زمان کم خواهد شد) وبلعکس. هرچه توان بزرگتر باشد مقدار کوچکتر خواهد بود.در این مقاله ما مقدار را برابر با و =0.5 در نظر ما از فرمول فوق برای وزن دهی یالهای موجود در گراف استفاده می-کنیم. نتیجه کار تشکیل گراف TWBN است.
