پیداکردن کوتاهترین مسیر در شبکه با استفاده از الگوریتم ژنتیک

پیداکردن کوتاهترین مسیر در شبکه با استفاده از الگوریتم ژنتیک

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

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

راهکار پیشنهادی

شبکه مورد نظر به صورت G(V,E) که یک گراف متصل با N گره است نشان داده می شود. متریک بهینه سازی هزینه ی بین گره ها می باشد. هدف یافت کمترین هزینه ی کل بین گره ی مبدأ )که با Vsrc نشان داده می شود( و گره مقصد ) که با Vdes نشان داده می شود( می باشد. در این مقاله بااستفاده از الگوریتم ژنتیک مسیریابی موثری تولید می شود.

مقدار دهی اولیه جدول مسیریابی 

یک ماژول برای تولید تمام مسیرهای ممکن از یک گره ی داده شده، به تمام گره های دیگر درشبکه استفاده می شود)مانند جدول شماره 1 که هزینه لینک های ارتباطی شبکه شکل شماره 1 را نشان می دهد(. در ابتدا “n” مسیر تصادفی در نظر گرفته می شود.کروموزم.این n اندازه جمعیت را تعیین می کند. در این مرحله کروموزم ها به عنوان جمعیت نسل اول عمل می کنند.

تولید مسیرهای بهینه

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

الف(شایستگی هر کروموزم محاسبه می شود. شایستگی به صورت زیر ارزیابی می شود:

  = Fitness تعداد هاپ هایی که در مسیر قراردارد * 10 –هزینه ی کل (جمع هزینه های لینک های جداگانه(

ب) دو کروموزم بهترین به عنوان والد انتخاب می شوند ( انتخاب از طریق متد چرخ رولت انجام می شود(.

پ) کراس اور با احتمال 8 / انجام می شود.

ج)جهش با احتمال 03/ انجام می شود.

د)فرزند در جمعیت قرارداده می شود و کروموزم هایی که شایستگی بسیار ضعیفی دارند از بین می روند.

در غیراینصورت اگر به معیار همگرایی رسیده است مسیر را به مدت T ثانیه ذخیره کرده و داده را به سمت مقصد در طول مسیر ارسال می کنیم.

ن)اگر شرط خاتمه برقرار نشده است مراحل را ن تا  الف تکرار می کنیم.

و) دوباره سازی مسیر بعد از مدت زمان T ثانیه، برای شبکه هایی که پویا هستند

انتخاب

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

کراس اور

عملگر کراس اور از ترکیب دو کروموزم والد، برای تولید فرزندان است. عمل کراس اور به طور عمده می تواند به صورت تک نقطه و چند نقطه باشد.در روش تک نقطه عملیات کراس اور تنها از یک نقطه انجام می شود ولی در چند نقطه، چند مکان جهت عملیات کراس اور در کروموزوم انتخابمی شود. کراس اور تک نقطه ای یک متد ساده است اما برای مسیریابی نمی تواند استفاده شود، زیرا کراس اور تک نقطه ای باعث ایجاد مسیر چرخه می شود.از این رو لازم است برخی تکنیک های پیشرفته چند نقطه کراس اور برای جلوگیری از چرخه استفاده کرد. از جمله این روشها می توان به کراس اور نیمه همسان  PMX 1 کراس اور منظم اشاره نمود OX 2 در این مقاله از روش کراس اور منظم استفاده نموده ایم. کراس اور منظم: با توجه به شکل 2 به شرح اجمالی این روش می پردازیم. ابتدا دو نقطه تصادفی در کروموزم ها انتخاب می شود. سپس ژنهای بین دو نقطه ی انتخابی را در کروموزم های فرزندان، در همان موقعیت کپی می کنیم. از راست ترین نقطه ی تقاطع شروع می کنیم ومقادیر ژنها را از چپ به راست می نویسیم. مثلا رشته ی >9>1>4>2>8>5>7>36 از کرومزوم P1 تولید می شود. برای تولید کروموزم فرزند (O2) اعداد بین دو نقطه ی تصادفی از کروموزم والد P2 را از رشته ی به دست آمده خارج می کنیم. اعداد به رنگ سیاه را از رشته بیرون می کشیم>9>1>4>2>8>5>7>3 6در کروموزم فرزند، ژن های باقی مانده که هنوزمشخص نشده اند را به صورت زیر پر می کنیم خانه های زرد رنگ. اعداد باقی مانده از رشته ی به دست آمده) اعداد به رنگ قرمز را از سمت چپ رشته برداشته و از راست ترین نقطه ی تصادفی از چپ به راست شروع به پر کردن ژن های کروموزم فرزند می کنیم.

جهش

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

شرایط خاتمه الگوریتم

