توضیحات
ABSTRACT
The problem of link prediction in temporal networks has attracted considerable recent attention from various domains, such as sociology, anthropology, information science, and computer science. In this paper, we propose a fast similarity-based method to predict the potential links in temporal networks. In this method, we first combine the snapshots of the temporal network into a weighted graph. A proper damping factor is used to assign greater importance to more recent snapshots. Then, we construct a sub-graph centered at each node in the weighted graph by a random walk from the node. The sub-graph constructed consists of a set of paths starting from the given node. Because the similarity score is computed within such small sub-graphs centered at each node, the algorithm can greatly reduce the computation time. By choosing a proper number of sampled paths, we can restrict the error of the estimated similarities within a given threshold. While other random walk-based algorithms require O(n3) time for a network with n nodes, the computation time of our algorithm is O(n2), which is the lowest time complexity of a similarity-based link prediction algorithm. Moreover, because the proposed method integrates temporal and global topological information in the network, it can yield more accurate results. The experimental results on real networks show that our algorithm demonstrates the best or comparable quality results in less time than other methods.
INTRODUCTION
Networks can naturally describe various social structures. In such networks, vertices denote individuals, while the edges represent relations among the individuals, such as corporations or companionship. Social network analysis has drawn increasing attention in the fields of sociology, computer science, and physics. It analyzes and explores the potential relations between social objects. Recently, complex network analysis has also drawn much attention in many commerce fields, such as e-business analysis and market modeling. One of the most important research areas in network analysis is link prediction . The objective of link prediction is to forecast prospective links from existing topological information of the network or identify unobserved links from the existing network structure. Link prediction is exploited to identify and categorize the human behavior and activity in social networks. Link prediction can be applied to detect criminals and terrorists via their secret contacts in social security networks. Link prediction is also employed to analyze the trend of changes in sensor networks.
چکیده
مشکل پیش بینی پیوند در شبکه های زمانی، توجه زیادی را از حوزه های مختلف از قبیل جامعه شناسی، انسان شناسی، علوم اطلاعات و علوم رایانه جلب کرده است. در این مقاله، یک روش مبتنی بر شباهت سریع پیشنهاد شده برای پیش بینی پیوندهای احتمالی شبکه های زمانی پیشنهاد می کنیم. در این روش ابتدا تصاویر لحظه ای شبکه شبكه ای را به یک گراف وزن تبدیل می کنیم. برای تعیین اهمیت بیشتر برای عکس های تازه تر مورد استفاده قرار می گیرد. سپس، ما یک نمودار زیر را در هر گره در گراف وزن با یک پیاده روی تصادفی از گره محاسبه میکنیم. زیر گراف ساخته شده شامل مجموعه ای از مسیرهای شروع از گره داده شده است. از آنجا که نمره شباهت در چنین زیر گرافهای کوچک محور در هر گره محاسبه می شود، الگوریتم می تواند زمان محاسبات را بسیار کاهش دهد. با انتخاب تعداد مناسب مسیرهای نمونه، ما می توانیم خطای شباهت های تخمین شده را در یک آستانه معین محدود کنیم. در حالی که دیگر الگوریتم های مبتنی بر پیاده روی تصادفی به زمان O (n3) برای شبکه با n گره نیاز دارند، زمان محاسبه الگوریتم ما O (n2) است، که کمترین زمان پیچیدگی الگوریتم پیش بینی پیوند مبتنی بر شباهت است. علاوه بر این، به دلیل اینکه روش پیشنهادی اطلاعات توپولوژیکی موقتی و جهانی را در شبکه ادغام می کند، می تواند نتایج دقیقتری به دست آورد. نتایج تجربی در شبکه های واقعی نشان می دهد که الگوریتم ما بهترین نتایج یا کیفیت قابل مقایسه را در زمان کمتر از سایر روش ها نشان می دهد.
مقدمه
شبکه ها می توانند به طور طبیعی ساختارهای مختلف اجتماعی را توصیف کنند. در چنین شبکه هایی، رایها افراد را نشان می دهند، در حالی که لبه ها روابط بین افراد را نشان می دهند، مانند شرکت ها یا همراهان. تجزیه و تحلیل شبکه های اجتماعی توجه بیشتری را در زمینه های جامعه شناسی، علوم رایانه و فیزیک افزایش داده است. آن را تجزیه و تحلیل و بررسی روابط بالقوه بین اشیاء اجتماعی است. اخیرا، تجزیه و تحلیل شبکه پیچیده نیز توجه زیادی در بسیاری از زمینه های تجارت مانند تجزیه و تحلیل کسب و کار الکترونیکی و مدل سازی بازار داشته است. یکی از مهمترین زمینه های تحقیق در تحلیل شبکه، پیش بینی ارتباط است. هدف از پیش بینی ارتباط این است که پیش بینی ارتباطات آینده از اطلاعات توپولوژیکی موجود در شبکه را پیش بینی کند یا لینک های ناخواسته را از ساختار شبکه موجود شناسایی کند. پیش بینی پیوند برای شناسایی و طبقه بندی رفتار و فعالیت های انسانی در شبکه های اجتماعی مورد سوء استفاده قرار می گیرد. پیش بینی پیوند می تواند برای شناسایی جنایتکاران و تروریست ها از طریق ارتباطات مخفی خود در شبکه های امنیتی اجتماعی استفاده شود. پیش بینی ارتباط نیز برای تحلیل روند تغییرات در شبکه های حسگر مورد استفاده قرار می گیرد.
Year: 2016
Publisher : ELSEVIER
By : Nahla Mohamed Ahmed , Ling Chen , Yulong Wang , Bin Li , Yun Li ,Wei Liu
File Information: English Language/ 14 Page / size: 1.52 KB
Only site members can download free of charge after registering and adding to the cart
سال : 1395
ناشر : ELSEVIER
کاری از : ناهله محمد احمد، لینگ چن، یولونگ وانگ، بن لی، یون لی، وی لی
اطلاعات فایل : زبان انگلیسی / 14 صفحه / حجم : KB 1.52
نقد و بررسیها
هنوز بررسیای ثبت نشده است.