Elimination based algorithm for link prediction on social networks

被引：6

作者：

Sharma U. ^{[1
]}

Sharma D. ^{[1
]}

Khatri S.K. ^{[1
]}

机构：

[1] Amity Institute of Information Technology, Amity University Uttar Pradesh, Noida, UP

来源：

International Journal of System Assurance Engineering and Management | 2015年 / 6卷 / 01期

关键词：

Algorithms; Link prediction; Social networks;

D O I：

10.1007/s13198-014-0245-2

中图分类号：

学科分类号：

摘要：

Link prediction is a very well studied problem as it has applications in different areas. Many algorithms have been presented in the literature for link prediction problem. The link prediction problem can be explained as follows: given the topology of graph G at a certain time t, we need to predict the topology of the graph at time t′ where t′ > t. The techniques used for link prediction are categorized as follows: nodes based techniques, Link based techniques and path based techniques. There are some other techniques that use meta-approaches. In this paper we present a new algorithm for link prediction on social networks. The algorithm tries to identify nodes that may get deleted by time t′ and use this information to predict new links that might appear in the future. Our tests show that our algorithm shows better result for link prediction on social networks compared to the previous algorithms. We had implemented our algorithm in C# on Pentium Core 2 Duo processor. The data used for testing is Gnutella peer to peer network. © 2014, The Society for Reliability Engineering, Quality and Operations Management (SREQOM), India and The Division of Operation and Maintenance, Lulea University of Technology, Sweden.

引用

页码：78 / 82

页数：4

共 12 条

[1]

Adamic L.A., Adar E., Predicting missing links via local information, Soc Netw, 25, 3, pp. 211-230, (2003)

[2]

Brin S., Page L., The anatomy of a large-scale hyper textual Web search engine, Comput Netw ISDN Syst, 30, (1998)

[3]

Fouss F., Pirotte A., Renders J.-M., Saerens M., A link analysis extension of correspondence analysis for mining relational databases, IEEE Trans Knowl Data Eng, 19, (2007)

[4]

Gobel F., Jagers A., Random walks on graphs, Stoch Process Appl, 2, 4, pp. 311-336, (1974)

[5]

Jaccard P., Etude comparative de la distribution florale dans une portion des Alpes et du Jura, Bulletin de la Societe Vaudoise des Science Naturelles, 37, (1901)

[6]

Jeh G., Widom J., A measure of structural context similarity, In: Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining, (2002)

[7]

Katz L., A new status index derived from socia matric analysis, Psychometrika, 18, 1, pp. 39-43, (1953)

[8]

Leskovec J., Kleinberg J., Faloutsos C., Graph evolution: densification and shrinking diameters, ACM Trans Knowl Discov Data, 1, 1, (2007)

[9]

Liu W., Lu L., Link prediction based on local random walk, Europhys Lett, 89, 5, (2010)

[10]

Newman M.E.J., Clustering and preferential attachment in growing networks, Phys Rev Lett E, 64, (2001)

← 1 2 →