Alan Mislove
ABSTRACT
Online social networking sites like Orkut, YouTube, and Flickr are among the most popular sites on the Internet. Users of these sites form a social network, which provides a powerful means of sharing, organizing, and finding content and contacts. The popularity of these sites provides an opportunity to study the characteristics of online social network graphs at large scale. Understanding these graphs is important, both to improve current systems and to design new applications of online social networks.
This paper presents a large-scale measurement study and analysis of the structure of multiple online social networks. We examine data gathered from four popular online social networks: Flickr, YouTube, LiveJournal, and Orkut. We crawled the publicly accessible user links on each site, obtaining a large portion of each social network's graph. Our data set contains over 11.3 million users and 328 million links. We believe that this is the first study to examine multiple online social networks at scale.
Our results confirm the power-law, small-world, and scale-free properties of online social networks. We observe that the indegree of user nodes tends to match the outdegree; that the networks contain a densely connected core of high-degree nodes; and that this core links small groups of strongly clustered, low-degree nodes at the fringes of the network. Finally, we discuss the implications of these structural properties for the design of social network based systems.
- Stanford WebBase Project. http://www-diglib.stanford.edu/~testbed/doc2/WebBase.Google Scholar
- L. A. Adamic. The Small World Web. In Proceedings of the Third European Conference on Research and Advanced Technology for Digital Libraries (ECDL'99), Paris, France, Sep 1999. Google ScholarDigital Library
- L. A. Adamic, O. Buyukkokten, and E. Adar. A social network caught in the Web. First Monday, 8(6), 2003.Google Scholar
- Y.-Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong. Analysis of Topological Characteristics of Huge Online Social Networking Services. In Proceedings of the 16th international conference on World Wide Web (WWW'07), Banff, Canada, May 2007. Google ScholarDigital Library
- R. Albert, H. Jeong, and A.-L. Barábási. The Diameter of the World Wide Web. Nature, 401:130, 1999.Google ScholarCross Ref
- L. A. N. Amaral, A. Scala, M. Barthélémy, and H. E. Stanley. Classes of small-world networks. Proceedings of the National Academy of Sciences (PNAS), 97:11149--11152, 2000.Google ScholarCross Ref
- A. Awan, R. A. Ferreira, S. Jagannathan, and A. Grama. Distributed uniform sampling in real-world networks. Technical Report CSD-TR-04-029, Purdue University, 2004.Google Scholar
- L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan. Group Formation in Large Social Networks: Membership, Growth, and Evolution. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'06), Philadelphia, PA, Aug 2006. Google ScholarDigital Library
- A.-L. Barábási and R. Albert. Emergence of Scaling in Random Networks. Science, 286:509--512, 1999.Google Scholar
- L. Becchetti, C. Castillo, D. Donato, and A. Fazzone. A Comparison of Sampling Techniques for Web Graph Characterization. In Proceedings of the Workshop on Link Analysis (LinkKDD'06), Philadelphia, PA, Aug 2006.Google Scholar
- V. Braitenberg and A. Schüz. Anatomy of a Cortex: Statistics and Geometry. Springer-Verlag, Berlin, 1991.Google Scholar
- A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph Structure in the Web: Experiments and Models. In Proceedings of the 9th International World Wide Web Conference (WWW'00), Amsterdam, May 2000. Google ScholarDigital Library
- A. Clauset, C. R. Shalizi, and M. E. J. Newman. Power-law distributions in empirical data, Jun 2007. http://arxiv.org/abs/0706.1062v1.Google Scholar
- d. boyd. Friends, Friendsters, and Top 8: Writing community into being on social network sites. First Monday, 11(12), 2006.Google Scholar
- P. Erdös and A. Rényi. On Random Graphs I. Publicationes Mathematicae Debrecen, 5:290--297, 1959.Google Scholar
- M. Faloutsos, P. Faloutsos, and C. Faloutsos. On Power-Law Relationships of the Internet Topology. In Proceedings of the Annual Conference of the ACM Special Interest Group on Data Communication (SIGCOMM'99), Cambridge, MA, Aug 1999. Google ScholarDigital Library
- S. Garriss, M. Kaminsky, M. J. Freedman, B. Karp, D. Mazières, and H. Yu. Re: Reliable Email. In Proceedings of the 3rd Symposium on Networked Systems Design and Implementation (NSDI'06), San Jose, CA, May 2006. Google ScholarDigital Library
- M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences (PNAS), 99:7821--7826, 2002.Google ScholarCross Ref
- Google Co-op. http://www.google.com/coop/.Google Scholar
- M. Granovetter. The Strength of Weak Ties. American Journal of Sociology, 78(6), 1973.Google ScholarCross Ref
- J. Kleinberg. Authoritative Sources in a Hyperlinked Environment. Journal of the ACM, 46:604--632, 1999. Google ScholarDigital Library
- J. Kleinberg. Navigation in a Small World. Nature, 406:845--845, 2000.Google ScholarCross Ref
- J. Kleinberg. The Small-World Phenomenon: An Algorithmic Perspective. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'00), Portland, OR, May 2000. Google ScholarDigital Library
- J. Kleinberg and S. Lawrence. The Structure of the Web. Science, 294:1849--1850, 2001.Google Scholar
- J. M. Kleinberg and R. Rubinfeld. Short paths in expander graphs. In IEEE Symposium on Foundations of Computer Science (FOCS'96), Burlington, VT, Oct 1996. Google ScholarDigital Library
- R. Kumar, J. Novak, and A. Tomkins. Structure and Evolution of Online Social Networks. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'06), Philadelphia, PA, Aug 2006. Google ScholarDigital Library
- R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Trawling the Web for Emerging Cyber-Communities. Computer Networks, 31:1481--1493, 1999. Google ScholarDigital Library
- S. Lee, R. Sherwood, and B. Bhattacharjee. Cooperative peer groups in NICE. In Proceedings of the Conference on Computer Communications (INFOCOM'03), San Francisco, CA, Mar 2003.Google ScholarCross Ref
- S. H. Lee, P.-J. Kim, and H. Jeong. Statistical properties of sampled networks. Physical Review E, 73, 2006.Google Scholar
- L. Li and D. Alderson. Diversity of graphs with highly variable connectivity. Physics Review E, 75, 2007.Google Scholar
- L. Li, D. Alderson, J. C. Doyle, and W. Willinger. Towards a Theory of Scale-Free Graphs: Definitions, Properties, and Implications. Internet Mathematics, 2(4):431--523, 2006.Google ScholarCross Ref
- D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic Routing in Social Networks. Proceedings of the National Academy of Sciences (PNAS), 102(33):11623--11628, 2005.Google ScholarCross Ref
- P. Mahadevan, D. Krioukov, K. Fall, and A. Vahdat. Systematic Topology Analysis and Generation Using Degree Correlations. In Proceedings of the Annual Conference of the ACM Special Interest Group on Data Communication (SIGCOMM'06), Pisa, Italy, August 2006. Google ScholarDigital Library
- S. Milgram. The small world problem. Psychology Today, 2(60), 1967.Google Scholar
- A. Mislove, K. P. Gummadi, and P. Druschel. Exploiting social networks for Internet search. In Proceedings of the 5th Workshop on Hot Topics in Networks (HotNets-V), Irvine, CA, Nov 2006.Google Scholar
- M. Molloy and B. Reed. A critical point for random graphs with a given degree distribution. Random Structures and Algorithms, 6, 1995. Google ScholarDigital Library
- M. Molloy and B. Reed. The size of the giant component of a random graph with a given degree sequence. Combinatorics, Probability and Computing, 7, 1998. Google ScholarDigital Library
- R. Morselli, B. Bhattacharjee, J. Katz, and M. A. Marsh. Keychains: A Decentralized Public-Key Infrastructure. Technical Report CS-TR-4788, University of Maryland, 2006.Google Scholar
- MozillaCoop. http://www.mozilla.com.Google Scholar
- MySpace is the number one website in the U.S. according to Hitwise. HitWise Press Release, July, 11, 2006. http://www.hitwise.com/press-center/hitwiseHS2004/social-networking-june-2006.php.Google Scholar
- M. E. J. Newman. The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences (PNAS), 98:409--415, 2001.Google ScholarCross Ref
- M. E. J. Newman. Mixing patterns in networks. Physics Review E, 67, 2003.Google Scholar
- L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Technical report, Stanford University, 1998.Google Scholar
- PayPerPost. http://www. payperpost.com.Google Scholar
- A. G. Phadke and J. S. Thorp. Computer relaying for power systems. John Wiley & Sons, Inc., New York, NY, USA, 1988. Google ScholarDigital Library
- I. Pool and M. Kochen. Contacts and influence. Social Networks, 1:1--48, 1978.Google ScholarCross Ref
- D. Rezner. The Power and Politics of Weblogs. In Proceedings of the ACM Conference on Computer Supported Cooperative Work (CSCW'04), Chicago, IL, Nov 2004.Google Scholar
- G. Siganos, S. L. Tauro, and M. Faloutsos. Jellyfish: A Conceptual Model for the AS Internet Topology. Journal of Communications and Networks, 8(3):339--350, 2006.Google ScholarCross Ref
- Skype. http://www.skype.com.Google Scholar
- StumbleUpon. http://www.stumbleupon.com.Google Scholar
- S. Wasserman and K. Faust. Social Networks Analysis: Methods and Applications. Cambridge University Press, Cambridge, UK, 1994.Google ScholarCross Ref
- D. Watts and S. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, 1998.Google ScholarCross Ref
- W. Willinger, D. Alderson, and L. Li. A pragmatic approach to dealing with high-variability in network measurements. In Proceedings of the 2nd ACM/Usenix Internet Measurement Conference (IMC'04), Taormina, Italy, Oct 2004. Google ScholarDigital Library
- Yahoo! MyWeb. http://myweb2.search.yahoo.com.Google Scholar
- H. Yu, M. Kaminsky, P. B. Gibbons, and A. Flaxman. SybilGuard: Defending against Sybil attacks via social networks. In Proceedings of the Annual Conference of the ACM Special Interest Group on Data Communication (SIGCOMM'06), Pisa, Italy, August 2006. Google ScholarDigital Library
Index Terms
- Measurement and analysis of online social networks
Recommendations
The effects of collective MMORPG (Massively Multiplayer Online Role-Playing Games) play on gamers' online and offline social capital
This study examines the impact of collective MMORPG play on gamers' social capital in both the virtual world and the real world. Collective MMORPG play is conceptualized as the frequency of joint gaming actions and gamers' assessment of the experience ...
Building social capital with Facebook: Type of network, availability of other media, and social self-efficacy matter#
Highlights- Type of friends affects building social capital via Facebook and traditional media.
AbstractFindings about Facebook's effect on relationships are mixed, possibly due to lack of models that acknowledge differences across users, types of their friends, and use of competing media. To address this, we proposed and tested how ...
Finding hierarchy in directed online social networks
WWW '11: Proceedings of the 20th international conference on World wide webSocial hierarchy and stratification among humans is a well studied concept in sociology. The popularity of online social networks presents an opportunity to study social hierarchy for different types of networks and at different scales. We adopt the ...
Comments