این مرحله میزان همگرایی الگوریتم را تعیین می کند. حداکثر تولید نسل بعدی می تواند وابسته به مقدار تابع شایستگی باشد. همچنین معیار دوم توقف می تواند به میزان تناسب کروموزم ها بستگی داشته باشد.در یک شبکه ممکن است در توپولوژی شبکه، تغییر ایجاد شود و همچنین بعضی از گره ها می توانند به شبکه بپیوندند و یا شبکه را ترک کنند و گره هایی وجود دارند که ممکن است شکست بخورند. تحت این شرایط مسیر بهینه نمی تواند کوتاه ترین مسیر ممکن باشد. لذا باید در شبکه ها در هر T ثانیه مسیرهای جدید تولید شود. هزینه ی لینک هایی که 999 گذاشته شده به معنای این است که بین دو گره هیچ ارتباطی وجود ندارد. 999 در مقایسه با هزینه های دیگر مقداری بزرگ است. شبکه مورد نظر برای کار جاری شامل 6 گره می باشد. ابتدا به طور تصادفی 11 کرموزم ساخته می شودجدول شماره 2. ده کروموزم با شایستگی بالاتر برای نسل اول انتخاب می شوندجدول شماره 3.. در هر نسل کروموزم های معتبرتر و با شایستگی بالاتر به نسل بعدی ارسال می شوند تا به افزایش شایستگی نسل بعدی بیانجامد. ما اندازه جمعیت در نسل اول را 10 در نظر گرفتیم و با استفاده از انتخاب چرخ رولت عملیات GA را روی نسل انجام دادیم.جدول شماره 4 نسل دوم بعد از کراس اور و جهش.. می خواهیم از نود شماره 1 به نود مقصد شماره 6 برویم. در نهایت زیر مجموعه  ای از مسیرها از گره 1 به گره ی 6 تولید می شود.جدول شماره 5

نتیجه گیری

در کار انجام شده پیش رو از الگوریتم ژنتیک برای مسیریابی در شبکه ها برای ارسال بسته ها در شبکه استفاده شده است. ما به دنبال راه حلی بودیم که بتوانیم مسیریابی درشبکه ها بزرگ را بدون داشتن اطلاعات قبلی را انجام دهیم. اگر اندازه و توپولوژی شبکه مدام در حال تغییر باشد این الگوریتم می تواند یک راه حل بهینه باشد. در تحقیقات انجام شده با استفاده از تغییر احتمال کراس اور و جهش و به کار گیری روش OX جهت کراس اورالگوریتم را تحد مطلوبی بهینه سازیم.

منابع

پیداکردن کوتاهترین مسیر در شبکه با استفاده از الگوریتم ژنتیک سمیرا کاتب نواز رازلیقی، علی اکبر تجری سیاه مرزکوه دانشجوی کارشناسی ارشد کامپیوتر، موسسه آموزش عالی میرداماد گرگان -دانشجوی دکتری کامپیوتر، دانشگاه تبریز

یک چارچوب مبتنی بر دانش برای پیش بینی لینک در شبکه های اجتماعی

A Knowledge Based Framework for Link Prediction in Social Networks

Abstract Social networks have a dynamic nature so their structures change over time. In this paper, we propose a new evolutionary method to predict the state of a network in the near future by extracting knowledg from its current structure. This method is based on the fact that social networks consist of communities. Observing current state of a given network, the method calculates the probability of a relationship between each pair of individuals who are not directly connected to each other and estimate the chance of being connected in the next time slot. We have tested and compared the method on one synthetic and one large real dataset with 117 185 083 edges. Results show that our method can predict the next state of a network with a high rate of accuracy

یک چارچوب مبتنی بر دانش برای پیش بینی لینک در شبکه های اجتماعی

چکیده

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

مدل تکاملی پیشنهادی

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

اجزای مدل ارائه شده

ساخت گراف وزن دار

نخست ما به طور خلاصه الگوریتم تکاملی را توصیف می کنیم. در این الگوریتم، هر فرد به عنوان یک راه حل احتمالی را بر اساس یک روش مجاورت و منبع خاص ذخیره شده در ساختاریک آرایه است. طول این آرایه برابر تعداد گره های کل گراف است. هر سلول از این آرایه از 1 تا n (طول آرایه) تعیین کننده یک گره در گراف است . به عنوان مثال، سلول  10 مربوط به گره 10است.اگر یک شبکه دارای 7 گره باشد، یک فرد را می توان به عنوان یک گره از مجموعه ای ازاین گره ها نشان داد که در شکل زیر تعریف شده است.

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

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

شکل 8 به عنوان مثال به روز رسانی فضای باور را نشان می دهد. پنج گره برای به روز رسانی فضای باور انتخاب شده اند که در شکل 4از همان شبکه نشان داده شده است. اگر ماتریس از قبل خالی بود، آن را توسط فراوانی تکرار گره ها و همسایگان خود پر می کنیم. به عنوان مثال، گره  5 به گره1، بیش از20 درصد (یک بار از 5 بار) در ارتباط بوده است. اگر ما این فضای باور را که در شکل زیر نشان داده شده است در نظر بگیریم یک گراف وزن دار جهت دار خواهیم داشت.

محاسبه احتمالات

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

