基于Skyline查询的社会网络链接预测

摘要/Abstract

摘要： 在社会媒体中,用户的状态信息实时地更新,用户之间的链接结构也不断改变,这给网络的链接预测提出了严峻的挑战。传统的链接预测方法针对某一特定情景,在非预定情景中效果往往表现不佳。针对单一网路连接预测算法的不足,提出一种基于Skyline查询的社会网络链接预测方法。该算法综合运用多种网络链接预测算法,将其预测值作为被预测链接的属性向量,并将Skyline点作为链接预测的结果返回给用户。实验表明,基于Skyline查询的链接预测方法其准确性明显高于相关链接预测研究的准确性,可应用于实际的社会媒体链接预测和推荐。

关键词: 社会网络,链接预测,Skyline,算法

Abstract: In social media,users update their statues in real time,and the links between them change quickly,which poses a huge challenge for link prediction in such social networks．Traditional link prediction algorithms are usually efficient in specific situations,but for other situations,they are not efficient．In order to deal with the deficiency of single link prediction algorithm,a Skyline query based link prediction approach in social networks was proposed．The algorithm combines multiple link prediction algorithms,assumes the values of these algorithms as a vector of the predicted link,and returns users with the Skyline points based on the calculated vector．Experiments show that the Skyline query based link prediction approach is more efficient than related researches,and can be used in real applications of link pre-dication and recommendation in social media.

Key words: Social networks,Link prediction,Skyline,Algorithm

许烁娜,曾碧卿. 基于Skyline查询的社会网络链接预测[J]. 计算机科学, 2014, 41(1): 258-261. https://doi.org/

XU Shuo-na and ZENG Bi-qing. Skyline Based Link Prediction on Social Networks[J]. Computer Science, 2014, 41(1): 258-261. https://doi.org/

参考文献

[1] Scott J．Social network analysis[M]．SAGE Publications Limited,2012
[2] Liben-Nowell D,Kleinberg J．The link-prediction problem forsocial networks[J]．Journal of the American society for information science and technology,2007,58(7):1019-1031
[3] Boccaletti S,Latora V,Moreno Y,et al．Complex networks:Structure and dynamics[J]．Physics reports,2006,424(4):175-308
[4] Hsu W H,King A,Paradesi M,et al．Collaborative and structural recommendation of friends using weblog-based social network analysis[C]∥AAAI Spring Symposium Series．2006
[5] Yin D,Hong L,Davison B D．Structural link analysis and prediction in microblogs[C]∥Proceedings of the 20th ACM international conference on Information and knowledge management．ACM,2011:1163-1168
[6] Lü L,Zhou T．Link prediction in complex networks:A survey[J]．Physica A:Statistical Mechanics and its Applications,2011,390(6):1150-1170
[7] Newman M E J．Clustering and preferential attachment in gro-wing networks[J]．Phys．Rev．E,2001,64
[8] Salton G,McGill M J．Introduction to Modern Information Retrieval[M]．New York:McDraw-HillCo.,1983:30-42
[9] Srensen T．A method of establishing groups of equal amplitude 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
[10] Zhang Guo-qing,Wang Di,Li Guo-Jie．Enhancing the transmission efficiency by edge deletion in scale-free networks[J]．Phys．Rev．E,2007,76
[11] Ravasz E,Somera A L,Mongru D A, et al.Hierarchical organization of modularity in metabolic networks[J]．Science,2002,297(30):1551-1555
[12] Borzsonyi S,Kossmann D,Stocker K．The skyline operator[C]∥Proc．of the 17th Int’l Conf．on Data Engineering．Heidelberg,IEEE Computer Soci ety Press,2001:421-430
[13] Chebotarev P,Shamis E．The matrix-forest theorem and measuring relations in small social groups[J]．Automation and Remote Control,1997,58(9):1505-1514
[14] Fouss F,Pirotte A,Renders J,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
[15] Lu L,Jin C,Zhou T．Similarity index based on local paths for link prediction of complex networks[J]．Phys．Rev．E,2009,80(4):046122
[16] Liu W,Lu L．Link prediction based on local random walk[J]EPL,2010,89(5):58007
[17] Sales-Pardo M,Guimer`a R,Amaral L A N．Extracting the hierarchical organization of complex systems[C]∥Proc．Natl．Acad．Sci．U.S.A.,2007,104:15224
[18] Airoldi E,Blei D,Fienberg S,et al.Mixed-membership stochastic block models[J]． Machine Learning Research,2008,9:1981-2014
[19] Clauset A,Moore C,Newman M E J．Hierarchical structure and the prediction of missing links in networks[J]．Nature,2008,453:98-101
[20] Friedman N,Getoor L,Koller D,et al.Learning Probabilistic relational models[C]∥Proceedings of the 16th International Joint Conference on Artificial Intelligence．Stockholm,Sweden,1999,1300
[21] Heckerman D,Meek C,Koller D．Probabilistic Entity-Relation-ship Models,PRMs,and Plate Models[C]∥Proceedings of the 21st International Conference on Machine Learning．Banff,Canada,2004,55
[22] Yu K,Chu W,Yu S,et al.Stochastic Relational Models for Discriminative Link Prediction[C]∥Proceedings of Neural Information Processing Systems．Cambridge MA:MIT Press,2006,1553
[23] Wu P,Zhang C,Feng Y,et al.AParallelizing skyline queries for scalable distribution[C]∥Proceedings of the 10th International Conference on Extending Database Technology．Munich,Germany:Springer,2006,112-130
[24] Cosgaya-Lozano A,Rau-Chaplin A,Zeh N．Parallel computation of skyline queries[C]∥Proceedings of the 21st International Symposium on High Performance Computing Sys-tems and Applications．Saskatchewan,Canada:IEEE,2007:12-18
[25] Lee Y W,Lee K Y,Kim M H．Efficient processing of multiple continuous skyline queries over a data stream[J]．Information Sciences,2012,221(1):316-337
[26] Zhang Wen-jin,Lin Xue-min,Zhang Ying,et al．Probabilisticskyline operator over sliding windows[J]．Information Systems,2013,38(8):1212-1233
[27] 王茜,张鲲鹏.隐私保护数据挖掘算法MASK的改进[J].重庆理工大学学报:自然科学版,2012,26(6):63-66

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed