وبلاگ

مدل های احتمالی یا روش های غیر سنتی نیز مورد بررسی قرار گرفتند.روش های مدعی در این مقوله، الگوریتم هایی هستند که توسط وانگ[۴۲] ، ساتولوری[۴۳] و پارتاساراتی [۴۴]در [۳۹] و کاشیما[۴۵] و ابه [۴۶]در [۴۱] طراحی شده اند. اولین الگوریتم از یک مدل احتمالاتی محلی مبتنی بر)[۴۷] MRFزنجیره تصادفی مارکوف( یک مدل گرافیکی غیر مستقیم استفاده کرده و دومی یک مدل احتمالاتی پارامتریک را به کار برده است. در مقابل کاشیما و دیگران [۴۱] یک مدل احتمالاتی جالب از تکامل شبکه پیشنهاد دادند که می تواند در پیش بینی لینک مورد استفاده قرار گیرد. آنها نشان دادند که با داشتن پارامترهای قابل تنظیم در یک مدل تکاملی شبکه، می توانند یک الگوریتم یادگیری برای پیش بینی لینک طراحی کنند. کلوست[۴۸] و دیگران [۴۱] یک مدل احتمالاتی پیشنهاد دادند که ساختار سلسله مراتبی شبکه را در نظر می گیرد. به گونه ای که رأس ها به گروه ها و زیر گروه هایی در چندین مقیاس تقسیم می شوند. این مدل ساختار سلسله مراتبی داده های شبکه را استنتاج می کند و می تواند برای پیش بینی لینکهای از دست رفته به کار رود. این روش به عنوان یک مدل احتمالاتی برای گراف های تصادفی سلسله مراتبی پیشنهاد داده شد. عمل یادگیری استفاده از داده های مشاهده شده شبکه برای تنظیم شبیه ترین ساختار سلسله مراتبی از طریق استنتاج آماری _ترکیبی از رویکرد حداکثر احتمال و الگوریتم نمونه گیری مونت کارلو_ است. تحقیق بر روی تحولات شبکه اجتماعی [ ۱۹ , ۲۰ , ۲۱] بسیار به مساله پیش بینی لینک نزدیک است. یک مدل تکاملی شبکه می تواند لبه های یک شبکه را با توجه به تعدادی ویژگی مشهور موجود پیش بینی کند. فرق این دو مقوله در این است که اولی بر روی ویژگی های سراسری شبکه و دومی بر حالت های محلی شبکه تمرکز می کند. در سالهای اخیر کار بر روی پیش بینی لینک از جنبه های مختلف دچار تحول شده است. یکی از جنبه های اصلی این کارها در نظرگرفتن زمان در مدل است۲۲] ،[۱۷ نشان داد [۱۷] که با اضافه کردن ویژگی زمان در تحلیل شبکه های اجتماعی می توان کارایی برنامه در پیش بینی لینک را افزایش داد. ۳-۳-روش های یادگیری ماشین برای پیش بینی لینک الگوریتم های یادگیری ماشین[۴۹] به دوصورت باناظر[۵۰] و بدون ناظر[۵۱] تعریف میشوند.تمایز بین این دو روش در اینکه چگونه روش های یادگیری داده ها را دسته بندی مینماید میباشد.هردوی این روش ها در مطالعات و تحقیقات مربوط به پیش بینی لینک با چارچوب های متفاوتی استفاده شده است.تحقیقات نشان داده است که کارایی روش ها با بهره گرفتن از متدهای با ناظر بیشتر از متدهای بدون ناظر میباشد. بااین حال چالش های پیش روی شبکه های اجتماعی شامل پیچیدگی و اندازه شبکه های اجتماعی میباشد و با تغییر زمان آشکار میشود. ۳-۳- -۱یادگیری بدون ناظر برای پیش بینی لینک یادگیری بدون ناظر برای یادگیری مدل ها از داده هایی که برچسب گذاری نشده اند استفاده میشوند.در حقیقت وظیفه اصلی یادگیری بدون ناظر یادگیری برچسب کلاس ها به صورت خودکار میباشد.به منظور کشف کردن برچسب های کلاس ها شباهت یا فاصله بین داده های مورد تست به وسیله الگوریتم یادگیری بدون ناظر انجام میشود.داده های مشابه در یک خوشه“clusters گروه بندی میشوند و به عنوان یک کلاس برپسب گذاری میشوند.با این حال پیش از تعیین تعداد خوشه ها تصمیم سخت و اختیاری میباشد.در بحث پیش بینی لینک مشکل خوشه بندی ها از آنجایی که اساسا دسته بندی ها دودویی میباشد ساده میباشد.مهمترین وظیفه در اینجا پیدا کردن موثرترین روش با ناظر برای دسته بندی نمونه هایی است که در یک لینک ممکن است وجود داشته باشند یا موجود نباشند. همه ی ویژگی هایی که شباهت بین جفت گره ها را بیان میکند در پیش بینی لینک با بهره گرفتن از روش های بدون ناظر قابل استفاده است.بیشتر روش های بدون ناظر امتیاز هایی را براساس همسایگی گره ها یا اطلاعات مسیر را برای بدست آوردن امتیاز به یک لینک بالقوه میدهند. [۴۷]این امتیازها میتواند تعداد همسایگان مشترک ،تعداد کوتاهترین مسیرها معیار کارایی جاکارد و … باشد.بیشتر تحقیق های پیش بینی لینک از روش های بدون ناظر به عنوان روش پایه ای برای مقایسه ها استفاده شده اند.وظیفه دسته -بندی[۵۲] در پیش بینی لینک تشخیص این مورد میباشد که آیا لینک در آینده ظاهر شده است یا خیر.بنابراین مقدار آستانه ،رسیدن به این مقدار است که اگر لینک های دسته بندی شده امتیازی بالاتر از مقدار آستانه دارند به عنوان لینک های بالقوه هستند و اگر از مقدار آستانه کمتر باشند به عنوان لینک های بالقوه نمیباشند. به صورت کلی ،وظیفه این دسته بندی باینری با بهره گرفتن از روش های بدون ناظر به خوبی حاصل نمیشود و از اینرو این روش ها در پیش بینی لینک محبوبیت آنچنانی ندارند. با این حال در تحقیقات پیش بینی لینک که براساس نزدیکی محلی یا همسایگی ها میباشد اغلب روش های بدون ناظر استفاده موثرتری دارند.لین و همکارانش روش های بدون ناظر را در پیش بینی لینک و برای داده های چند رابطه ای پیشنهاد داده اند.در محیط های چند رابطه ای هر لینک یک برچسب کلاس به عنوان مستروف،منتشر شده ،ذکر شده و …دارد.وظیفه پیش بینی لینک های بالقوه با بهره گرفتن از این کلاس ها میباشد. بیشتر تحقیقات فقط از روش های بدون ناظر که نسبتا کم میباشد استفاده شده است. بیشتر تحقیقات پیش بینی لینک به روش های با ناظر بستگی دارد و به خاطر کاربردهای محدود روش های بدون ناظر میباشد.در بخش بعدی روش های بدون ناظر شرح داده میشوند. ۳-۳-۲-یادگیری با ناظر برای پیش بینی لینک دسته بندی با ناظر(راهنما)یا نظارت شده اغلب به نحوی انجام میشود که به آن سیستم هوشمند [۵۳]گفته میشود.بنابراین تعداد زیادی از تکنیک های باناظر براساس هوش مصنوعی توسعه یافته اند شامل(روش های مبتنی بر منطق و تکنیکهای براساس پرسپترون)و تکنیک های آماری شامل (شبکه های بیزین و تکنیک های براساس نمونه)میباشند.هدف اصلی یادگیری با ناظر ساختن یک مدل مختصری از برچسب کلاس های توزیع شده است که به عنوان ویژگی های پیش گویی کننده میباشند.نتایج دسته بندی کننده برای رسیدن به برچسب کلاس ها برای نمونه های مورد آزمایشtest که مقدار ویژگی های پیش گویی کننده شناخته شده است اما مقدار برچسب کلاس ها ناشناخته و بدون نام است ،استفاده میشود. [۴۶]. در الگوریتم های باناظر،کلاس ها از پیش تعیین شده و مثال ها با کلاس های مربوط برچسب گذاری میشوند.این کلاس ها یک مجموعه محدود میتواند باشد.وظیفه یادگیری ماشین با ناظر ،جستجوی الگوها و ساخت مدل ریاضی میباشد. سپس این مدل براساس ظرفیت پیش گویی کننده مرتبط با اندازه واریانس در داده های خودش ارزیابی میشود. متدهای در دسترس از قبیل درخت تصمیم،naive Bayes،ماشین بردار پشتیبان(SVM)[54] ،رگرسیون منطقی و…مثال هایی از تکنیک های یادگیری با ناظر میباشند. برخلاف روش های بدون ناظر ،روش های باناظر به تازگی در پیش بینی لینک استفاده شده اند.بعضی از مطالعات اخیر از الگوریتم های باناظر خاصی را برای پیش بینی لینک توسعه داده اند.داپا و همکارانش یک الگوریتم یادگیری برای پیش بینی لینک را براساس محدودیت های شانس پیشنهاد کرده اندو در تمامی مطالعاتی که در زمینه یادگیری باناظر انجام شده است از درخت تصمیم استفاده شده است و روش های دیگر نیز قابل استفاده هستند. [۴۵] ۳-۴- رویکردهای موجود در پیش بینی لینک روش های موجود برای پیش بینی لینک می تواند در سه مقوله گنجانده شود شکل زیر اولی شامل مدل های سنتی)غیربیزین( است که مجموعه ای از ویژگی ها را برای آموزش یک مدل دسته بندی باینری استخراج می کند. در این حالت هر نقطه داده به یک جفت رأس در گراف شبکه اجتماعی مربوط می شود. در اینجا برای هر جفت رأس تصمیم می گیریم که برای آن لینک وجود داشته باشد یا نداشته باشد. از آنجایی که پیش بینی لینک در این حالت تبدیل به یک دسته بندی باینری شده است از همه ابزار رایج دسته بندی بانظارت مثل naive bayes ، شبکه های عصبی، SVM ، k نزدیکترین همسایه و غیره می توان استفاده نمود. مساله اصلی در این رویکرد تعیین ویژگی های مناسب برای دسته بندی است. در این روش برای محاسبه ویژگی های مورد نیاز، تعدادی معیار مجاورت یا شباهت بین دو رأس در شبکه در نظر گرفته و محاسبه می شود و در دسته بندی ها مورد استفاده قرار می گیرد. لیبن ناول و کلین برگ [۱۴] اولین کسانی بودند که این رویکرد را اعمال کردند و شباهت بین یک جفت رأس را با بهره گرفتن از معیارهای مختلف شباهت مبتنی بر گراف استخراج کردند. دومی، رویکردهای احتمالاتی است که احتمال الحاق موجودیت ها در یک شبکه اجتماعی را با بهره گرفتن از مدل های گرافیکی بیزین مدل می کند. ایده اصلی در استفاده از مفاهیم بیزین، بدست آوردن یک احتمال ثانویه است که به شانس اتصال یک جفت رأس که مورد نظر ماست اشاره دارد. مزیت این روش این است که این مقدار خود می تواند به عنوان یک ویژگی مطرح شود. و رویکرد سوم رویکردهای جبرخطی است که شباهت بین ندها در یک شبکه را با بهره گرفتن از ماتریس های شباهت کاهش رتبه محاسبه می کند. این الگوریتم ها روشی را پیشنهاد می دهد که یک تابع F را که مستقیماً روی ماتریس مجاورت یا ماتریس لاپلاسین گراف کار می کند، آموزش می دهد. ویژگی های مورد استفاده در تعیین ویژگی های مورد استفاده در روش های مختلف، در دو گروه قرار می گیرند: گروه اول ویژگی های مبتنی بر مشخصات راس از قبیل سن، شغل، جنسیت، مکان زندگی، محتویات پست ها و اطلاعات به اشتراک گذاشته شده و غیره هستند. گروه دوم ویژگی های مبتنی بر ساختار گراف می باشند. این ویژگی ها شامل دو دسته ویژگی های محلی و سراسری است. ویژگی های محلی دارای مزیت سرعت و ویژگی های سراسری دارای مزیت دقت می باشند. در ادمه هر یک از سه رویکرد بیان شده، شرح داده می شوند.رویکرد های موجود در پیش بینی لینک در شکل ۳-۳ نشان داده شده است. شکل ۳-۳ رویکرد های موجود در پیش بینی لینک ۳-۳-۱- رویکرد مبتنی بر شباهت ساده ترین چارچوب روش های پیش بینی لینک الگوریتم مبتنی بر شباهت است که در آن به هر جفت رأس x و y یک مقدار S که به عنوان مقدار شباهت شناخته می شود، نسبت داده می شود. علی رغم سادگی این روش،مطالعه بر روی الگوریتم های مبتنی بر شباهت اهمیت زیادی پیدا کرده است. در واقع، تعریف شباهت رأس یک موضوع جدی در پیش بینی لینک میان رأس های موجود در شبکه های اجتماعی و هر ساختار گرافی دیگری است.میزان شباهت می تواند بسیار ساده و یا پیچیده باشد و می تواند برای بعضی از شبکه ها خوب کار کند و برای سایر شبکه ها با شکست مواجه شود. شباهت رأس می تواند با بهره گرفتن از ویژگی های اساسی رأس ها تعریف شود و در آن دو رأس شبیه به هم در نظر گرفته می شوند اگر ویژگی های مشترک زیادی داشته باشند. اما این ویژگی ها معمولاً مخفی هستند و باید به طریقی محاسبه شوند. پس از محاسبه معیارها و ویژگی های شباهت بین رئوس، این ویژگی ها به روشی با یکدیگر ترکیب شده و جهت پیش بینی لینک مورد استفاده قرار می گیرند. روش مورد توجه در این رویکرد جهت پیش بینی لینک، دسته بندی باینری لبه هایی است که هنوز تشکیل نشده و رأس های مورد نظر هنوز ارتباطی را ترتیب نداده اند. در این حالت هر یک از نقاط داده به یک جفت رأس در گراف شبکه اجتماعی مربوط می شود. اگر بین جفت رأس مزبور اتصال و ارتباطی برقرار باشد، نقطه داده ای دارای مقدار یک و در غیر این صورت دارای مقدار صفر خواهد بود. بنابراین مسأله اصلی در این رویکرد تعیین معیارهای شباهت و ویژگی های مناسب است. لذا به دنبال ویژگی هایی هستیم که بر اساس آن دسته بندی و در نتیجه پیش بینی را انجام دهیم. استخراج ویژگی ها از گراف شبکه ،معمولاً با دو رویکرد محلی و سراسری صورت می گیرد. روش های محلی که معمولا در شبکه های اجتماعی بر خط مورد استفاده قرار می گیرد، برای محاسبه ویژگی های مورد نیاز مسیرهای با طول۲ را در نظر می گیرند، و از جمله آنها می توان از روش دوست دوست یا دوستان مشترک، آدامیک آدار و ضریب جاکارد را نام برد. در حالی که روش های سراسری برای یافتن میزان شباهت بین دو فرد یا دو رأس کل گراف شبکه را پیمایش می کنند. اگرچه از آنجایی که این روش ها کل اطلاعات شبکه را در نظر می گیرند ممکن است دارای دقت زیادی باشند، ولی بار محاسباتی بالایی دارند و طبیعتاً برای شبکه های اجتماعی برخط مناسب نمی باشند. از جمله روش هایی که مبتنی بر این رویکرد می باشند، معیار کاتز و گام تصادفی با شروع مجدد را می- توان نام برد. علاوه بر این دو رویکرد روش هایی وجود دارند که حالتی میانه را در نظر می گیرند و مسیرهایی بیشتر از طول ۲ را با در نظر گرفتن یک حد آستانه مورد بررسی قرار می دهند. این روش ها می توانند تا حدی از مزیت سرعت روش های محلی و نیز تا حدی از مزیت دقت روش های سراسری را در خود داشته باشند که از جمله آنها می توان روش friendlink را نام برد. علی رغم تفاوت هایی که در محاسبه مقادیر ویژگی ها وجود دارد، آنچه مسلم است ویژگی ها باید نوعی نزدیکی بین جفت رأس ها را نشان دهند و در واقع معیاری برای کشف شباهت بین رئوس شبکه اجتماعی باشند. ۳-۳-۱–۱استخراج ویژگی این بخش اختصاص دارد به ویژگی هایی که از گراف شبکه اجتماعی استخراج شده و مورد استفاده قرار می گیرند. اگر G=(V،E) گرافی باشد که ساختار توپولوژیک شبکه اجتماعی را نشان دهد، هر لبه گراف با نمایش داده می شود که هستند. هدف ما ایجاد یک دسته بندی کننده مناسب با بهره گرفتن از تکنیک های یادگیری ماشین است، به گونه ای که برای هر دو رأس u و v بتواند پیش بینی کند که آیا اتصال بین این دو رأس دارای احتمال بالایی می باشد یا خیر. لذا برای هر لبه کاندید برای دسته بندی ما یک مجموعه از ویژگی های برگرفته از ساختار توپولوژیک شبکه را استخراج کرده ایم.این ویژگی ها به شرح زیر هستند: جدول ۳-۱ ویژگیهای ساختاری مربوط به جفت راس های گراف شبکه های اجتماعی ویژگی های درجه رأس[۸,۱۱] ویژگی های زیر گراف رأس[۱۱] ویژگی دوستان مشترک [۵۵][۲۳] شاخص آدامیک/آدار [۵۶][۲۴]