فرض کنید ، G (E V W)، بیانگر ورودی های گراف وزن دار است، که در آن V مجموعه ای از گره ها و E مجموعه ای از یال ها بین هر جفت از گره ها از این رو، هر یک از یا لها E(IJ)  و j i ∈ V علاوه بر اینW مجموعه ای از وزن یال ها باW(IJ)>1 W(J I) 0< است ≤ 1 برای تمام یال هاو  برای هر جفت از گره غیر متصلKI،) جایی که ، K ∈ V و (I، K) / ∈ E، اگر یک گره با J) ∈ V و (I، I)،(J وجود دارد، وزن تخمینی بین i و k به صورت زیر محاسبه :

اگر یک لینک بین دو گره i و k در غیاب گره j وجود دارد، پس, J ,K ) W’(Iرا می توان به عنوان وزن برآورد شده برای هر لینک تفسیر کرد. برای هر مسیر مشابه وزن بر این اساس محاسبه می شود و در نهایت، احتمال رابطه بین گره i و k به صورت زیر قابل محاسبه است:

که در آن n تعداد مسیر بین i و k است.

رتبه بندی احتمالات

پس از محاسبه تمام احتمالات، جفت پیش بینی شده باید بر اساس رتبه بندی احتمالات انتخاب شود. این فرایند در الگوریتم زیر نشان داده شده است:

Algorithm CA-LP (G,A,B,L)

Input:

G: an undirected and unweighted graph, G(V,E)

A: adjacency matrix of G

B: Belief Space matrix

L: desired number of top predicted links

Output:

O: n*n matrix of L probabilities where

O(i,j)=P(i,j), ( i,j are members of V)

Main:

1: Map Belief space to a weighted directed Graph

2: Compute

P(i,k) by extracting weights from B according to

(1) and (2), for all pairs where A(i,k)=0 and A(i,j), A(j,k)=1

3: Store probabilities in a array

4: Sort the array

5: Choose the top-L and store in O where O(i,k)=P(i,k)

منابع

A Knowledge Based Framework for Link Prediction in Social Network Pooya Moradian Zadeh(B) and Ziad Kobti School of Computer Science, University of Windsor, Windsor, ON, Canada moradiap,kobti}@uwindsor.ca

ارائه مدل ترکیبی با استفاده از الگوریتم ژنتیک جهت پیش بینی پیوندها در شبکه اجتماعی

ارائه مدل ترکیبی با استفاده از الگوریتم ژنتیک جهت پیش بینی پیوندها در شبکه اجتماعی

چکیده

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

روش پیشنهادی

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

استخراج ویژگی

مسئله اصلی در این رویکرد تعیین معیارهای شباهت و ویژگیهای مناسب است که بتوان بر اساس آن دسته بندی و درنتیجه پیشبینی پیوند را انجام داد. ویژگیها و معیارهایی که در حوزه مسئله پیشبینی پیوند مطرح هستند، هر یک به عنوان یکی از الگوریتمهای پیشبینی پیوند محسوب میشوند. برای انجام دسته بندی از ویژگی ها معیارهای شباهت محلی گره های یک گراف شبکه اجتماعی استفاده میشود. . به دلیل پیچیدگی زمانی و محاسباتیویژگیهای سراسری، از این ویژگیها استفاده نشده است. تعداد ویژگیهایی که در این تحقیق استفاده میشود، 11 ویژگی است. این ویژگیها معمولاًپنهان هستند و باید محاسبه شوند. محاسبه شباهت بین گرهها، با استفاده از ابزار Matlab انجام میشود.انتخاب ویژگیها از دو جنبه اهمیت پیدا میکند. اولاً انتخاب برخی از ویژگیهابه جای همه آنها زمان انجام دسته بندی را کاهش می دهد. ثانیاً در عمل بسیاری از ویژگیها در افزایش کارایی نقشی نداشته و موجب کاهش کارایی نیز می شوند؛ لذا با شناسایی این ویژگای ها و حذف آنها از عملیات دسته بندی می توان کارایی و دقت روش های دسته بندی را افزایش داد. راهکارهای مختلفی برای انتخاب ویژگی وجود دارد؛ در این تحقیق ازروشهای تکاملی نظیرالگوریتم ژنتیک جهت انتخاب مناسب ترین ویژگی استفاده شده است. برای بهره گیری از این الگوریتم، طول کروموزوم را برابر با تعداد ویژگیهای موجود در نظر گرفته به گونه ای که هر ژن به یکی از  ویژگی های موجود تعلق گیرد. یک بودن هر ژن نشان دهنده شرکت ویژگی مربوطه در دسته بندی و صفر بودن آن، نماینده عدم شرکت آن ویژگی است.پارامترهای تنظیم شده جهت الگوریتم ژنتیک در جدول زیر آمده است.

مدل ترکیبی

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

مقاومتر خواهد شد.برای انجام دسته بندی و ترکیب دسته بندهای پایه از نرم فزار RapidMinerاستفاده می شود.

ارزیابی

به منظور تفکیک داده های آموزشی و آزمایشی از روش 10Fold Cross Validation استفاده شده است. دراین روش کل مجموعه دادهها به 10 قسمت مساوی تقسیم میشوند. از 3 قسمت به عنوان مجموعه داده های آموزشی استفاده میشود و بر اساس آن مدل ساخته میشود و با یک قسمت باقی مانده عملیات ارزیابی انجام می شود. فرآیندمزبور به تعداد 10 مرتبه تکرار خواهد شد، به گونه ای که از هرکدام از 10 قسمت تنها یکبار برای ارزیابی استفاده شده ودر هر مرتبه یک دقت برای مدل ساخته شده، محاسبه میشود. در این روش ارزیابی دقت نهایی دسته بند برابر با میانگین دقت محاسبه شده خواهد بود. بدیهی است که در این شیوه ارزیابی، دقت محاسبه شده برای دسته بند قابل اعتماد بوده و دانش حاصل شده جامع خواهد بود.

