|
 ABSTRACT
In this paper, we consider the evolution of structure within large online social networks. We present a series of measurements of two such networks, together comprising in excess of five million people and ten million friendship links, annotated with metadata capturing the time of every event in the life of the network. Our measurements expose a surprising segmentation of these networks into three regions: singletons who do not participate in the network; isolated communities which overwhelmingly display star structure; and a giant component anchored by a well-connected core region which persists even in the absence of stars.We present a simple model of network growth which captures these aspects of component structure. The model follows our experimental results, characterizing users as either passive members of the network; inviters who encourage offline friends and acquaintances to migrate online; and linkers who fully participate in the social evolution of the network.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
L. A. Adamic and E. Adar. How to search a social network. Social Networks, 27(3):187--203, 2005.
|
| |
2
|
R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 47, 2002.
|
| |
3
|
R. Albert, H. Jeong, and A.-L. Barabási. Diameter of the world wide web. Nature, 401:130--131, 1999.
|
| |
4
|
A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, 1999.
|
| |
5
|
B. Bollobás. A probabilistic proof of an asymptotic formula for the number of labeled regular graphs. European Journal of Combinatorics, 1:311--316, 1980.
|
| |
6
|
B. Bollobás. Random Graphs. Cambridge University Press, 2001.
|
| |
7
|
B. Bollobás and O. Riordan. Mathematical results on scale-free random graphs, pages 1--37. Wiley--WCH, 2002.
|
| |
8
|
Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.309-320, June 2000
|
| |
9
|
P. S. Dodds, R. Muhamad, and D. J. Watts. An experimental study of search in global social networks. Science, 301:827--829, 2003.
|
| |
10
|
S. Dorogovtsev and J. Mendes. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, 2000.
|
| |
11
|
S. Dorogovtsev and J. Mendes. Evolution of networks. Advances in Physics, 51, 2002.
|
| |
12
|
P. Erdös and A. Rényi. On random graphs I. Publications Mathematics Debrecen, 6:290--297, 1959.
|
 |
