Impact and enhancement of similarity features on link prediction

doi:10.11772/j.issn.1001-9081.2020111744

Abstract

Abstract: Link prediction focuses on the design of prediction algorithms that can describe a given network mechanism more accurately to achieve the prediction result with higher accuracy. Based on an analysis of the existing research achievements, it is found that the similarity characteristics of a network has a great impact on the link prediction method used. In networks with low tag similarity between nodes, increasing the tag similarity is able to improve the prediction accuracy; in networks with high tag similarity between nodes, more attention should be paid to the contribution of structural information to link prediction to improve the prediction accuracy. Then, a tag-weighted similarity algorithm was proposed by weighting the tags, which was able to improve the accuracy of link prediction in networks with low similarity. Meanwhile, in networks with relatively high similarity, the structural information of the network was introduced into the node similarity calculation, and the accuracy of link prediction was improved through the preferential attachment mechanism. Experimental results on four real networks show that the proposed algorithm achieves the highest accuracy compared to the comparison algorithms Cosine Similarity between Tag Systems (CSTS), Preferential Attachment (PA), etc. According to the network similarity characteristics, using the proposed corresponding algorithm for link prediction can obtain more accurate prediction results.

Key words: complex network, link prediction, tag system, weighted tag, preferential attachment mechanism

摘要： 链路预测的主要任务是设计一个能够更加准确地描述给定网络机制的预测算法，从而得到更准确的预测结果。在分析现有研究成果基础上发现，网络的相似性特征对采用的链路预测方法有较大的影响：在节点间标签相似性较低的网络中，提高标签的相似性可以提高预测的准确性；而在节点间标签相似性较高的网络中，则应更加关注结构信息对于链路预测的贡献来提高预测的准确性。随后，通过对标签进行加权处理，提出带权值的标签相似性算法，在低相似性网络中能够提高链路预测的准确性。同时，在较高相似性网络中，将网络的结构信息引入到节点的相似性计算中，并通过偏好链接机制来提升链路预测的准确性。在四个真实网络上的实验结果表明，所提算法相对于标签系统间的余弦相似性（CSTS）算法、偏好链接（PA）等算法取得了最高的准确率。根据网络相似性特征，采用所提出的对应算法进行链路预测能够得到更准确的预测结果。

关键词: 复杂网络, 链路预测, 标签系统, 带权值标签, 偏好链接机制

CLC Number:

TP391

CAI Biao, LI Ruicen, WU Yuanyuan. Impact and enhancement of similarity features on link prediction[J]. Journal of Computer Applications, 2021, 41(9): 2569-2577.

蔡彪, 李蕊岑, 吴媛媛. 相似性特征对链路预测的影响与增强[J]. 计算机应用, 2021, 41(9): 2569-2577.

References

