基于投影的二分网络链接预测

doi:10.11896/j.issn.1002-137X.2016.02.027

摘要/Abstract

摘要： 提出基于投影的二部网络链接预测算法。算法首先将二部图投影为一个单部图,在此基础上定义了潜在边的概念,使得对二分网络链接的预测仅在潜在边中进行,大大降低了预测算法的复杂度。定义了潜在边所覆盖的模式以及模式的权重,通过潜在边所覆盖的模式的权重来计算潜在边的可信度,并将其作为该潜在边上存在实际链接的评分。实验结果表明,所提算法能够有效地提高链接预测的速度和结果的精度。

关键词: 二部网络,链接预测,投影,潜在边

Abstract: An algorithm for link prediction in a bipartite network was presented.In the algorithm we first mapped the bipartite network to unipartite one called projected graph.Based on the projected graph,we defined the concept of potential link.We performed the link prediction only within the potential links so as to reduce the computation time.We also defined the pattern covered by the potential links and the weight of the patterns.By calculating the weight of the patterns a potential link covers,the confidence of the potential link can be obtained,which can be used as the final score of link prediction.Experimental results show that our algorithm can get faster speed and higher quality of link prediction results.

Key words: Bipartite network,Link prediction,Projection,Internal links

高曼,陈崚,徐永成. 基于投影的二分网络链接预测[J]. 计算机科学, 2016, 43(2): 118-123. https://doi.org/10.11896/j.issn.1002-137X.2016.02.027

GAO Man, CHEN Ling and XU Yong-cheng. Projection Based Algorithm for Link Prediction in Bipartite Network[J]. Computer Science, 2016, 43(2): 118-123. https://doi.org/10.11896/j.issn.1002-137X.2016.02.027

参考文献

[1] Ryan N.Lichtenwalter,New precepts and method in link prediction[C]∥Proceedings of ACM KDD’10.2010:243-252
[2] Lv Lin-yuan,Zhou Tao.Link predication in complex networks:A survey[J].Physica A,2011,0:1150-1170
[3] Lv Lin-yuan.Link prediction on complex networks[J].Journal of University of Electronic Science and Technology of China,2010,9(5):651-661(in Chinese) 吕琳媛.复杂网络链路预测[J].电子科技大学学报,2010,39(5):651-661
[4] Zhang L,Hu K,Tang Y.Predicting Disease-related Genes byTopological Similarity in Human Protein-protein Interaction Network[J].Central European Journal of Physics,2010,8(4):672-682
[5] Guimera R,Sales-Pardo M.Missing and Spurious Interactionsand the Reconstruction of Complex Networks[J].Proceedings of the National Academy of Science,USA, 2010,106(52):22073-22078
[6] Papadimitriou A,Symeonidis P,Manolopoulos Y.Fast and accurate link prediction in social networking systems[J].Journal of Systems and Software,2012,85(9):2119-2132
[7] Hossmann T,Nomikos G,Spyropoulos T,et al.Collection and analysis of multi-dimensional network data for opportunistic networking research[J].Computer Communications,2012,5(13):1613-1625
[8] Jahanbakhsh K,King V,Shoja G C.Predicting missing contacts in mobile social networks[J].Pervasive and Mobile Computing,2012,8(5):698-716
[9] Sun Y,Barbery R,Gupta M,et al.Co-Author Relationship Prediction in Heterogeneous Bibliographic Networks[C]∥Procee-dings of 2011 International Conference on Advances in Social Networks Analysis and Mining(ASONAM 2011).2011:121-128
[10] Li Xin,Chen Hsin-chun.Recommendation as link prediction in bipartite graphs:A graph kernel-based machine learning approach[J].Decision Support Systems,2013,54(2):880-890
[11] Huang Z,Lin D K J.The time-series link prediction problem with applications in communication surveillance[J].INFORMS J.on Computing.2009,21:286-303
[12] Liu H K,Lv L Y,Zhou T.Uncovering the network evolutionmechanism by link prediction[J].Sci.Sin.Phys Mech & Astron,2011,1(7):816-823(in Chinese) 刘宏鲲,吕琳媛,周涛.利用链路预测推断网络演化机制[J].中国科学:物理学力学天文学,2011,41(7):816-823
[13] Salton G,Mcgill M J.Introduction to modern information re-trieval[M].Auckland:MuGraw-Hill,1983
[14] Jaccard P.Etude comparative de la distribution florale dans une portion des Alpes et des Jura[J].Bulletin de la Société Vaudoise des Science Naturelles,1901,37:547-579
[15] Sorensen T.A method of establishing groups of equalamplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons[J].Biol Skr,1948,5(4):1-34
[16] Ravasz E,Somera A L,Mongru D A,et al.Hierarchical organization of modularity in metabolic networks[J].Science,2002,297(5586):1553-1555
[17] Leicht E A,Holme P,Newman M E J.Vertex similarity in networks[J].Phys Rev E 73,2006,73:026120
[18] Barabasi A-L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512
[19] Adamic L A,Adar E.Friends and neighbors on the web[J].Social Networks,2003,25(3):211-230
[20] Zhou T,Lv L,Zhang Y C.Predicting missing links via local information[J].Eur Phys J B,2009,71(4):623-630
[21] Lv L,Jin C H,Zhou T.Similarity index based on local paths for link prediction of complex networks[J].Phys Rev E,2009,80:046122
[22] Katz L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43
[23] Klein D J,Randic M.Resistance distance[J].J Math Chem,1993,12(1):81-95
[24] Fouss F,Pirotte A,Renders J M,et al.Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J].IEEE Trans Knowl Data Eng,2007,19(3):355-369
[25] Brin S,Page L.The anatomy of a large-scale hypertextual Web search engine[J].Comput Netw & ISDN Syst,1998,30(1-7):107-117
[26] Jeh G,Widom J.SimRank:A measure of structural context similarity[C]∥Proceedings of the ACM SIGKDD 2002.New York:ACM Press,2002:538-543
[27] Zhou T,Lv L,Zhang Y-C.Predicting missing links via local information[J].European Physical Journal B,2009,71(4):623-630
[28] Lv L,Jin C-H,Zhou T.Similarity index based on local paths for link prediction of complex networks[J].Physical Review E-Statistical,Nonlinear,and Soft Matter Physics,2009,80(4):046122
[29] Liu W-P,Lv L.Link Prediction Based on Local Random Walk[J].European Physics Letter.,2010,89(5):58007
[30] Rao Jun,Wu Bin,Dong Yu-xiao.Parallel Link Prediction inComplex Network Using MapReduce[J].Journal of Software,2012,3(12):3175-3186(in Chinese) 饶君,吴斌,东昱晓.MapReduce环境下的并行复杂网络链路预测[J].软件学报,2012,23(12):3175-3186
[31] Dong Yu-xiao,Ke Qing,Wu Bin.Link Prediction Based on Node Similarity[J].Computer Science,2011,8(7):162-164(in Chinese) 东昱晓,柯庆,吴斌.基于节点相似性的链接预测[J].计算机科学,2011,38(7):162-164
[32] http://www.linkprediction.org/index.php/link/resource/data
[33] Latora V,Marchiori M.Efficient behavior of small-world net-works[J].Phys.Rev.Lett.,2001,67:198701-198704
[34] Watts D J,Strogatz S.Collective dynamics of ‘small-world’ networks[J].Nature.,1998,393(6684):440-442
[35] Newman M E J.Assortative mixing in networks[J].Phys.Rev.Lett.,2002,9(20):208701-208705
[36] Newman M E J.Scientific collaboration networks.I.networkconstruction and fundamental results [J].Physical Review E,2001,64:0161311-061317
[37] Newman M E J.Scientific collaboration networks.II.Shortestpaths,weighted networks,and centrality [J].Physical Review E,2001,64:0161321-0161327
[38] Liu Ai-fen,Fu Chun-hua,Zhang Zeng-ping,et al.An Empirical Statistical Investigation on Chinese Mainland Movie Network[J].Complex Systems and Complexity Science,2007,4(3):10-16
[39] Robins G,Alexander M.Small worlds among interlocking directors:network structure and distance in bipartite graphs [J].Computational & Mathematical organization Theory,2004,0(1):69-94
[40] Battiston S,Catanzaro M.Statistical properties of corporateboard and director networks [J].European Physics Journal B,2004,8(2):345-352
[41] Chen Wen-qin,Lu Jun-an,Liang Jia.Research in Disease-Gene Network Based on Bipartite Network Projection[J].Complex Systems & Complexity Science,2009,6(1):13-19
[42] Ergun G.Human sexual contact network as a bipartite graph[J].Physica A,2002,8(1-4):483-488
[43] Lambiotte R,Ausloos M.Uncovering collective listening habits and music genres in bipartite networks [J].Physical Review E,2005,72(6):066107
[44] Le Blond S,Guillaume J L,Latapy M.Clustering in P2P exchanges and consequences on performances[C]∥Castro M,Renesse R,eds.Peer-to-Peer Systems IV.Berlin:Heidelberg,2005,193-204

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed