Learning to predict reciprocity and triadic closure in social networks

Abstract

We study how links are formed in social networks. In particular, we focus on investigating how a reciprocal (two-way) link, the basic relationship in social networks, is developed from a parasocial (one-way) relationship and how the relationships further develop into triadic closure, one of the fundamental processes of link formation.

We first investigate how geographic distance and interactions between users influence the formation of link structure among users. Then we study how social theories including homophily, social balance, and social status are satisfied over networks with parasocial and reciprocal relationships. The study unveils several interesting phenomena. For example, “friend's friend is a friend” indeed exists in the reciprocal relationship network, but does not hold in the parasocial relationship network.

We propose a learning framework to formulate the problems of predicting reciprocity and triadic closure into a graphical model. We demonstrate that it is possible to accurately infer 90% of reciprocal relationships in a Twitter network. The proposed model also achieves better performance (+20--30% in terms of F1-measure) than several alternative methods for predicting the triadic closure formation.

References

1. Backstrom, L., Kumar, R., Marlow, C., Novak, J., and Tomkins, A. 2008. Preferential behavior in online groups. In Proceedings of the International Conference on Web Search and Data Mining (WSDM'08). 117--128.
2. Backstrom, L. and Leskovec, J. 2011. Supervised random walks: Predicting and recommending links in social networks. In Proceedings of the International Conference on Web Search and Data Mining (WSDM'11). 635--644.
3. Cha, M., Haddadi, H., Benevenuto, F., and Gummadi, P. K. 2010. Measuring user influence in twitter: The million follower fallacy. In Proceedings of the AAAI International Conference on Weblogs and Social Media (ICWSM'10).
4. Crandall, D. J., Backstrom, L., Cosley, D., Suri, S., Huttenlocher, D., and Kleinberg, J. 2010. Inferring social ties from geographic coincidences. Proc. Nat. Acad. Sci. United States 107, 22436--22441.
5. Diehl, C. P., Namata, G., and Getoor, L. 2007. Relationship identification for social network discovery. In Proceedings of the 22^nd National Conference on Artificial Intelligence (AAAI'07). 546--552.
6. Eagle, N., Pentland, A. S., and Lazer, D. 2009. Inferring social network structure using mobile phone data. Proc. Nat. Acad. Sci. United States 106, 36.
7. Easley, D. and Kleinberg, J. 2010. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press.
8. Hammersley, J. M. and Clifford, P. 1971. Markov field on finite graphs and lattices.
9. He, J., Hopcroft, J., Liang, H., Suwajanakorn, S., and Wang, L. 2011. Detecting the structure of social networks using (α, β)-communities. In Proceedings of the 8^th International Conference on Algorithms and Models for the Web Graph (WAW'11).
10. Hopcroft, J., Lou, T., and Tang, J. 2011. Who will follow you back? Reciprocal relationship prediction. In Proceedings of the 20^th ACM International Conference on Information and Knowledge Management (CIKM'11). 1137--1146.
11. Horton, D. and Wohl, R. R. 1956. Mass communication and para-social interaction: Observations on intimacy at a distance. Psychiatry 3, 1, 215--229.
12. Huberman, B., Romero, D. M., and Wu, F. 2009. Social networks that matter: Twitter under microscope. First Monday 14, 118--138.
13. Java, A., Song, X., Finin, T., and Tseng, B. L. 2007. Why we twitter: An analysis of a microblogging community. In Proceedings of the 9^th International Workshop on Knowledge Discovery on the Web and the 1^st International Workshop on Social Networks Analysis (WebKDD/SNA-KDD'07). 118--138.
14. Katz, L. 1953. A new status index derived from sociometric analysis. Psychometrika 18, 1, 39--43.
15. Kwak, H., Lee, C., Park, H., and Moon, S. B. 2010. What is twitter, a social network or a news media? In Proceedings of the 19^th International Conference on World Wide Web (WWW'10). 591--600.
16. Lafferty, J. D., Mccallum, A., and Pereira, F. C. N. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the 18^th International Conference on Machine Learning (ICML'01). 282--289.
17. Lazarsfeld, P. F. and Merton, R. K. 1954. Friendship as a social process: A substantive and methodological analysis. In Freedom and Control in Modern Society, M. Berger, T. Abel, and C. H. Page, Eds., Van Nostrand, New York, 8--66.
18. Leskovec, J., Huttenlocher, D., and Kleinberg, J. 2010. Predicting positive and negative links in online social networks. In Proceedings of the 19^th International Conference on World Wide Web (WWW'10). 641--650.
19. Liben-Nowell, D. and Kleinberg, J. M. 2007. The link-prediction problem for social networks. JA-SIST 58, 7, 1019--1031.
20. Lichtenwalter, R., Lussier, J. T., and Chawla, N. V. 2010. New perspectives and methods in link prediction. In Proceedings of the 16^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'10). 243--252.
21. Mathioudakis, M. and Koudas, N. 2010. Twittermonitor: Trend detection over the twitter stream. In Proceedings of the International Conference on Management of Data (SIGMOD'10). 1155--1158.
22. Murphy, K. P., Weiss, Y., and Jordan, M. I. 1999. Loopy belief propagation for approximate inference: An empirical study. In Proceedings of the 15^th Conference on Uncertainty in Artificial Intelligence (UAI'99). 467--475.
23. Newman, M. E. J. 2001. Clustering and preferential attachment in growing networks. Phys. Rev. E64, 2, 25--102.
24. Page, L., Brin, S., Motwani, R., and Winograd, T. 1999. The pagerank citation ranking: Bringing order to the web. Tech. rep. SIDL-WP-1999-0120, Stanford University.
25. Romero, D. M. and Kleinberg, J. M. 2010. The directed closure process in hybrid social-information networks, with an analysis of link formation on twitter. In Proceedings of the AAAI International Conference on Weblogs and Social Media (ICWSM'10).
26. Sakaki, T., Okazaki, M., and Matsuo, Y. 2010. Earthquake shakes twitter users: Real-time event detection by social sensors. In Proceedings of the 19^th International Conference on World Wide Web (WWW'10). 851--860.
27. Tan, C., Lee, L., Tang, J., Jiang, L., Zhou, M., and Li, P. 2011. User-level sentiment analysis incorporating social networks. In Proceedings of the 17^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'11). 1397--1405.
28. Tan, C., Tang, J., Sun, J., Lin, Q., and Wang, F. 2010. Social action tracking via noise tolerant timevarying factor graphs. In Proceedings of the 16^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'10). 1049--1058.
29. Tang, J., Lou, T., and Kleinberg, J. 2012a. Inferring social ties across heterogeneous networks. In Proceedings of the 5^th ACM International Conference on Web Search and Data Mining (WSDM'12). 743--752.
30. Tang, J., Sun, J., Wang, C., and Yang, Z. 2009. Social influence analysis in large-scale networks. In Proceedings of the 15^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'09). 807--816.
31. Tang, J., Wu, S., Sun, J., and Su, H. 2012b. Cross-domain collaboration recommendation. In Proceedings of the 18^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'12).
32. Tang, W., Zhuang, H., and Tang, J. 2011. Learning to infer social ties in large networks. In Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases (ECML/PKDD'11). 381--397.
33. Wang, C., Han, J., Jia, Y., Tang, J., Zhang, D., Yu, Y., and Guo, J. 2010. Mining advisor-advisee relationships from research publication networks. In Proceedings of the 16^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'10). 203--212.
34. Wang, C., Satuluri, V., and Parthasarathy, S. 2007. Local probabilistic models for link prediction. In Proceedings of the 7^th IEEE International Conference on Data Mining (ICDM'07). 322--331.
35. Weber, M. 1991. The Nature of Social Action in Runciman, W.G. ‘Weber: Selections in Translation’. Cambridge University Press.
36. Weng, J., Lim, E.-P., Jiang, J., and He, Q. 2010. Twitterrank: Finding topic-sensitive influential twitterers. In Proceedings of the 3^rd ACM International Conference on Web Search and Data Mining (WSDM'10). 261--270.
37. Wu, S., Hofman, J. M., Mason, W. A., and Watts, D. J. 2011. Who says what to whom on twitter. In Proceedings of the 20^th International Conference on World Wide Web (WWW'11). 705--714.
38. Xing, E. P., Jordan, M. I., and Russell, S. 2003. A generalized mean field algorithm for variational inference in exponential families. In Proceedings of the 19^th Conference on Uncertainty in Artificial Intelligence (UAI'03). 583--591.
39. Yang, Z., Guo, J., Cai, K., Tang, J., Li, J., Zhang, L., and Su, Z. 2010. Understanding retweeting behaviors in social networks. In Proceedings of the 19^th ACM International Conference on Information and Knowledge Management (CIKM'10). 1633--1636.
40. Zhuang, H., Tang, J., Tang, W., Lou, T., Chin, A., and Wang, X. 2012. Graph-based ranking algorithms for e-mail expertise analysis. Data Mining Knowl. Discov. 25, 2, 270--297.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

• Information systems

  • Information retrieval