مجموعه داده ها

جهت ارزیابی روش پیشنهادی از مجموعه داده های دو شبکه ی اجتماعی واقعی Hi5 و Facebook استفاده شده تاکارایی روش پیشنهادی بررسی شود. مشخصات کامل این مجموعه داده در جدول زیر آمده است.

نتابج حاصل از هر یک دسته بندهای پایه با استفاده از کلیه معیارهای شباهت مطرح شده و به ازای هر یک از مجموعه دادهه ای Facebook و Hi5 در جدول زیر آمده است.

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

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

همانگونه که جدول بالا نشان میدهد با اعمال الگوریتم ژنتیک، AUC حاصل از مدل ترکیبی افزایش یافته است بنابراین ترکیب نتایج سه دسته بند که هر یک به تنهایی نسبت به سایر دسته بندها نتایج بهتر و AUC بالاتری را نتیجه داده اند و بهبود نتیجه نهایی با در نظر گرفتن الگوریتم ژنتیک نشان دهنده کارایی مناسب روش ارائه شده در این تحقیق است.شکل زیر تعداد دفعات استفاده از ویژگیهای مطرح شده در مدل ترکیبی طی 12 بار اجرا را نشان میدهد. معیار دوستان مشترک و معیار سالتون و معیار مجموع وزن دو گره در گراف، 11 بار و معیار ضریب جاکارد و معیار HPI و معیارضریب همبستگی، 10 بار در مدل ترکیبی استفاده شده که این نشان از کارایی خوب این ویژگیها نسبت به سایر ویژگیها در پیش بینی است.

نتیجه گیری

در این مقاله مدلی ارائه شده که با استفاده از روش های یادگیری جمعی نظیرالگوریتم ژنتیک و باترکیب چنددسته بند پایه میتواند مدل تکاملی شبکه را با پیشبینی پیوندهای آتی ، بدست آورد. این مدل با استفاده از مجموعه داده ای دو شبکه اجتماعی Hi5 و Facebook ارزیابی شده است، نتایج نشان داده که روش پیشنهادی می تواند پیوندهای بین موجودیتهای یک شبکه اجتماعی را با دقت و کارایی مناسب پیشبینی نماید که نسبت به دسته بندهای پایه، از کارایی خوبی برخوردار بوده و میتواند دقت پیشبینی را افزایش دهد.در ادامه کار و تحقیقات بعدی میتوان با درنظر گرفتن وزن هر دسته بند در ترکیب، از روش رأی گیری حداکثری وزن دار در ترکیب دسته بندها استفاده نمود تا به نتایج دقیق تری دست یافت.

پیشگویی پیوند در شبکه های اجتماعی با استفاده از ترکیب دسته بندی کننده ها (استفاده از الگوریتم GA وPSO)

پیشگویی پیوند در شبکه های اجتماعی با استفاده از ترکیب دسته بندی کننده ها (استفاده از الگوریتم GA  وPSO™)

چکیده