[1] MALLEK S,BOUKHRIS I,ELOUEDI Z,et al. Evidential link prediction in social networks based on structural and social information[J]. Journal of Computational Science, 2019, 30:98-107.
[2] CAI B,ZENG L N,WANG Y P,et al. Community detection method based on node density,degree centrality,and k-means clustering in complex network[J]. Entropy, 2019, 21(12):No. 1145.
[3] CAI B,WANG Y P,ZENG L N,et al. Edge classification based on convolutional neural networks for community detection in complex network[J]. Physica A:Statistical Mechanics and its Applications,2020,556:No. 124826.
[4] ZHANG H,MING Z,FAN C L,et al. A path-based computational model for long non-coding RNA-protein interaction prediction[J]. Genomics,2020,112(2):1754-1760.
[5] ZHANG B Z,LI J Y,QUAN L J,et al. Sequence-based prediction of protein-protein interaction sites by simplified long short-term memory network[J]. Neurocomputing,2019,357:86-100.
[6] ZAHIRI J,EMAMJOMEH A,BAGHERI S,et al. Protein complex prediction:a survey[J]. Genomics,2020,112(1):174-183.
[7] YASAMI Y,SAFAEI F. A novel multilayer model for missing link prediction and future link forecasting in dynamic complex networks[J]. Physica A:Statistical Mechanics and its Applications,2018, 492:2166-2197.
[8] WANG Z Q,LIANG J Y,LI R. Exploiting user-to-user topic inclusion degree for link prediction in social-information networks[J]. Expert Systems with Applications,2018,108:143-158.
[9] MUNIZ C P, GOLDSCHMIDT R, CHOREN R. Combining contextual,temporal and topological information for unsupervised link prediction in social networks[J]. Knowledge-Based Systems, 2018,156:129-137.
[10] LI S G,YUAN J P,SHI Y,et al. Growing scale-free networks with tunable distributions of triad motifs[J]. Physica A:Statistical Mechanics and its Applications,2015,428:103-110.
[11] 齐鹏飞, 周丽华, 杜国王, 等. 基于聚类的超链路预测[J]. 计算机应用,2020,40(2):434-440.(QI P F,ZHOU L H,DU G W, et al. Clustering-based hyperlink prediction[J]. Journal of Computer Applications,2020,40(2):434-440.)
[12] LI S G,SONG X W,LU H Y,et al. Friend recommendation for cross marketing in online brand community based on intelligent attention allocation link prediction algorithm[J]. Expert Systems with Applications,2020,139:No. 112839.
[13] PAN L M,ZHOU T,LÜ L Y,et al. Predicting missing links and identifying spurious links via likelihood analysis[J]. Scientific Reports,2016,6:No. 22955.
[14] LORRAIN F,WHITE H C. Structural equivalence of individuals in social networks[J]. The Journal of Mathematical Sociology, 1971,1(1):49-80.
[15] ADAMIC L A,ADAR E. Friends and neighbors on the Web[J]. Social Networks,2003,25(3):211-230.
[16] ZHOU T,LÜ L Y,ZHANG Y C. Predicting missing links via local information[J]. The European Physical Journal B:Condensed Matter and Complex Systems,2009,71(4):623-630.
[17] PECH R,HAO D,LEE Y L,et al. Link prediction via linear optimization[J]. Physica A:Statistical Mechanics and its Applications,2019,528:No. 121319.
[18] YAO Y B,ZHANG R S,YANG F,et al. Link prediction in complex networks based on the interactions among paths[J]. Physica A:Statistical Mechanics and its Applications,2018, 510:52-67.
[19] ZHAO J,MIAO L L,YANG J,et al. Prediction of links and weights in networks by reliable routes[J]. Scientific Reports, 2015,5:No. 12261.
[20] CAI B, YANG X W, HUANG Y S, et al. A triangular personalized recommendation algorithm for improving diversity[J]. Discrete Dynamics in Nature and Society,2018,2018:No. 3162068.
[21] HUANG R R,WANG N,HAN C Q,et al. TNAM:a tag-aware neural attention model for Top-N recommendation[J]. Neurocomputing,2020,385:1-12.
[22] LEI K,FU Q A,YANG M,et al. Tag recommendation by text classification with attention-based capsule network[J]. Neurocomputing,2020,391:65-73.
[23] 卜心怡, 陈美灵. 社交网络中的链路预测研究[J]. 图书馆学研究,2016(17):17-21,39.(BU X Y,CHEN M L. Research on link prediction in social networks[J]. Research on Library Science,2016(17):17-21,39.)
[24] SCHIFANELLA R,BARRAT A,CATTUTO C,et al. Folks in Folksonomies:social link prediction from shared metadata[C]//Proceedings of the 3rd ACM International Conference on Web Search and Data Mining. New York:ACM,2010:271-280.
[25] AIELLO L M,BARRAT A,SCHIFANELLA R,et al. Friendship prediction and homophily in social media[J]. ACM Transactions on the Web,2012,6(2):No. 9.
[26] SALTON G,McGILL M J. Introduction to Modern Information Retrieval[M]. New York:McGraw-Hill,1983:402-403.
[27] JACCARD P. Étude comparative de la distribution florale dans une portion des Alpes et des Jura[J]. Bulletin del la Société Vaudoise des Sciences Naturelles,1901,37(142):547-579.
[28] WANG J,ZHANG Q M,ZHOU T. Tag-aware link prediction algorithm in complex networks[J]. Physica A:Statistical Mechanics and its Applications,2019,523:105-111.
[29] LIBEN-NOWELL D, KLEINBERG J. The link-prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology,2007,58(7):1019-1031.
[30] FRIEDMAN N,GEIGER D,GOLDSZMIDT M. Bayesian network classifiers[J]. Machine Learning,1997,29(2/3):131-163.
[31] LEWIS D D. Naive (Bayes) at forty:the independence assumption in information retrieval[C]//Proceedings of the 1998 European Conference on Machine Learning,LNCS 1398. Berlin:Springer,1998:4-15.
[32] LIU Z,ZHANG Q M,LÜ L Y,et al. Link prediction in complex networks:a local naïve Bayes model[J]. EPL (Europhysics Letters),2011,96(4):No. 48007.
[33] WATTS D J,STROGATZ S H. Collective dynamics of'smallworld'networks[J]. Nature,1998,393(6684):440-442.
[34] BARABÁSI A L,ALBERT R. Emergence of scaling in random networks[J]. Science,1999,286(5439):509-512.
[35] LU Q,GETOOR L. Link-based classification[C]//Proceedings of the 20th International Conference on Machine Learning. Palo Alto,CA:AAAI Press,2003:496-503.
[36] SEN P,NAMATA G,BILGIC M,et al. Collective classification in network data articles[J]. AI Magazine,2008,29(3):93-106.
[37] CANTADOR I,BRUSILOVSKY P,KUFLIK T. Second workshop on information Heterogeneity and fusion in Recommender systems (HetRec2011)[C]//Proceedings of the 5th ACM Conference on Recommender Systems. New York:ACM,2011:387-388.
[38] ADAMIC L A,GLANCE N. The political blogosphere and the 2004 U. S. election:divided they blog[C]//Proceedings of the 3rd International Workshop on Link Discovery. New York:ACM, 2005:36-43.
[39] HU J T,ZHANG Q M,ZHOU T. Segregation in religion networks[J]. EPJ Data Science,2019,8:No. 6.
[40] HANLEY J A,McNEIL B J. The meaning and use of the area under a Receiver Operating Characteristic (ROC) curve[J]. Radiology,1982,143(1):29-36.
[41] AGHABOZORGI F,KHAYYAMBASHI M R. A new similarity measure for link prediction based on local structures in social networks[J]. Physica A:Statistical Mechanics and its Applications,2018,501:12-23.