›› 2015,Vol. 30 ›› Issue (4): 829-842.doi: 10.1007/s11390-015-1563-9

所属专题: Artificial Intelligence and Pattern Recognition Data Management and Data Mining

• Special Section on Selected Paper from NPC 2011 • 上一篇    下一篇

微博中融合结构和交互信息的链接预测学习

Yan-Tao Jia(贾岩涛), Member, CCF, ACM, Yuan-Zhuo Wang(王元卓), Member, CCF, ACM, IEEE, Xue-Qi Cheng(程学旗), Senior Member, CCF, Member, ACM, IEEE   

  1. Key Laboratory of Network Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
  • 收稿日期:2014-12-02 修回日期:2015-04-11 出版日期:2015-07-05 发布日期:2015-07-05
  • 作者简介:Yan-Tao Jia is an assistant professor at Institute of Computing Technology, Chinese Academy of Sciences (CAS), Beijing. He received his Ph.D. degree in mathematics from Nankai University, Tianjin, in 2012. His main research interests include open knowledge network, social computing, and combinatorial algorithms.
  • 基金资助:

    This work is supported by the National Basic Research 973 Program of China under Grant Nos. 2013CB329602 and 2014CB340405, the National Natural Science Foundation of China under Grant Nos. 61173008, 61232010, 60933005, 61402442, 61402022, and 61303244, Beijing Nova Program under Grant No. Z121101002512063, and the Natural Science Foundation of Beijing under Grant No. 4154086.

Learning to Predict Links by Integrating Structure and Interaction Information in Microblogs

Yan-Tao Jia(贾岩涛), Member, CCF, ACM, Yuan-Zhuo Wang(王元卓), Member, CCF, ACM, IEEE, Xue-Qi Cheng(程学旗), Senior Member, CCF, Member, ACM, IEEE   

  1. Key Laboratory of Network Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
  • Received:2014-12-02 Revised:2015-04-11 Online:2015-07-05 Published:2015-07-05
  • About author:Yan-Tao Jia is an assistant professor at Institute of Computing Technology, Chinese Academy of Sciences (CAS), Beijing. He received his Ph.D. degree in mathematics from Nankai University, Tianjin, in 2012. His main research interests include open knowledge network, social computing, and combinatorial algorithms.
  • Supported by:

    This work is supported by the National Basic Research 973 Program of China under Grant Nos. 2013CB329602 and 2014CB340405, the National Natural Science Foundation of China under Grant Nos. 61173008, 61232010, 60933005, 61402442, 61402022, and 61303244, Beijing Nova Program under Grant No. Z121101002512063, and the Natural Science Foundation of Beijing under Grant No. 4154086.

使用有监督的方法进行微博中链接关系的预测是近几年被广泛研究的问题。它试图找到一个衡量网络中用户间相似度的度量。但是,已有工作中的度量方式没有融合网络的结构信息和用户间的交互信息。这使得链接预测的结果和真实值之间存在着巨大的误差。例如,使用目前最好的无监督方法进行链接预测的F1值大约在0.2左右。在本文中,我们首先发现了该误差并证明了它的存在性。为了缩小这个误差,我们定义了转发相似度来衡量用户间的交互信息,并且提出了基于结构——交互的矩阵分解模型进行关注关系预测。在推特数据集上的实验结果证明了本文提出的模型要优于目前最好的预测方法。

Abstract: Link prediction in Microblogs by using unsupervised methods has been studied extensively in recent years, which aims to find an appropriate similarity measure between users in the network. However, the measures used by existing work lack a simple way to incorporate the structure of the network and the interactions between users. This leads to the gap between the predictive result and the ground truth value. For example, the F1-measure created by the best method is around 0.2. In this work, we firstly discover the gap and prove its existence. To narrow this gap, we define the retweet similarity to measure the interactions between users in Twitter, and propose a structural-interaction based matrix factorization model for following-link prediction. Experiments based on the real world Twitter data show that our model outperforms state-of-the-art methods.

[1] Wasserman S, Faust K. Social Network Analysis: Methods and Applications. Cambridge University Press, Nov. 1994.

[2] Gu Q, Zhou J, Ding C. Collaborative filtering: Weighted nonnegative matrix factorization incorporating user and item graphs. In Proc. SDM, April 29-May 1, 2010, pp.199- 210.

[3] Backstrom L, Leskovec J. Supervised random walks: Predicting and recommending links in social networks. In Proc. the 4th WSDM, Feb. 2011, pp.635-644.

[4] Leskovec J, Huttenlocher D, Kleinberg J. Predicting positive and negative links in online social networks. In Proc. the 19th WWW, Apr. 2010, pp.641-650.

[5] Adamic L, Adar E. Friends and neighbors on the web. Social Networks, 2003, 25(3): 211–230.

[6] Newman M E. Clustering and preferential attachment in growing networks. Phys. Rev. E, 2001, 64(2): Article No. 025102.

[7] Katz L. A new status index derived from sociometric analysis. Psychometrika, 1953, 18(1): 39-43.

[8] Sadilek A, Kautz H, Bigham J P. Finding your friends and following them to where you are. In Proc. the 5th WSDM, Feb. 2012, pp.723-732.

[9] Hopcroft J, Lou T, Tang J.Who will follow you back? Reciprocity relationship prediction. In Proc. the 20th CIKM, Oct. 2011, pp.1137-1146.

[10] Lou T, Tang J, Hopcroft J, Fang Z, Ding X. Learning to predict reciprocity and triadic closure in social networks. ACM Transactions on Knowledge Discovery from Data, 2013, 7(2): 5:1-5:25.

[11] Yin D, Hong L, Davison B D. Structural link analysis and prediction in microblogs. In Proc. the 20th CIKM, Oct. 2011, pp.1163-1168.

