Link prediction whose intent is to discover the likelihood of the existence of a link between two disconnected nodes is an important task in complex network analysis. To perform this task, a similarity-based algorithm that employs the similarities of nodes to find links is a very popular solution. However, when calculating the similarity between two nodes, most of the similarity-based algorithms only focus on the contributions of paths connecting these two nodes but ignore the influences of these two nodes themselves. Therefore, their results are not accurate enough. In this paper, a novel similarity index, called Scop, is proposed for link prediction. By directly defining the contributions of paths to their end nodes and the contributions of end nodes themselves, Scop not only distinguishes the contributions of different paths but also integrates the contributions of end nodes. Hence, Scop can obtain better performance on accuracy. Experiments on 10 networks compared with six baselines indicate that Scop is remarkably better than others.
LüLJinC HZhouT. Similarity index based on local paths for link prediction of complex networks. Physical Review E2009; 80(4): 046122.
2.
Von MeringCKrauseRSnelB. Comparative assessment of large-scale data sets of protein-protein interactions. Nature2002; 417(6887): 399–403.
3.
ButtsCT. Network inference, error, and informant (in) accuracy: A Bayesian approach. Social Networks2003; 25(2): 103–140.
4.
GuimeràRSales-PardoM. Missing and spurious interactions and the reconstruction of complex networks. Proceedings of the National Academy of Science2009; 106(52): 22073–22078.
5.
ClausetAMooreCNewmanMEJ. Hierarchical structure and the prediction of missing links in networks. Nature2008; 453(7191): 98–101.
6.
SarukkaiRR. Link prediction and path analysis using markov chains. Computer Networks2000; 33(1): 377–386.
7.
ZhuJHongJHughesJG. Using Markov chains for link prediction in adaptive web sites. In: Soft-Ware 2002: Computing in an imperfect world. Heidelberg: Springer, 2002, pp.60–73.
8.
BilgicMNamataGMGetoorL. Combining collective classification and link prediction. In: Proceedings of the 7th IEEE international conference on data mining workshops. Washington, DC: IEEE Computer Society, 2007, pp. 381–386.
9.
PopesculAUngarLH. Statistical relational learning for link prediction. In: Proceedings of the workshop on learning statistical models from relational data at IJCAI 2003. New York: ACM, 2003, pp. 81–90.
10.
YuKChuWYuS. Stochastic relational models for discriminative link prediction. In: Proceedings of the 2006 neural information processing systems. Vancouver: MIT Press, 2006, pp. 1553–1560.
11.
LüLZhouT. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications2011; 390(6): 1150–1170.
12.
Liben-NowellDKleinbergJ. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology2007; 58(7): 1019–1031.
13.
LorrainFWhiteHC. Structural equivalence of individuals in social networks. The Journal of Mathematical Sociology1971; 1(1): 49–80.
14.
JaccardP. Etude comparative de la distribution florale dans une portion des Alpes et du Jura. Bulletin del la Societe Vaudoise des Sciences Naturelles1901; 37: 547–579.
15.
AdamicLAAdarE. Friends and neighbors on the web. Social Networks2003; 25(3): 211–230.
16.
ZhouTLüLZhangYC. Predicting missing links via local information. The European Physical Journal B – Condensed Matter and Complex Systems2009; 71(4): 623–630.
17.
KatzL. A new status index derived from sociometric analysis. Psychometrika1953; 18(1): 39–43.
18.
JehGWidomJ. SimRank: A measure of structural-context similarity. In: Proceedings of the 8th ACM SIGKDD international conference on knowledge discovery and data mining. New York: ACM, 2002, pp. 538–543.
19.
LiuWLüL. Link prediction based on local random walk. EPL (Europhysics Papers)2010; 89(5): 58007.
20.
PapadimitriouASymeonidisPManolopoulosY. Fast and accurate link prediction in social networking systems. Journal of Systems and Software2012; 85(9): 2119–2132.
21.
Khosravi-FarsaniHNematbakhshMLausenG. SRank: Shortest paths as distance between nodes of a graph with application to RDF clustering. Journal of Information Science2013; 39(2): 198–210.
HanleyJAMcNeilBJ. A method of comparing the areas under receiver operating characteristic curves derived from the same cases. Radiology1983; 148(3): 839–843.
24.
HerlockerJLKonstanJATerveenLG. Evaluating collaborative filtering recommender systems. ACM Transactions on Information Systems2004; 22(1): 5–53.
25.
LüLZhouT. Link prediction in weighted networks: The role of weak ties. EPL (Europhysics Papers)2010; 89(1): 18001.
26.
WattsDJStrogatzSH. Collective dynamics of ‘small-world’ networks. Nature1998; 393(6684): 440–442.
27.
GirvanMNewmanMEJ. Community structure in social and biological networks. Proceedings of the National Academy of Sciences2002; 99(12): 7821–7826.
AdamicLAGlanceN. The political blogosphere and the 2004 US election: Divided they blog. In: Proceedings of the 3rd international workshop on link discovery. New York: ACM, 2005, pp. 36–43.
32.
GleiserPMDanonL. Community structure in jazz. Advances in Complex Systems2003; 6(04): 565–573.
33.
MeliánCJBascompteJ. Food web cohesion. Ecology2004; 85(2): 352–358.
34.
BlagusNŠubeljLBajecM. Self-similar scaling of density in complex real-world networks. Physica A: Statistical Mechanics and its Applications2012; 391(8): 2794–2802.
35.
IsellaLStehléJBarratA. What’s in a crowd? Analysis of face-to-face behavioral networks. Journal of Theoretical Biology2011; 271(1): 166–180.
36.
PageLBrinS. The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, 1999.
37.
NarangKLermanKKumaraguruP. Network flows and the link prediction problem. In: Proceedings of the 7th workshop on social network mining and analysis. New York: ACM, 2013, p. 3.
