Link Prediction in Social Networks | springerprofessional.de

Springer Professional

nach oben

2016 | Buch

Kapitel lesen Erstes Kapitel lesen

Link Prediction in Social Networks

Role of Power Law Distribution

verfasst von: Virinchi Srinivas, Pabitra Mitra

Verlag: Springer International Publishing

Buchreihe : SpringerBriefs in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This work presents link prediction similarity measures for social networks that exploit the degree distribution of the networks. In the context of link prediction in dense networks, the text proposes similarity measures based on Markov inequality degree thresholding (MIDTs), which only consider nodes whose degree is above a threshold for a possible link. Also presented are similarity measures based on cliques (CNC, AAC, RAC), which assign extra weight between nodes sharing a greater number of cliques. Additionally, a locally adaptive (LA) similarity measure is proposed that assigns different weights to common nodes based on the degree distribution of the local neighborhood and the degree distribution of the network. In the context of link prediction in dense networks, the text introduces a novel two-phase framework that adds edges to the sparse graph to forma boost graph.

Anzeige

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

Link prediction deals with predicting new links which are likely to emerge in network in the future, given the network at the current time. It has a wide range of applications including recommender systems, spam mail classification, identifying domain experts in various research areas, etc. In this chapter, we discuss the prior art in link prediction literature.

Virinchi Srinivas, Pabitra Mitra

Chapter 2. Link Prediction Using Thresholding Nodes Based on Their Degree

Abstract

In this chapter, we propose MIDT, a degree threshold-based similarity measure, for link prediction which exploits the power law degree distribution which social networks typically follow. We show that, in power law networks, the number of high-degree common neighbors is insignificant compared to the low-degree common neighbors. We use this property to assign a zero weight to the high-degree common neighbors and a higher weight to the low-degree neighbors in computing similarity between nodes. Experiments on standard benchmark datasets show the superiority of MIDT similarity measure. Specifically, MIDT shows an improvement of upto \(4\,\%\) in terms of AUC when compared to the state-of-the-art link prediction similarity measures.

Virinchi Srinivas, Pabitra Mitra

Chapter 3. Locally Adaptive Link Prediction

Abstract

In this chapter, we address the shortcomings of the existing link prediction similarity measures; every similarity measure assigns the same weight to a node irrespective of the pair of nodes between which the similarity is being computed. In contrast, the weight of a node must depend based on the local neighborhood of the node pair under consideration. In this regard, we propose the Locally Adaptive (LA) similarity measure, a generic similarity measure, which adapts (assigned weight) across different local neighborhoods by assigning different weights to the same node based on the neighborhood. Further, using a smoothening parameter, we can show that the state-of-the-art similarity measures like CN, AA, and RA are specific forms of the proposed similarity measure. Experiments on benchmark datasets show an improvement of upto 6 % using the LA similarity measure when compared to the state-of-the-art link prediction similarity measures.

Virinchi Srinivas, Pabitra Mitra

Chapter 4. Two-Phase Framework for Link Prediction

Abstract

In this chapter, we focus only on link prediction in sparse networks. Link prediction in sparse networks poses a major challenge as link prediction similarity measures perform poorly on sparse networks (Eur. Phys. J. B, 85(1):3, 2012, [2]). Similar work has been done earlier in link prediction in (Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 393–402, 2010, [3]) which they term as “cold start link prediction problem.” The author considers predicting the network structure using available information regarding the nodes when the whole network is missing. In a similar manner, we predict the whole network when the network is evolving and very sparse. Specifically, we propose a two-phase framework to predict links in sparse networks. The generality of our approach makes it feasible to use it along with any link prediction similarity measures. Experiments on benchmark datasets show the superiority of the framework as it shows an improvement of upto \(47\,\%\) in terms of AUC.

Virinchi Srinivas, Pabitra Mitra

Chapter 5. Applications of Link Prediction

Abstract

Link prediction has a wide variety of applications. Graphs provide a natural abstraction to represent interactions between different entities in a network. We can have graphs representing social networks, transportation networks, disease networks, email/telephone calls network to list a few. Link prediction can specifically be applied on these networks to analyze and solve interesting problems like predicting outbreak of a disease, controlling privacy in networks, detecting spam emails, suggesting alternative routes for possible navigation based on the current traffic patterns, etc.

Virinchi Srinivas, Pabitra Mitra

Chapter 6. Conclusion

Abstract

Link prediction problem has been studied extensively in relation to various applications. However, the role of degree distribution of the networks have not been explicitly exploited in this context. In this book, we deal with link prediction by considering the power law degree distribution of large-scale networks. We summarize our key findings and also discuss possible future directions in the context of link prediction.

Virinchi Srinivas, Pabitra Mitra

Backmatter

Titel: Link Prediction in Social Networks
verfasst von: Virinchi Srinivas
Pabitra Mitra
Copyright-Jahr: 2016
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-28922-9
Print ISBN: 978-3-319-28921-2
DOI: https://doi.org/10.1007/978-3-319-28922-9

Premium Partner