Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Learning to Infer Social Ties in Large Networks

  • Conference paper

Abstract

In online social networks, most relationships are lack of meaning labels (e.g., “colleague” and “intimate friends”), simply because users do not take the time to label them. An interesting question is: can we automatically infer the type of social relationships in a large network? what are the fundamental factors that imply the type of social relationships? In this work, we formalize the problem of social relationship learning into a semi-supervised framework, and propose a Partially-labeled Pairwise Factor Graph Model (PLP-FGM) for learning to infer the type of social ties. We tested the model on three different genres of data sets: Publication, Email and Mobile. Experimental results demonstrate that the proposed PLP-FGM model can accurately infer 92.7% of advisor-advisee relationships from the coauthor network (Publication), 88.0% of manager-subordinate relationships from the email network (Email), and 83.1% of the friendships from the mobile network (Mobile). Finally, we develop a distributed learning algorithm to scale up the model to real large networks.

The work is supported by the Natural Science Foundation of China (No. 61073073, No. 60973102), Chinese National Key Foundation Research (No. 60933013, No.61035004).

Similar content being viewed by others

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  1. Albert, R., Barabasi, A.L.: Statistical mechanics of complex networks. Reviews of Modern Physics 74(1) (2002)

    Google Scholar 

  2. Backstrom, L., Leskovec, J.: Supervised random walks: predicting and recommending links in social networks. In: WSDM, pp. 635–644 (2011)

    Google Scholar 

  3. Califf, M.E., Mooney, R.J.: Relational learning of pattern-match rules for information extraction. In: AAAI/IAAI, pp. 328–334 (1999)

    Google Scholar 

  4. Diehl, C.P., Namata, G., Getoor, L.: Relationship identification for social network discovery. In: AAAI, pp. 546–552. AAAI Press, Menlo Park (2007)

    Google Scholar 

  5. Domingos, P., Richardson, M.: Mining the network value of customers. In: KDD, pp. 57–66 (2001)

    Google Scholar 

  6. Eagle, N., Pentland, A.S., Lazer, D.: Mobile phone data for inferring social network structure. In: Social Computing, Behavioral Modeling, and Prediction, pp. 79–88 (2008)

    Google Scholar 

  7. Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In: SIGCOMM, pp. 251–262 (1999)

    Google Scholar 

  8. Getoor, L., Taskar, B.: Introduction to statistical relational learning. The MIT Press, Cambridge (2007)

    MATH  Google Scholar 

  9. Granovetter, M.: The strength of weak ties. American Journal of Sociology 78(6), 1360–1380 (1973)

    Article  Google Scholar 

  10. Grob, R., Kuhn, M., Wattenhofer, R., Wirz, M.: Cluestr: mobile social networking for enhanced group communication. In: GROUP, pp. 81–90 (2009)

    Google Scholar 

  11. Karypis, G., Kumar, V.: MeTis: Unstrctured Graph Partitioning and Sparse Matrix Ordering System, version 4.0 (September 1998)

    Google Scholar 

  12. Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: KDD, pp. 137–146 (2003)

    Google Scholar 

  13. Kleinberg, J.: Temporal dynamics of on-line information streams. In: Data Stream Managemnt: Processing High-Speed Data. Springer, Heidelberg (2005)

    Google Scholar 

  14. Krackhardt, D.: The Strength of Strong Ties: The Importance of Philos in Organizations, pp. 216–239. Harvard Business School Press, Boston

    Google Scholar 

  15. Leskovec, J., Huttenlocher, D.P., Kleinberg, J.M.: Predicting positive and negative links in online social networks. In: WWW, pp. 641–650 (2010)

    Google Scholar 

  16. Liben-Nowell, D., Kleinberg, J.: The link-prediction problem for social networks. JASIST 58(7), 1019–1031 (2007)

    Article  Google Scholar 

  17. Murphy, K., Weiss, Y., Jordan, M.: Loopy belief propagation for approximate inference: An empirical study. In: UAI, vol. 9, pp. 467–475 (1999)

    Google Scholar 

  18. Newman, M.E.J.: The structure and function of complex networks. SIAM Reviews 45 (2003)

    Google Scholar 

  19. Popescul, A., Ungar, L.: Statistical relational learning for link prediction. In: IJCAI 2003 Workshop on Learning Statistical Models from Relational Data, vol. 149, p. 172 (2003)

    Google Scholar 

  20. Roth, M., Ben-David, A., Deutscher, D., Flysher, G., Horn, I., Leichtberg, A., Leiser, N., Matias, Y., Merom, R.: Suggesting friends using the implicit social graph. In: KDD, pp. 233–242 (2010)

    Google Scholar 

  21. Strogatz, S.H.: Exploring complex networks. Nature 410, 268–276 (2003)

    Article  Google Scholar 

  22. Tan, C., Tang, J., Sun, J., Lin, Q., Wang, F.: Social action tracking via noise tolerant time-varying factor graphs. In: KDD, pp. 1049–1058 (2010)

    Google Scholar 

  23. Tang, J., Sun, J., Wang, C., Yang, Z.: Social influence analysis in large-scale networks. In: KDD, pp. 807–816 (2009)

    Google Scholar 

  24. Tang, J., Zhang, J., Yao, L., Li, J., Zhang, L., Su, Z.: Arnetminer: Extraction and mining of academic social networks. In: KDD 2008, pp. 990–998 (2008)

    Google Scholar 

  25. Taskar, B., Wong, M.F., Abbeel, P., Koller, D.: Link prediction in relational data. In: NIPS. MIT Press, Cambridge (2003)

    Google Scholar 

  26. Wang, C., Han, J., Jia, Y., Tang, J., Zhang, D., Yu, Y., Guo, J.: Mining advisor-advisee relationships from research publication networks. In: KDD, pp. 203–212 (2010)

    Google Scholar 

  27. Xiang, R., Neville, J., Rogati, M.: Modeling relationship strength in online social networks. In: WWW, pp. 981–990 (2010)

    Google Scholar 

  28. Xing, E.P., Jordan, M.I., Russell, S.: A generalized mean field algorithm for variational inference in exponential families. In: UAI 2003, pp. 583–591 (2003)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Technology, Tsinghua University, China

    Wenbin Tang, Honglei Zhuang & Jie Tang

Authors
  1. Wenbin Tang

    You can also search for this author inPubMed Google Scholar

  2. Honglei Zhuang

    You can also search for this author inPubMed Google Scholar

  3. Jie Tang

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Informatics and Telecommunications, University of Athens, Panepistimioupolis, Ilisia, 15784, Athens, Greece

    Dimitrios Gunopulos

  2. Google Switzerland GmbH, Brandschenkestrasse 110, 8002, Zurich, Switzerland

    Thomas Hofmann

  3. Department of Computer Science, University of Bari “Aldo Moro”, via Orabona 4, 70125, Bari, Italy

    Donato Malerba

  4. Deptartment of Informatics, Athens University of Economics and Business, Patision 76, 10434, Athens, Greece

    Michalis Vazirgiannis

Rights and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Tang, W., Zhuang, H., Tang, J. (2011). Learning to Infer Social Ties in Large Networks. In: Gunopulos, D., Hofmann, T., Malerba, D., Vazirgiannis, M. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2011. Lecture Notes in Computer Science(), vol 6913. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23808-6_25

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp