基于相似度传播的二分网络链接预测

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

摘要/Abstract

摘要： 链接预测是复杂网络分析中的重要研究问题。提出了一个基于链接相似度传播的二部图链路预测算法。该算法将链接相似度得分通过随机游走在网络中进行传播和更新。在该算法中,网络里的每一条边都被分配一个基于相似度的传播概率。不同部分的节点之间的链接相似性得分根据它们的边的传播概率来传播。在不同大小的真实社交网络上的实验结果证明,该算法可以取得比其他算法更精确的预测结果。

关键词: 二分网络,链接预测,随机游走,相似度

Abstract: Link prediction is an important issue in the study of complex analysis. We presented a similarity propagation based link prediction in bipartite networks.The algorithm propagates and updates the link similarity scores by a random walk in the network.In the algorithm,each link in the network is assigned a similarity based on the transmission probability.The link similarity scores between different parts of the nodes are propagated via the links according to their transmission probability.The experimental results on real social networks of varying sizes show that our algorithm can achieve higher quality prediction results than other methods.

Key words: Bipartite network,Link prediction,Random walk,Similarity

姚飞亚,陈崚. 基于相似度传播的二分网络链接预测[J]. 计算机科学, 2016, 43(4): 86-91. https://doi.org/10.11896/j.issn.1002-137X.2016.04.017

YAO Fei-ya and CHEN Ling. Similarity Propagation Based Link Prediction in Bipartite Networks[J]. Computer Science, 2016, 43(4): 86-91. https://doi.org/10.11896/j.issn.1002-137X.2016.04.017

参考文献

[1] Lv L Y,Zhou T.Link prediction in complex networks:A survey[J].Physica A, 2011,390:1150-1170
[2] Ahmed H S,Faouzi B M,Caelen J.Detection and classificationof the behavior of people in an intelligent building by camera[J].International Journal on Smart Sensing and Intelligent Systems,2013,6(4):1317-1342
[3] Yang L T,Wang S,Jiang H.Cyclic Temporal Network Density and its impact on Information Diffusion for Delay Tolerant Networks[J].International Journal on Smart Sensing and Intelligent Systems,2011,4(1):35-52
[4] Liu Z H,Ma J F,Zeng Y.Secrecy transfer for sensor networks:from random graphs to secure random geometric graphs[J].International Journal on Smart Sensing and Intelligent Systems, 2013,6(1):77-94
[5] Jia X,Xin F,Chuan W R.Adaptive spray routing for opportunistic networks[J].International Journal on Smart Sensing and Intelligent Systems,2013,6(1):95-119
[6] Newman M E J.Scientific collaboration networks.I.network con-struction and fundamental results [J].Physical Review E,2001,64:016131
[7] Newman M E J.Scientific collaboration networks.II.Shortest paths,weighted networks,and centrality [J].Physical Review E,2001,64:132-158
[8] 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
[9] Robins G,Alexander M.Small worlds among interlocking directors:network structure and distance in bipartite graphs [J].Computational & Mathematical organization Theory,2004,10:69-94
[10] Battiston S,Catanzaro M.Statistical properties of corporateboard and director networks [J].European Physics Journal B,2004,8:345-352
[11] Chen Wen-qin,Lu Jun-an,Liang Jia.Research in Disease-Gene Network Based on Bipartite Network Projection[J].Complex Systems and Complexity Science,2009,6(1):13-19
[12] Ergun G.Human sexual contact network as a bipartite graph[J].Physica A,2002,8:483-488
[13] Lambiotte R,Ausloos M.Uncovering collective listening habits and music genres in bipartite networks [J].Physical Review E,2005,72:066107
[14] Le Blond S,Guillaume J L,LatapyM.C lustering in P2P exchanges and consequences on performances [M]∥Castro M,Renesse R.Peer- to-Peer Systems IV:Lecture Notes in Computer Scie-nce.Berlin:Heidelberg,2005:193-204
[15] Purnamrita S,Chakrabarti D,Jordan M.Nonparametric link prediction in dynamic networks[C]∥ ICML.2012:1206-6394
[16] Murata T,Moriyasu S.Link Prediction based on Structural Pro-perties of Online Social Networks[J].New Generation Computing,2008,26(3):245-257
[17] Kim H,Tang J,Anderson R,et al.Centrality prediction in dynamic human contact networks[J].Computer Networks,2012,56(3):983-996
[18] Pujari M,Kanawati R.Supervised Rank Aggregation Approach for Link Prediction in Complex Networks[C]∥ WWW 2012 Companion.Lyon,France,2012:1189-1196
[19] Vu D Q,Asuncion A U,Hunter D R,et al.Continuous-time regression models for longitudinal networks,Advances in Neural Information Processing Systems 24[C]∥Proceedings of the 25th Annual Conference on Neural Information Processing Systems.2011:1-9
[20] Bringmann B,Berlingerio M,Bonchi F,et al.Learning and Predicting the Evolution of Social Networks[J].IEEE Intelligent Systems,2010,25(4):26-34
[21] O’Madadhain J,Hutchins J,Smyth P.Prediction and ranking algorithms for event-based network data[C]∥Proceeding of the ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.2005:23-30
[22] Hanneke S,Fu W J,Xing E P.Discrete temporal models of social Networks[J].Electronic Journal of Statistics,2010,4:585-605
[23] Liu Ji,Denga G.Link prediction in a user_object network based on time-weighted resource allocation[J].Physica A,2009,388:3643-3650
[24] Gao S,Denoyer L,Gallinari P.Temporal Link Prediction by Integrating Content and Structure Information[C]∥Glasgow,CIKM’11.Scotland,UK,2011:1169-1174
[25] Potgieter A,April K,Cooke R,et al.Temporality in link prediction:Understanding social complexity[J].Journal of Transactions on Engineering Management,2006,11(1):83-96
[26] Hu F Y,Wong H S.Labelling of Human Motion Based on CBGA and Probabilistic Model[J].International Journal on Smart Sensing and Intelligent Systems,2013(2):583-609
[27] Zhu Jian-han,Hong Jun,Hughes J G.Using Markov Chains for Link prediction in Adaptive Web Sites [C]∥Soft-Ware 2002:Computing in an Imperfect World,LNCS.Vol.2311,April,2002:60-73
[28] Chang Yang-jui,Kao Hung-yu.Link Prediction in a BipartiteNetwork Using Wikipedia Revision Information[C]∥Procee-dings of the 2012 Conference on Technologies and Applications of Artificial Intelligence (TAAI).2012:50-55
[29] Benchettara N,Kanawati R,Rouveirol C.Supervised MachineLearning Applied to Link Prediction in Bipartite Social Networks[C]∥Proceedings of 2010 International Conference on Advances in Social Networks Analysis and Mining (ASONAM).2010:326-330
[30] Xia Shuang,Dai Bing-tian, Lim Ee-peng,et al.Link Predictionfor Bipartite Social Networks:The Role of Structural Holes[C]∥Proceedings of 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM).2012:153-157
[31] 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
[32] Kunegis J,De Luca E W,Albayrak S.The Link Prediction Problem in Bipartite Networks[M]∥Hullermeier E,Kruse R,Hoffmann F,eds.Computeational Intelligence for Knowledge-Based Systems Design:Lecture Notes in Computer Science.2010:380-389
[33] Jeh G,Widom J.SimRank:a measure of structural-context simi-larity[C]∥Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD’02).ACM Press,2002:538-543
[34] Lind P G,Gonzalez M C,Hermann H J.Cycles and clustering in bipartite networks[J].Physical Review E,2005,72(5): 168-191
[35] Kunegis J,De Luca E W,Albayrak S.The link prediction problems in bipartite networks[J].Computational Intelligence for Knowledge-Based System Design,2010,6178:380-389

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed