×

Accurate similarity index based on activity and connectivity of node for link prediction. (English) Zbl 1318.05069

Summary: Recent years have witnessed the increasing of available network data; however, much of those data is incomplete. Link prediction, which can find the missing links of a network, plays an important role in the research and analysis of complex networks. Based on the assumption that two unconnected nodes which are highly similar are very likely to have an interaction, most of the existing algorithms solve the link prediction problem by computing nodes’ similarities. The fundamental requirement of those algorithms is accurate and effective similarity indices. In this paper, we propose a new similarity index, namely similarity based on activity and connectivity (SAC), which performs link prediction more accurately. To compute the similarity between two nodes, this index employs the average activity of these two nodes in their common neighborhood and the connectivities between them and their common neighbors. The higher the average activity is and the stronger the connectivities are, the more similar the two nodes are. The proposed index not only commendably distinguishes the contributions of paths but also incorporates the influence of endpoints. Therefore, it can achieve a better predicting result. To verify the performance of SAC, we conduct experiments on 10 real-world networks. Experimental results demonstrate that SAC outperforms the compared baselines.

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C38 Paths and cycles
05C40 Connectivity
Full Text: DOI

References:

[1] DOI: 10.1002/aris.2007.1440410119 · doi:10.1002/aris.2007.1440410119
[2] DOI: 10.1038/srep07536 · doi:10.1038/srep07536
[3] DOI: 10.1088/1367-2630/16/3/033041 · doi:10.1088/1367-2630/16/3/033041
[4] DOI: 10.1209/0295-5075/97/48001 · doi:10.1209/0295-5075/97/48001
[5] DOI: 10.1073/pnas.0708078105 · doi:10.1073/pnas.0708078105
[6] DOI: 10.1016/S0022-2836(03)00239-0 · doi:10.1016/S0022-2836(03)00239-0
[7] DOI: 10.1145/1117454.1117456 · doi:10.1145/1117454.1117456
[8] DOI: 10.1016/j.physa.2010.11.027 · doi:10.1016/j.physa.2010.11.027
[9] DOI: 10.1209/0295-5075/98/28004 · doi:10.1209/0295-5075/98/28004
[10] DOI: 10.1371/journal.pone.0055437 · doi:10.1371/journal.pone.0055437
[11] DOI: 10.1038/srep01613 · doi:10.1038/srep01613
[12] M. Fire, IEEE Third Int. Conf. Social Computing and Privacy, Security, Risk and Trust SocialCom/PASSAT (IEEE, 2011) pp. 73–80.
[13] F. Xie, Proc. 2014 IEEE/WIC/ACM Int. Joint Conf. Web Intelligence and Intelligent Agent Technologies (IEEE, 2014) pp. 205–212.
[14] DOI: 10.1016/S1389-1286(00)00044-X · doi:10.1016/S1389-1286(00)00044-X
[15] DOI: 10.1007/3-540-46019-5_5 · doi:10.1007/3-540-46019-5_5
[16] M. Bilgic, G. Namata and L. Getoor, Proc. ICDM Workshops (IEEE, 2007) pp. 381–386.
[17] K. Yu, Advances in Neural Information Processing Systems (MIT Press, 2006) pp. 1553–1560.
[18] Hasan M. A., Proc. Workshop on Link Discovery: Issues, Approaches and Applications (2005)
[19] DOI: 10.1145/1835804.1835837 · doi:10.1145/1835804.1835837
[20] DOI: 10.1002/asi.20591 · doi:10.1002/asi.20591
[21] DOI: 10.1080/0022250X.1971.9989788 · doi:10.1080/0022250X.1971.9989788
[22] DOI: 10.1016/S0378-8733(03)00009-1 · doi:10.1016/S0378-8733(03)00009-1
[23] DOI: 10.1103/PhysRevE.80.046122 · doi:10.1103/PhysRevE.80.046122
[24] DOI: 10.1007/BF02289026 · Zbl 0053.27606 · doi:10.1007/BF02289026
[25] DOI: 10.1145/775047.775126 · doi:10.1145/775047.775126
[26] DOI: 10.1209/0295-5075/106/18008 · doi:10.1209/0295-5075/106/18008
[27] DOI: 10.1016/j.jss.2012.04.019 · doi:10.1016/j.jss.2012.04.019
[28] DOI: 10.1177/0165551514560121 · doi:10.1177/0165551514560121
[29] DOI: 10.1140/epjb/e2009-00335-8 · Zbl 1188.05143 · doi:10.1140/epjb/e2009-00335-8
[30] DOI: 10.1142/S0217984913500395 · doi:10.1142/S0217984913500395
[31] Milgram S., Psychol. Today 1 pp 61– (1967)
[32] DOI: 10.1148/radiology.148.3.6878708 · doi:10.1148/radiology.148.3.6878708
[33] DOI: 10.1103/PhysRevE.72.027104 · doi:10.1103/PhysRevE.72.027104
[34] DOI: 10.1073/pnas.122653799 · Zbl 1032.91716 · doi:10.1073/pnas.122653799
[35] DOI: 10.1016/j.physa.2011.12.055 · doi:10.1016/j.physa.2011.12.055
[36] DOI: 10.1142/S0219525903001067 · doi:10.1142/S0219525903001067
[37] DOI: 10.1016/0378-8733(89)90017-8 · doi:10.1016/0378-8733(89)90017-8
[38] DOI: 10.1103/PhysRevE.74.036104 · doi:10.1103/PhysRevE.74.036104
[39] DOI: 10.1016/j.jtbi.2010.11.033 · Zbl 1405.92255 · doi:10.1016/j.jtbi.2010.11.033
[40] DOI: 10.1038/30918 · Zbl 1368.05139 · doi:10.1038/30918
[41] DOI: 10.1103/PhysRevLett.89.208701 · doi:10.1103/PhysRevLett.89.208701
[42] DOI: 10.1209/0295-5075/89/58007 · doi:10.1209/0295-5075/89/58007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.