پیشگویی پیوند در شبکه های اجتماعی یکی از فعالیت های مهم در تحلیل شبکه های اجتماعی است. اهمیت پیشگویی پیونددر شبکه های اجتماعی به دلیل طبیعت دینامیک آن هاست. اعضا و پیوندهای ارتباطی بین آن ها در این شبکه ها مدام در حال افزایش است و این پیوندها ممکن است به دلایل گوناگون از دست برود؛ لذا با پیشگویی این پیوندها امکان گسترش وتکمیل این شبکه ها و بازیابی اطلاعات و موارد از دست رفته را می توان به دست آورد. برای کشف و پیشگویی این پیوندها نیاز به اطلاعاتی است که غالباً از ساختار گرافی شبکه استخراج می شوند و به عنوان معیارهایی برای پیشگویی مورد استفاده قرار می گیرند. در این مقاله پس از معرفی دو معیار جدید که کارایی مؤثری در پیشگویی و نیز ارائۀ پیشنهادات از خود نشان داده اند روش جدیدی ارائه شده است که با ترکیب چند دسدته بندی کننده و با بهره گیدری از روش ها ی تکاملی الگوریتم ژنتیک و الگوریتم رقابت استعماری( عمل پیشگویی پیوند را به انجام می رساند. برای اثبات کار از دو مجموعهEpinions و Facebook استفاده شده است. ما نشان داده ایم که روش پیشدنهاد ی می تواند کار ا یی و دقت پیشگویی را افزایش دهد.

روش مورد استفاده در پیشگویی پیوند

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

دسته بندی برای پیشگویی پیوند

هدف در پیشگویی پیوند، دسته بندی یال هایی که هنوز تشکیل نشده اند، به دو گروه مثبت و منفی است . یال ها ی مثبت یال هایی هستند که احتمال تشکیل آن ها در آینده وجود دارد و یال های منفی یال هایی هستند که براساس پیشگویی صورت گرفته، احتمال ایجاد آن ها وجود ندارد. در این مقاله برای دسته بندی یال ها به دو گروه مثبت و منفی، از ترکیب دسته بندی کننده ها استفاده شده است . برای تکمیل کار وافزایش کارایی و بالا بردن دقت پیشگویی از روش های تکاملی بهره گرفته شده است . دلیل استفاده از ترکیب دسته بندی کننده ها این است که هنگام طراحی یک سیستم یادگیر و ازجمله یک دسته بندی کننده ، انتخابها ی فراوانی وجود دارد. این تنوع انتخاب باعث می شود که نوعی ازواریانس در عملکرد سیستم وجود داشته باشد. درنتیجه اگر سیستم های مختلفی داشته و از نتایج آن ها استفاده شود ، این امکان وجود دارد که توزیع خطا حول هدف متمرکز شده و باافزایش نمونه گیری از این توزیع به نتیجه بهتری برسیم . درواقع به بیان دیگر باید گفت هیچ الگوریتمی وجود ندارد که برای تمامی مسایل و در تمامی زمانها بهترین دقیق ترین یادگیر را به وجود آورد. بنابراین اگر تعدادی یادگیر پایه داشته باشی ، می توان با ترکیب نتایج آن ها به دقت بالاتری رسید.در این کار، از ظرفیت ها ی روشهای تکاملی الگوریتم ژنتیک و الگوریتم رقابت استعماری برای انتخاب در ابعاد مختلف، ترکیب دسته بندی کننده ها استفاده کرده ایم . دلیل استفاده از روش های تکاملی این است که این روشها ، راه حل های مختلفی از یک مسئله را به صورت همزمان بررسی می کنند و خود را به راه حل های خاص یا معیارهای ویژه ای محدود نمی کنند. به همین دلیل می توانند در همۀ شرایط خود را با مسئله وفق دهند و براساس شرایط مسئله پارامترهای خود را تنظیم کرده، پاسخ بهینه را به دست آورند . البته آنچه مسلم است ترکیب دسته بندی کننده هاست که در واقع دسته بندی درچندین مرحله است زمان محاسباتی نسبتاً بالایی خواهد داشت و این نوع روش ها، در کاربردهای برخط از قبیل ارائه پیشنهاد دوست و پیشنهاد کالا چندان مفید فایده نخواهد بود. اما کاربردهای غیربرخط زیادی وجود دارند که دقت و کارایی در آن نسبت به زمان محاسباتی، اهمیتی بسیارتری دارد.ازجمله این کاربردها می توان تشخیص و شناسایی گروه ها ی مجرم و تروریسم را نام برد که اشتباه در تشخیص می تواندهزینه های جبران ناپذیری را بر جامعه تحمیل کند.

روش های تکاملی مورد استفاده در دسته بندی

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

 روش ترکیب دسته بندی کننده ها

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

که در آن N تعداد دسته بندی کننده ها و c تعداد کلاس هاست  zi j خروجی برای کلاس i از دسته بندی کنند j است. wi ضریب وزنی معادل همین خروجی است . ازآنجایی که ما در پیشگویی پیوند با دو کلاس صفر و یک مواجهیم ، دوyمحاسبه می شود. در این روش، خروجی هر دسته بندی کننده رادرz1 و متمم صفر یا یک آن را  در z2قرار می دهیم. کلاس برنده برای هریک از داده ها هریک از یالها کلاسی است که بیشترین مقدار y را دارد. بدین معنی که پس از محاسبۀ yi ها کلاس مورد نظربرابرمقداراندیس y بزر گتر است .

بنابراین مسلم است هه در این قسمت ، مسئله اصلی پیداکردن وزن های wi برای شرکت در ترکیب خطی است. هریک از c دسته بندی کننده که قرار است با یکدیگر ترکیب شوند دارای وزن هایی برای هریک m از کلاس خود هستند. بنابراین m×c وزن داریم که باید به طریقی مقادیر آن رابیابیم . روشی که در این مقاله برای محاسبۀ وزن های مورد نیازاستفاده شده، الگوریتم رقابت استعماری است . در الگوریتم رقابت استعماری که پیش از این شرح داده شد، هر عنصرجمعی یک کشور نامیده می شود که ابعادی به اندازۀ تعداد عناصر مسئله عناصری که به دنبال یافتن آنها هستیم دارد . بنابراین در این روش ، ابعاد هریک از کشورها برابر m×cاست که مقادیر هریک از آن ها بین 25 و 25 - در نظر گرفته شده است . تابع شایستگی در این روش منطق با کارایی نهایی ترکیب دسته بندی کننده ها تعریف، می شود که این کارایی در این قسمت نیز مقدار AUC خروجی است در سایر مقادیر این الگوریتم ، از مقادیر پیش فرض الگوریتم استفاده کرده ایم .پس از این  وزن های مربوط به هریک از دسته بندی کننده هابا استفاده از الگوریتم رقابت استعماری محاسبه شد، باجایگذاری این مقادیر در معادلۀ خطی می تهوان کلاس مربوط به هریک از نمونه های داده ورودی را تعیین کرد.

با توجه به روش پیشنهادی و توضیحات ارائه شده درمقاله، مراحل کار را می توان به صورت زیر خلاصه کرد:

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

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

درجدول زیر نتایج مربوط به دسته بندی داده ها ی مربوط به مجموعه دادۀ Epinionsنشان داده شده است:

نتیجه گیری

یکی از رویکردهای مورد توجه در پیشگویی پیوند، استفاده ازیادگیری با نظارت و انجام پیشگویی در قالب دسته بندی دوتایی است در این رویکرد دو مسئله قابل توجه است : یکی مجموعه ویژگی هایی است که در دسته بندی مورد استفاده قرارمی گیرند و دیگری روش دسته بندی. در این مقاله، از تعدادی از ویژگی های مطرح در پیشگویی پیوند که از ساختارتوپولوژیک گراف شبکه استخراج شده اند، استفاده شده اسهت به علاوه، دو ویژگی جدید نیز معرفی شده و مورد استفاده قرارگرفته است . تجربه نشان داده است که در دسته بندی ها ، دربسیاری موارد می توان با ترکیب چند دسته بندی کننده ، ازمزایای همۀ این دسته بندی کننده ها استفاده کرد و کارایی نهایی را افزایش داد. بنابراین در این مقاله نشان داده شده است که با ترکیب چند دسته بندی کننده که بهترین کارایی را در رابطه با داده های واقعی شبکۀ اجتماعی از خود نشان د اده اند و با بهره گیری از الگوریتم ها و روش های تکاملی، می توان کارایی دسته بندی را افزایش داد و درنتیجه، پیشگویی بهتری را در این شبکه ها انجام داد.

منایع

پیشگویی پیوند در شبکه های اجتماعی با استفاده از ترکیب دسته بندی کننده ها اعظم کی پور مرتضی براری  حسین شیرازی

ارایه روشی جدید برای پیش بینی لینک بین رأس های موجود درشبکه های اجتماعی

چکیده

امروزه شبکه های اجتماعی برخط، به دلیل امکان ایجاد ارتباط بین افراد مختلف درسرتاسر دنیا محبوبیت زیادی دارند. این شبکه های اجتماعی که از امکانا تی مانند پیشنهاد دوست به کاربران برخوردارند، در اغلب موارد برای بیان پیشنهادهای خود، از ویژگی های محلی ساختار گراف شبکه استفاده میکنند. برای بیان پیشنهاد در این شبکه ها، رو شهای مختلفی با دو رویکرد محلی و سراسری پیمایش گراف شبکه پیشنهاد شده و مورد استفاده قرار میگیرد .در این مقاله روشی با رویکرد محلی ارائه شده است که در مقایسه با روش های دیگر، دارای کارایی مناسبی است، علاوه بر اینکه به دلیل محلی بودن رویکرد، از سرعت قابل قبولی برخورداراست. بر اساس ارزیابی ای که روی مجموعه داده های دو شبکه اجتماعی بزرگ Facebook و Epinionsانجام شده است، این ویژگی جدید می تواند پیشگویی خوبی برای یالهایی انجام دهد که قرار است در آینده شکل بگیرند و در نتیجه پیشنهادهای قابل قبولی را ارائه دهد.

مقدمه

شبکه های اجتماعی شبکه های پویایی اند که همواره اعضا و ارتباطات و پیوندهای بین آنها رو به افزایش است. زنجیره این پیوندها گاهی به دلیل فرآیند ایجاد ناقص یا به دلیل اینکه هنوز در این شبکه ها انعکاس نیافته اند (برای مثال، دوستان دنیای واقعی که یک ارتباط اجتماع ی مجاز ی ایجاد نکرده اند)، پاره شده و از دست می روند (فایر و دیگران، 2011 )، لذا یکی از مسائل مهم درشبکه های اجتماعی، مسئله پیش گویی پیوند  است.مسئله پیشگویی، یکی از جنبه های مهم داده کاوی است. داده کاوی پیشگویی کننده، مدلی ازسیستم ارائه می کند که این مدل را مجموعه ای از داد ه های مشخص، پیش بینی می کنند و هدف کلی آن ایجاد الگویی برای طبقه بندی، پیش بینی و تخمین داده ها است. پیشگویی پیوند، به معنای وجود و عدم وجود یک پیوند یا ارتباط در آینده بین دو رأس یک شبکه اجتماعی است و یک ابزار مهم برای تحلیل شبکه های اجتماعی به شمار می رود که کاربردهای زیادی نیز در حوزه های دیگری چون، بازیابی اطلاعات، بایوانفورماتیک و تجارت الکترونیک دارد. به علاوه در حوزة علم وب و اینترنت، می تواند در کارهایی مانند ایجاد ابرپیوند خودکار وب و پیش بینی ابرپیوند سایت های وب کاربرد داشته باشد یکی از مهمترین کاربردهای پیشگویی پیوند در تجارت الکترو نیک ، ایجاد سیستم های پیشنهاد دهنده است. این پیشنهادها می توانند شامل پیشنهاد کالا یا پیشنهاد دوست باشند. ازجمله فواید پیشگویی پیوند اینکه با پیشنهادهای مناسب در زمینة کالا، می توان ضریب خرید اینترنتی افراد جامعه را بالا برد. عمل خرید تحت تأثیر بسیاری از خصایص مشتریان ، مانند ویژگی های شخصیتی، سبک زندگی، دانش و مهارت ها، عوامل اجتماعی، عوامل روانی و عوامل جمعیتی قرار دارد .خرید اینترنتی براساس تجربه واقعی از خرید کالا صورت نمی گیرد، بلکه براساس ظواهری مانند تصویر، شکل، اطلاعات کیفی و تبلیغات از کالا استوار است؛ به همین دلیل جلب اعتماد مشتری برای انجام مبادلات ازطریق اینترنت، مورد توجه بسیاری از سازمان ها و مشتریان قرار گرفته است .یکی از را ههای جلب اعتماد مشتری، به واسطه اعتماد به افرادی حاصل می شود که با وی دریک شبکه اجتماعی در ارتباط بوده و از کالای مورد نظر استفاده می کنند . به همین دلیل ،هم پیوندی به معنی تمایل اعضا برای پیوند و ارتباط با یکدیگر، به منزله ویژگی مهمی برای یکپارچه سازی اطلاعات یاد شده است که موجب پایداری کسب وکارها می شود.در این زمینه پیشگویی پیوند با تحلیل ارتباطات موجود در شبکه های اجتماعی، می تواند فرآیند پیشنهاد کالا و خدمات را تسهیل کند.از جنبه دوست یابی نیز، شبکه های اجتماعی برخطی مانند فیس بوک دارای حجم انبوهی ازداده هستند که می توانند با جست وجو در میان آنها و تحلیل اطلاعات موجود، در این مورد که چه کسی ممکن است بخواهد با دیگری دوست شود، پیشگویی کنند و بر اساس این پیشگویی ها به کاربران پیشنهادهای مناسبی ارائه دهند.ساختار شبکه های اجتماعی، به صورت گرافی مدل می شود که رأس های گراف همان کاربران شبکه هستند و ارتباطات بین این کاربران، یال های گراف را شکل میدهند. برای ارائه پیشنهاد در این شبکه ها دو رویکرد کلی وجود دارد. رویکرد اول که مبتنی بر ویژگی های محلی ساختارگراف شبکه است، روشی است که معمولاً در شبکه های اجتماعی برخط مورد استفاده قرارمی گیرد. این شبکه ها معمولاً پیشگویی های خود را بر اساس تعداد دوستان مشترکی که دو کاربردارند، انجام می دهند؛ زیرا احتمال بسیار زیادی وجود دارد که دو کاربری که دوستان مشترک زیادی دارند، تمایل داشته باشند با یکدیگر چه در دنیای مجازی و چه در دنیای واقعی دوست شوند. اشکالی که به این روش ها وارد است، به در نظر گرفتن حداکثر فاصلة 2 بین هر دو کاربر در گراف شبکه برمی گردد که ممکن است از دقت کافی برخوردار نباشند.در مقابل روش های با رویکرد محلی ، مانند روش دوست  دوست یا دوستان مشترک روش های سراسری نیز وجود دارند که برای یافتن میزان شباهت بین دو فرد ، کل گراف شبکه را پیمایش می کنند. از آنجایی که این روش ها کل اطلاعات شبکه را در نظرمی گیرند، ممکن است از دقت زیادی برخوردار باشند، ولی بار محاسباتی بالایی دارند و طبیعتاً برای شبکه های اجتماعی برخط مناسب نیستند. از جمله رو شهایی که مبتنی بر این رویکردمعیار کاتز گام تصادفی با شروع مجدد نام برد. در این نوشتار روشی ارائه خواهد شد که با استفاده از رویکردی محلی، در تهیه یک معیارجدید برای پیشنهاد دوست و پیشگویی پیوند، در کنار بهره مندی از مزیت سرعت رو شهای محلی، از کارایی مناسبی نسبت به سایر رو شهای موجود، برخوردار است.

روش شناسی پژوهش

معیار آدامیک  آدار ایده مناسبی برای تعیین میزان شباهت کاربران شبکه های اجتماعی ارائه می دهد و توانسته است پیشگویی های خوبی را به انجام رساند. ایده موجود در این معیار این است که اگر همسایه مشترک دو کاربر دوستان کمتری داشته باشد (درجه کمتر) معلوم است گزیده ترانتخاب می کند و احتمال ایجاد ارتباط قوی تری بین دو رأس مورد نظر وجود دارد. لذا به درجه هر یک از همسایگان مشترک، وزن معکوسی داده است تا چنانچه همسایه مشترک دارای درجه بالاتری بود، وجود این همسایه واسطه اثر کمتری بر نتیجه پیشنهادها داشته باشد.نکته گفتنی در این روش، اینکه ممکن است رأس مشترکی که دوستان زیادی دارد، دربسیاری از این دوستان با دو سر ارتباط (دو کاربری که در حال بررسی میزان شباهت آنهاهستیم) اشتراک داشته باشد. به بیان دیگر، داشتن دوستان زیاد برای یک رأس واسطه یک امتیازمنفی محسوب می شود، اما در صورتی که این دوستان، خود دوستان مشترک یکی از دو کاربری باشند که قصد پیشنهاد دوست به آنها را داریم، این تعداد دوستان باید امتیاز مثبت تلقی شود.در این بخش، ما یک معیار تعیین شباهت بین جفت رأس های گراف شبکه پیشنهاد داده ایم که با در نظر گرفتن درجه رأس های میانی و نیز دوستان مشترک رأس میانی با دو رأس اصلی،این میزان شباهت را با توجه به معادله زیر بیان می کند.

که در آن (Cn(u,z تعداد همسایه های مشترک دو رأس z و u است.رابطة بالا برای تعداد بالای دوستان مشترک رأس میانی با دو رأس اصلی، امتیاز مثبت قائل می شود و به همین دلیل، مجموع این تعداد در صورت معادله قرار داده شده است تا میزان شباهت را افزایش دهد. از سوی دیگر، برای درجة رأس میانی امتیاز منفی در نظر گرفته شده ودر مخرج معادله جای می گیرد.در مقایسه هایی که بین این روش و روش های معرفی شده صورت گرفته است، مشاهده می شود که این معیار کارایی قابل قبولی نسبت به روش های دیگر دارد که در ادامه این کارایی اثبات می شود.

یافته های پژوهش

در این بخش الگوریتم پیشنهادی این پژوهش با سیزده ویژگی شرح داده شده، مقایسه می شود وکارایی آن به صورت تجربی اثبات خواهد شد . برای این کار، از دو مجموعه داد ه واقعی Facebook و Epinions استفاده شده است. مجموعه داده های شبکه اجتماعیEpinionsکه یک شبکة اجتماعی به شمار می رود در نظر گرفته شده و از 49 k کاربر و k 487یال بین جفت رأس ها تشکیل شده است مجموعه داده ای Facebook که در 30 اکتبر 2009جمع آوری شده شامل 3/7k کاربر و از  13.7k یال است. برای ارزیابی و مقایسه روش ها و الگوریتم های مختلف پیشگویی پیوند با روش پیشنهادی، از معیار MAP استفاده شده است، تا در بررسی کارایی الگوریتم مورد نظر، روی ترتیب دوستان پیشنهاد داده شده با این رو شها، تأکید بیشتری شود. معادله MAPبه صورت رابطه زیر تعریف می شود:

در این رابطه N تعداد کاربران در مجموعه دادة آزمایشی Rتعداد کاربران مرتبط با کاربر Uمجموعه آزمایشی و precision: مقدار precision در k امین موقعیت فهرست پیشنهادها برای uاست توجه کنید که MAP در واقع هر دو مقدار precisionوrecall را درخود دارد و از نظر هندسی در زیر منحنی precision-recall جای دارد.به منظور ارزیابی روش ها، از هر مجموعه آموزشی به صورتی کاملاً تصادفی، 1000 رأس انتخاب شد و با در نظر گرفتن همه ارتباطات میان آنها، پس از محاسبه و مقایسة مقادیر معیارها، آزمایش های لازم روی آنها انجام گرفت. از آنجایی که با این انتخاب همه رأس ها، حتی رأس هایی که هنوز دوستی ندارند و به اصطلاح افراد تازه وارد این شبکه اجتماعی به شمار میروند نیز انتخاب می شوند، این امکان وجود دارد که در نتایج همه انواع روش های معرفی شده، با دقت پایینی مواجه شویم؛ چراکه این نوع رأس ها، با مشکلی به نام آغاز سرد  برخورد می کنند که یک مشکل رایج در ارائه پیشنهادهای شبکه های اجتماعی محسوب می شود. در این حالت، اطلاعاتی از فرد تازه وارد در دست نیست تا بتوان از این طریق، علایق وی را شناسایی کرد و پیشنهادهای مناسب را به او ارائه داد در شبکه های اجتماعی مشهوری چون Facebook که از روش«  دوست دوست » برای ارائة پیشنهادها استفاده می کنند، این مشکل از راه بررسی اسامی موجود در پست الکترونیکی فرد و تطابق آن با اعضای شبکه اجتماعی و ارائه اسامی تطابق یافته، از بین می رود.در گوگل پلاس نیز برای حل این مشکل، فرد را وادار می کنند که در آغاز ورود به شبکه، ده نفردوست را انتخاب کرده و معرفی کند.برای تفکیک داده های آموزشی و آزمایشی در هر دو مورد از اعتبارسنجی ضربدری ده لایه ای  استفاده شد و الگوریتم ها به کمک زبان نرم افزاری جاوا، به اجرا گذاشته شدند . مقایسه بین الگوریتم های مختلف در رابطه با مجموعه داده ه ای انتخابی و نتایج آن، در جدول 1 نشان داده شده است.

همان طور که در جدول 1 مشاهده می شود، روش جدید در رابطه با مجموعه داده Epinions پس از معیار ضریب خوشه بندی، بهترین جواب را داده است و در مقایسه با سایر معیارها بهتر عمل کرده است. در مورد Facebook نیز به کمک روش پیشنهادی، در مجموع بهترین پاسخ در رابطه با مجموعه دادة انتخابی به دست آمده است؛ در حالیکه در این مجموعه داده، ضریب خوشه بندی دارای کارایی بسیار پایینی بوده است. بنابراین همان گونه که در جدول 1 مشاهده می شود، روش جدید در مورد هر دو مجموعه داده در مقایسه با سایر رو شها، پاسخهای مناسب و قابل قبولی خواهد داشت و پیش بینی های خوبی را ارائه می دهد.

نتیجه گیری  

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

منابع:

ارائة روشی جدید برای پیشگویی پیوند بین رأس های موجود درشبکه های اجتماعی اعظم کی پور مرتضی براری ، حسین شیرازی