13
|
Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
|
| |
14
|
|
| |
15
|
|
| |
16
|
J. Kleinberg. Complex networks and decentralized search algorithms. In Intl. Congress of Mathematicians, 2006.
|
| |
17
|
J. M. Kleinberg. Navigation in a small world. Nature, 406:845, 2000.
|
| |
18
|
|
| |
19
|
|
| |
20
|
R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
|
| |
21
|
|
| |
22
|
Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
[doi> 10.1145/1081870.1081893]
|
| |
23
|
D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic routing in social networks. PNAS, 102(33):11623--11628, 2005.
|
| |
24
|
|
| |
25
|
M. Newman. The structure and function of complex networks. SIAM Review, 45, 2:167--256, 2003.
|
| |
26
|
M. E. J. Newman, S. H. Strogatz, and D. J. Watts. Random graphs with arbitrary degree distributions and their applications. Physics Reviews E, 64, 2001.
|
| |
27
|
|
| |
28
|
S. Strogatz. Exploring complex networks. Nature, 410, 2001.
|
| |
29
|
S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994.
|
| |
30
|
D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, 1998.
|
CITED BY 35
|
|
|
|
|
Yu-Ru Lin , Hari Sundaram , Aisling Kelliher, Summarization of social activity over time: people, actions and concepts in dynamic networks, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
|
|
|
Yu-Ru Lin , Yun Chi , Shenghuo Zhu , Hari Sundaram , Belle L. Tseng, Facetnet: a framework for analyzing communities and their evolutions in dynamic networks, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
|
|
|
|
|
|
|
|
|
|
|
|
Alan Mislove , Hema Swetha Koppula , Krishna P. Gummadi , Peter Druschel , Bobby Bhattacharjee, Growth of the flickr social network, Proceedings of the first workshop on Online social networks, August 18-18, 2008, Seattle, WA, USA
|
|
|
Minas Gjoka , Michael Sirivianos , Athina Markopoulou , Xiaowei Yang, Poking facebook: characterization of osn applications, Proceedings of the first workshop on Online social networks, August 18-18, 2008, Seattle, WA, USA
|
|
|
Gayatri Swamynathan , Christo Wilson , Bryce Boe , Kevin Almeroth , Ben Y. Zhao, Do social networks improve e-commerce?: a study on social marketplaces, Proceedings of the first workshop on Online social networks, August 18-18, 2008, Seattle, WA, USA
|
|
|
|
|
|
|
|
|
David Crandall , Dan Cosley , Daniel Huttenlocher , Jon Kleinberg , Siddharth Suri, Feedback effects between similarity and social influence in online communities, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
|
|
|
Jian Huang , Ziming Zhuang , Jia Li , C. Lee Giles, Collaboration over time: characterizing and modeling network evolution, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA
|
|
|
Jure Leskovec , Lars Backstrom , Ravi Kumar , Andrew Tomkins, Microscopic evolution of social networks, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
|
|
|
Christo Wilson , Bryce Boe , Alessandra Sala , Krishna P.N. Puttaswamy , Ben Y. Zhao, User interactions in social networks and their implications, Proceedings of the fourth ACM european conference on Computer systems, April 01-03, 2009, Nuremberg, Germany
|
|
|
|
|
|
Adriano M. Pereira , Arlei Silva , Wagner Meira, Jr. , Virgilio Almeida, Seller's credibility in electronic markets: a complex network based approach, Proceedings of the 3rd workshop on Information credibility on the web, April 20-20, 2009, Madrid, Spain
|
|
|
Yun Chi , Shenghuo Zhu , Xiaodan Song , Junichi Tatemura , Belle L. Tseng, Structural and temporal analysis of the blogosphere through community factorization, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
|
|
|
Qiankun Zhao , Sourav S. Bhowmick , Xin Zheng , Kai Yi, Characterizing and predicting community members from evolutionary and heterogeneous networks, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
|
|
|
Georgia Koutrika , Frans Adjie Effendi , Zoltán Gyöngyi , Paul Heymann , Hector Garcia-Molina, Combating spam in tagging systems, Proceedings of the 3rd international workshop on Adversarial information retrieval on the web, May 08-08, 2007, Banff, Alberta, Canada
|
|
|
|
|
|
Josiane Xavier Parreira , Sebastian Michel , Matthias Bender , Tom Crecelius , Gerhard Weikum, P2P authority analysis for social communities, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
|
|
|
|
|
|
Josiane Xavier Parreira , Debora Donato , Carlos Castillo , Gerhard Weikum, Computing trusted authority scores in peer-to-peer web search networks, Proceedings of the 3rd international workshop on Adversarial information retrieval on the web, May 08-08, 2007, Banff, Alberta, Canada
|
|
|
Koustuv Dasgupta , Rahul Singh , Balaji Viswanathan , Dipanjan Chakraborty , Sougata Mukherjea , Amit A. Nanavati , Anupam Joshi, Social ties and their relevance to churn in mobile telecom networks, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
|
|
|
|
|
|
|
|
|
|
|
|
Lars Backstrom , Cynthia Dwork , Jon Kleinberg, Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
|
|
|
Jon M. Kleinberg, Challenges in mining social network data: processes, privacy, and paradoxes, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, p.4-5, August 12-15, 2007, San Jose, California, USA
|
|
|
Katherine Panciera , Aaron Halfaker , Loren Terveen, Wikipedians are born, not made: a study of power editors on Wikipedia, Proceedings of the ACM 2009 international conference on Supporting group work, May 10-13, 2009, Sanibel Island, Florida, USA
|
|
|
Ralf Schenkel , Tom Crecelius , Mouna Kacimi , Sebastian Michel , Thomas Neumann , Josiane X. Parreira , Gerhard Weikum, Efficient top-k querying over social-tagging networks, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore
|
|
|
|
|
|
Alan Mislove , Massimiliano Marcon , Krishna P. Gummadi , Peter Druschel , Bobby Bhattacharjee, Measurement and analysis of online social networks, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
H.2