Proceedings

Link Label Prediction in Signed Social Networks

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 2591-2596.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

Online social networks continue to witness a tremendous growth both in terms of the number of registered users and their mutual interactions. In this paper, we focus on online signed social networks where positive interactions among the users signify friendship or approval, whereas negative interactions indicate antagonism or disapproval. We introduce a novel problem which we call the link label prediction problem: Given the information about signs of certain links in a social network, we want to learn the nature of relationships that exist among the users by predicting the sign, positive or negative, of the remaining links. We propose a matrix factorization based technique MF-LiSP that exhibits strong generalization guarantees. We also investigate the applicability of logistic regression Leskove et al. in this setting. Our experiments on Wiki-Vote, Epinions and Slashdot data sets strongly corroborate the efficacy of these approaches.

  1. O. Bousquet and A. Elisseeff. Stability and Generaliza- tion. JMLR, 2:499-526, 2002.
  2. E.J. Candès and T. Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. Inform. Theory, 56:2053-2080, 2009.
  3. K.-Y. Chiang, N. Natarajan, A. Tewari, I.S. Dhillon. Ex- ploiting longer cycles for link prediction in signed net- works. In Proceeding of ACM CIKM, pages 1157-1162, 2011.
  4. P. Cui, F. Wang, S. Liu, M. Ou, S. Yang, and L. Sun. Who should share what?: item-level social influence predic- tion for users and posts sign prediction. In SIGIR, 2011.
  5. J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chan- dra. Efficient Projections onto the l 1 -Ball for Learning in High Dimensions. In ICML, 2008.
  6. J. Kunegis, A. Lommatzsch, and C. Bauckhage. The Slashdot zoo: Mining a social network with negative edges. In WWW, pages 740-750, 2009.
  7. J. Leskovec, D. Huttenlocher, and J. Kleinberg. Signed networks in social media. In ACM SIGCHI, pages 1361- 1370, 2010.
  8. J. Leskovec, D. Huttenlocher, and J. Kleinberg. Predict- ing Positive and Negative Links in Online Social Net- works. In WWW, 2010.
  9. D. Liben-Nowell and J.M. Kleinberg. The link predic- tion problem for social networks. Proceedings of the 12th ACM International Conference on Information and Knowledge Management (CIKM), pages 556-559, 2003.
  10. U. Kuter and J. Golbeck. SUNNY: A New Algorithm for Trust Inference in Social Networks Using Probabilistic Confidence Models. In the Proceedings of AAAI, pages 1377-1382, 2007.
  11. H. Ma, D. Zhou, C. Liu, M.R. Lyu, and I. King. Recom- mender Systems with Social Regularization. In WSDM, 2011.
  12. A.K. Menon and C. Elkan. sign prediction via matrix factorization. In ECML PKDD, 2011.
  13. J. Scripps, P.-N. Tan, F. Chen, and A.-H. Esfahanian. A matrix alignment approach for sign prediction. In ICPR, pages 1-4, 2008.
  14. N. Srebro and A. Shraibman. Rank, trace-norm and max-norm. In COLT, pages 545560, 2005.
  15. S.-H. Yang, A.J. Smola, B. Long, H. Zha, and Y. Chang. Friend or frenemy?: predicting signed ties in social net- works. In Proceedings of SIGIR, pages 555-564, 2012.
  16. F. Wang, T. Li, X. Wang, S. Zhu, and C. Ding. Com- munity discovery using nonnegative matrix factorization. Data Mining and Knowledge Discovery, 22(3):493-521, 2011.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards