ProfileRank: finding relevant content and influential users based on information diffusion

ABSTRACT

Understanding information diffusion processes that take place on the Web, specially in social media, is a fundamental step towards the design of effective information diffusion mechanisms, recommendation systems, and viral marketing/advertising campaigns. Two key concepts in information diffusion are influence and relevance. Influence is the ability to popularize content in an online community. To this end, influentials introduce and propagate relevant content, in the sense that such content satisfies the information needs of a significant portion of this community.

In this paper, we study the problem of identifying influential users and relevant content in information diffusion data. We propose ProfileRank, a new information diffusion model based on random walks over a user-content graph. ProfileRank is a PageRank inspired model that exploits the principle that relevant content is created and propagated by influential users and influential users create relevant content. A convenient property of ProfileRank is that it can be adapted to provide personalized recommendations.

Experimental results demonstrate that ProfileRank makes accurate recommendations, outperforming baseline techniques. We also illustrate relevant content and influential users discovered using ProfileRank. Our analysis shows that ProfileRank scores are more correlated with content diffusion than with the network structure. We also show that our new modeling is more efficient than PageRank to perform these calculations.

References

1. L. Adamic and E. Adar. Friends and neighbors on the web. Social networks, 25(3):211--230, 2003.
2. R. Baeza-Yates, B. Ribeiro-Neto, et al. Modern information retrieval, volume 82. Addison-Wesley New York, 1999.
3. S. Baluja, R. Seth, D. Sivakumar, Y. Jing, J. Yagnik, S. Kumar, D. Ravichandran, and M. Aly. Video suggestion and discovery for youtube: taking random walks through the view graph. In WWW, 2008.
4. M. Bianchini, M. Gori, and F. Scarselli. Inside pagerank. ACM Trans. Internet Technol., 5(1):92--128, 2005.
5. M. Cha, H. Haddadi, F. Benevenuto, and K. P. Gummadi. Measuring User Influence in Twitter: The Million Follower Fallacy. In ICWSM, 2010.
6. M. Cha, A. Mislove, and K. P. Gummadi. A measurement-driven analysis of information propagation in the flickr social network. In WWW, 2009.
7. J. Chen, R. Nairn, L. Nelson, M. Bernstein, and E. Chi. Short and tweet: experiments on recommending content from information streams. In CHI, 2010.
8. M. De Choudhury, S. Counts, and M. Czerwinski. Identifying relevant social media content: leveraging information diversity and user cognition. In HT, 2011.
9. M. Franceschet. Pagerank: standing on the shoulders of giants. Commun. ACM, 54(6):92--101, June 2011.
10. N. Friedkin. A structural theory of social influence, volume 13. Cambridge University Press, 2006.
11. M. Gomez Rodriguez, J. Leskovec, and A. Krause. Inferring networks of diffusion and influence. In SIGKDD, 2010.
12. A. Goyal, F. Bonchi, and L. V. Lakshmanan. Learning influence probabilities in social networks. In WSDM, 2010.
13. D. Gruhl, R. Guha, D. Liben-Nowell, and A. Tomkins. Information diffusion through blogspace. In WWW, 2004.
14. J. Hannon, M. Bennett, and B. Smyth. Recommending twitter users to follow using content and collaborative filtering approaches. In RecSys, 2010.
15. Y. Kim and K. Shim. Twitobi: A recommendation system for twitter using probabilistic modeling. ICDM, 2011.
16. J. M. Kleinberg. Authoritative sources in a hyperlinked environment. In SODA, 1998.
17. H. Kwak, C. Lee, H. Park, and S. Moon. What is twitter, a social network or a news media? In WWW, 2010.
18. V. Leroy, B. B. Cambazoglu, and F. Bonchi. Cold start link prediction. In SIGKDD, 2010.
19. J. Leskovec, L. A. Adamic, and B. A. Huberman. The dynamics of viral marketing. ACM Trans. Web, 1(1):5, 2007.
20. J. Leskovec, L. Backstrom, and J. Kleinberg. Meme-tracking and the dynamics of the news cycle. In SIGKDD, 2009.
21. D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In CIKM, 2003.
22. L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, 1999.
23. F. Ricci, L. Rokach, and B. Shapira. Introduction to recommender systems handbook. Recommender Systems Handbook, 2011.
24. D. M. Romero, W. Galuba, S. Asur, and B. A. Huberman. Influence and passivity in social media. In PKDD, 2011.
25. A. Silva, H. Valiati, S. Guimarães, and W. Meira Jr. From individual behavior to influence networks: A case study on twitter. In Webmedia, 2011.
26. J. Tang, J. Sun, C. Wang, and Z. Yang. Social influence analysis in large-scale networks. In KDD, 2009.
27. H. Tong, C. Faloutsos, and J.-Y. Pan. Fast random walk with restart and its applications. In ICDM, 2006.
28. H. Tong, S. Papadimitriou, P. S. Yu, and C. Faloutsos. Proximity tracking on time-evolving bipartite graphs. In SDM, 2008.
29. D. Watts. A twenty-first century science. Nature, 445(7127), 2007.
30. J. Weng, E.-P. Lim, J. Jiang, and Q. He. Twitterrank: finding topic-sensitive influential twitterers. In WSDM, 2010.
31. V. V. Williams. Multiplying matrices faster than coppersmith-winograd. In STOC, 2012.
32. J. Yang and J. Leskovec. Patterns of temporal variation in online media. In WSDM, 2011.

Index Terms

• Information systems

  • Information retrieval

    • Retrieval models and ranking