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

Special Issue: Artificial Intelligence and Pattern Recognition; Data Management and Data Mining

• Special Section on Data Management and Data Mining • Previous Articles     Next Articles

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.

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!
Full text



[1] Li Wanxue;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[2] Wu Yunzeng;. On the Development of Applications of Logic in Programming[J]. , 1987, 2(1): 30 -34 .
[3] Li Renwei;. Soundness and Completeness of Kung s Reasoning Procedure[J]. , 1988, 3(1): 7 -15 .
[4] Min Yinghua;. Guest Editor s Introduction:Fault-Tolerant Computing[J]. , 1990, 5(2): 3 -4 .
[5] Han Jianchao; Shi Zhongzhi;. Formalizing Default Reasoning[J]. , 1990, 5(4): 374 -378 .
[6] Zhuang Nan;. Design of Quaternary ECL Q Gate[J]. , 1991, 6(1): 32 -36 .
[7] Wang Lei; Tan Ying;. The Researches in Fault-Tolerant D ataflow Architecture[J]. , 1991, 6(4): 395 -398 .
[8] Zheng Fangqing;. The Decomposition of Belief Function[J]. , 1992, 7(2): 189 -192 .
[9] Shen Yidong;. Form alizing Incomplete Knowledge in Incomplete Databases[J]. , 1992, 7(4): 295 -304 .
[10] Zhang Bo; Zhang Ling;. On Memory Capacity of the Probabilistic Logic Neuron Network[J]. , 1993, 8(3): 62 -66 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved