| عنوان فارسی مقاله: |
الگوریتم مبتنی بر نمونه جهت پیش بینی اتصال در شبکه های زمانی |
| عنوان انگلیسی مقاله: |
Sampling-based algorithm for link prediction in temporal networks |
چکیده
مسئله پیش بینی اتصال در شبکه های زمانی توجه زیادی را در زمینه های مختلف از جمله جامعه شناسی، انسان شناسی، علم اطلاعات و علم رایانه به خود جلب نموده است. در این مقاله روش تشابه محور سریع برای پیش بینی اتصال های بالقوه در شبکه های زمانی مطرح می کنیم. در این روش، ابتدا به ترکیب تصاویر کلی شبکه زمانی در گراف وزن دار می پردازیم. عامل مناسب بازدارنده برای تعیین اهمیت بیشتر به تصاویر کلی به کار می رود. سپس گراف فرعی با مرکزیت در هر گره در گراف وز ندار با گام تصادفی از گره ساختاربندی می کنیم. گراف فرعی ساختاربندی شده شامل یک سری مسیرها با شروع از گره داده شده می باشد. چون امتیاز تشابه درون گراف های فرعی کوچک با مرکزیت درون هر گره محاسبه می شود، الگوریتم می تواند به طور زیاد زمان محاسبه را کاهش دهد. با انتخاب تعداد مناسب مسیرهای نمونه گیری شده، می توانیم خطای تشابه برآوردی درون آستانه داده شده محدود کنیم. در حالی که الگوریتم های گام تصادفی دیگر نیاز به( O(n^3 زمان برای شبکه دارای nگره دارد، زمان محاسبه الگوریتم ما برابر ( O(n^2 می باشد که پایین ترین پیچیدگی زمانی الگوریتم پیش بینی اتصال تشابه محور می باشد. علاوه بر این چون روش پیشنهادی اطلاعات مکان شناسی جهانی و زمانی را در شبکه ادغام می کند، آن می تواند نتایج دقیق تری به دست دهد. نتایج آزمایشی در شبکه های حقیقی نشان می دهد که الگوریتم ما نشان دهنده بهترین بوده یا اینکه کیفیت قابل قیاس منجر به زمان کمتر در مقایسه با روش های دیگر می شود.