[12] Lichtenwalter R, Lussier J, Chawla N. New perspectives and methods in link prediction. In Proc. the 16th KDD, Jul. 2010, pp.243-252.

[13] Akasaka R, Grafe P, Kondo M. ‘Me Too' 2.0: An analysis of viral retweets on the Twittersphere, 2010. http://snap.stanford.edu/class/cs224w- 2010/proj2010/13 projectFinal.pdf, May 2015.

[14] Kwak H, Lee C, Park H, Moon S. What is Twitter, a social network or a news media? In Proc. the 19th WWW, Apr. 2010, pp.591-600.

[15] Koren Y. Factorization meets the neighborhood: A multifaceted collaborative filtering model. In Proc. the 14th KDD, Aug. 2008, pp.426-434.

[16] Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender system. Computer, 2009, 42(8): 30-37.

[17] Zhou T, Shan H, Banerjee A, Sapiroy G. Kernelized probabilistic matrix factorization: Exploiting graphs and side information. In Proc. the 12th SDM, Aug. 2012, pp.403- 414.

[18] Menon A K, Elkan C. Link prediction via matrix factorization. In Proc. ECML PKDD, Sept. 2011, pp.437-452.

[19] Zhang J, Wang C, Wang J, Yu P S. LaFT-tree: Perceiving the expansion trace of one's circle of friends in online social networks. In Proc. WSDM, Feb. 2013, pp.597-606.

[20] Gao S, Denoyer L, Gallinari P. Temporal link prediction by integrating content and structure information. In Proc. the 20th CIKM, Oct. 2011, pp.1169-1174.

[21] Acar E, Dunlavy D, Kolda T. Link prediction on evolving data using matrix and tensor factorizations. In Proc. ICDM Workshops, Dec. 2009, pp.262–269.

[22] Spiegel S, Clausen J, Albayrak S, Kunegis J. Link prediction on evolving data using tensor factorization. In Proc. PAKDD Workshops, May 2011, pp.100-110.

[23] Romero D M, Kleinberg J. The directed closure process in hybrid social-information networks, with an analysis of link formation on Twitter. In Proc. the 4th ICWSM, May 2010.

[24] Salakhutdinov R, Mnih A. Probabilistic matrix factorization. In Proc. the 21st NIPS, Dec. 2007, pp.1257-1264.

[25] Lee D, Seung H S. Algorithms for non-negative matrix factorization. In Proc. NIPS, Nov. 2000, pp.556-562.

[26] Cialdini R B. Influence: Science and Practice. Allyn and Bacon/Pearson, 2001.

[27] Qu Q, Liu S, Jensen C S, Zhu F, Faloutsos C. Interestingness-driven diffusion process summarization in dynamic networks. In Proc. ECML PKDD, Part II, Sept. 2014, pp.597-613.

[28] Yin Z, Gupta M, Weninger T, Han J. LINKREC: A unified framework for link recommendation with user attributes and graph structure. In Proc. the 19th WWW, Apr. 2010, pp.1211-1212.

[29] Liben-Nowell D, Kleinberg J. The link prediction problem for social networks. In Proc. CIKM, Nov. 2003, pp.556-559.

[30] Liu S, Wang S, Zhu F, Zhang J, Krishnan R. HYDRA: Large-scale social identity linkage via heterogeneous behavior modeling. In Proc. SIGMOD, June 2014, pp.51-62.

[31] Jia Y, Wang Y, Li J, Feng K, Cheng X, Li J. Structuralinteraction link prediction in Microblogs. In Proc. the 22nd WWW, May 2013, pp.193-194.

[32] Liu D, Wang Y, Jia Y, Li J, Yu Z. From strangers to neighbors: Link prediction in microblogs using social distance game. In Proc. WSDM, Feb. 2014.

[33] Liu D, Wang Y, Jia Y et al. LSDH: A hashing approach for large-scale link prediction in microblogs. In Proc. the 28th AAAI, July 2014, pp.3120-3121.

[34] Zhao Z, Jia Y, Wang Y, Cheng X. Content-structural relation inference in knowledge base. In Proc. the 28th AAAI, July 2014, pp.3154-3155.

[35] Jia Y, Wang Y, Cheng X, Jin X, Guo J. OpenKN: An open knowledge computational engine for network big data. In Proc. ASONAM, Aug. 2014, pp.657-664.

[36] Jia Y, Wang Y, Jin X, Cheng X. TSBM: The temporalspatial Bayesian model for location prediction in social networks. In Proc. WI-IAT, Aug. 2014, pp.194-201.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 李万学;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[2] 吴允曾;. On the Development of Applications of Logic in Programming[J]. , 1987, 2(1): 30 -34 .
[3] 黎仁蔚;. Soundness and Completeness of Kung s Reasoning Procedure[J]. , 1988, 3(1): 7 -15 .
[4] 闵应骅;. Guest Editor s Introduction:Fault-Tolerant Computing[J]. , 1990, 5(2): 3 -4 .
[5] 韩建超; 史忠植;. Formalizing Default Reasoning[J]. , 1990, 5(4): 374 -378 .
[6] 庄南;. Design of Quaternary ECL Q Gate[J]. , 1991, 6(1): 32 -36 .
[7] 王镭; 谭英;. The Researches in Fault-Tolerant D ataflow Architecture[J]. , 1991, 6(4): 395 -398 .
[8] 郑方青;. The Decomposition of Belief Function[J]. , 1992, 7(2): 189 -192 .
[9] 沈一栋;. Form alizing Incomplete Knowledge in Incomplete Databases[J]. , 1992, 7(4): 295 -304 .
[10] 张钹; 张铃;. On Memory Capacity of the Probabilistic Logic Neuron Network[J]. , 1993, 8(3): 62 -66 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: