Afton Geil
John D. Owens
ABSTRACT
In this paper, we investigate the potential of GPUs for performing link structure analysis of social graphs. Specifically, we implement Twitter's WTF ("Who to Follow") recommendation system on a single GPU. Our implementation shows promising results on moderate-sized social graphs. It can return the top-K relevant users for a single user in 172 ms when running on a subset of the 2009 Twitter follow graph with 16 million users and 85 million social relations. For our largest dataset, which contains 75% of the users (30 million) and 50% of the social relations (680 million) of the complete follow graph, this calculation takes 1.0 s. We also propose possible solutions to apply our system to follow graphs of larger sizes that do not fit into the on-board memory of a single GPU.
- K. Avrachenkov, N. Litvak, D. Nemirovsky, and N. Osipova. Monte Carlo methods in PageRank computation: When one iteration is sufficient. SIAM Journal of Numerical Analysis, 45(2):890--904, Feb. 2007. Google Scholar
Digital Library
- B. Bahmani, A. Chowdhury, and A. Goel. Fast incremental and personalized PageRank. Proceedings of the VLDB Endowment, 4(3):173--184, Dec. 2010. Google ScholarDigital Library
- A. Goel. The "who-to-follow" system at Twitter: Algorithms, impact, and further research. WWW 2014 industry track, 2014.Google Scholar
- P. Gupta, A. Goel, J. Lin, A. Sharma, D. Wang, and R. Zadeh. WTF: The who to follow service at Twitter. In Proceedings of the International Conference on the World Wide Web, pages 505--514, May 2013. Google ScholarDigital Library
- J. M. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5):604--632, Sept. 1999. Google ScholarDigital Library
- H. Kwak, C. Lee, H. Park, and S. Moon. What is Twitter, a social network or a news media? In Proceedings of the International Conference on the World Wide Web, pages 591--600, Apr. 2010. Google ScholarDigital Library
- R. Lempel and S. Moran. SALSA: The stochastic approach for link-structure analysis. ACM Transactions on Information Systems, 19(2):131--160, Apr. 2001. Google ScholarDigital Library
- J. Leskovec. SNAP: Stanford large network dataset collection. http://snap.stanford.edu/data/. Accessed: 2014-05--18.Google Scholar
- D. Merrill, M. Garland, and A. Grimshaw. Scalable GPU graph traversal. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '12, pages 117--128, Feb. 2012. Google ScholarDigital Library
- S. A. Myers, A. Sharma, P. Gupta, and J. Lin. Information network or social network?: The structure of the Twitter follow graph. In Proceedings of the Companion Publication of the International Conference on the World Wide Web, WWW Companion '14, pages 493--498, Apr. 2014. Google ScholarDigital Library
- L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, Nov. 1999.Google Scholar
- A. Rungsawang and B. Manaskasemsak. Fast PageRank computation on a GPU cluster. In Proceedings of the 2012 20th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP), pages 450--456, Feb. 2012. Google ScholarDigital Library
- K. G. Srinivasa, K. Mishra, C. S. Prajeeth, and A. M. Talha. GPU implementation of friend recommendation system using CUDA for social networking services. In Proceedings of the International Conference on Emerging Research in Computing, Information, Communication, and Applications, pages 890--895, Aug. 2013.Google Scholar
- T. Wu, B. Wang, Y. Shan, F. Yan, Y.Wang, and N. Xu. Efficient PageRank and SpMV computation on AMD GPUs. In Proceedings of the 39th International Conference on Parallel Processing, pages 81--89, Sept. 2010. Google ScholarDigital Library
Index Terms
- WTF, GPU! computing twitter's who-to-follow on the GPU
Recommendations
On recommending hashtags in twitter networks
SocInfo'12: Proceedings of the 4th international conference on Social InformaticsTwitter network is currently overwhelmed by massive amount of tweets generated by its users. To effectively organize and search tweets, users have to depend on appropriate hashtags inserted into tweets. We begin our research on hashtags by first ...
Recommending Who to Follow in the Software Engineering Twitter Space
With the advent of social media, developers are increasingly using it in their software development activities. Twitter is one of the popular social mediums used by developers. A recent study by Singer et al. found that software developers use Twitter ...
A sentiment analysis of audiences on twitter: who is the positive or negative audience of popular twitterers?
ICHIT'11: Proceedings of the 5th international conference on Convergence and hybrid information technologyMicroblogging is a new informal communication medium of blogging that differs from a traditional blog in which content is much shorter. Microbloggers post about topics that describe their current status. Twitter is a popular microblogging service and ...
Comments