Structure and evolution of online social networks pdf

Muhamad, and D. An experimental study of search in gression. It would be attractive to develop a more detailed theory global social networks. Science, —, Dorogovtsev and J. Oxford University Press, Third, Figure 4 shows a surprising macroscopic component struc- [11] S.

Evolution of networks. Advances in Physics, 51, ture in which the total mass of individuals is well spread across a On random graphs I.

Publications Mathematics oretic perspective, smaller components. We feel that a deeper un- Debrecen, —, Faloutsos, P. Faloutsos, and C. On power-law relationships of the internet topology. Fetterly, M. Manasse, M. Najork, and J. A large-scale study of the two active by very different types of participants. Software Practice and Experience, 34 2 —, Finally, we have presented a simple model which is surprisingly It will be in- [15] J.

The small-world phenomenon: An algorithmic perspective. In 32nd STOC, pages —, Complex networks and decentralized search algorithms. In Intl. Similarly, the model itself is optimized to [17] J. Navigation in a small world. Nature, , Kumar, J. Novak, P. Raghavan, and A. Structure and evolution of blogspace. CACM, 47 12 —39, On the bursty evolution of the data in order to provide predictive power.

Nonetheless, it is in- blogspace. World Wide Web Journal, 8 2 —, Kumar, P. Rajagopalan, D. Sivakumar, A. Tomkins, and taken as descriptive of the social network in any sense.

For exam- E. Stochastic models for the web graph. In 41st FOCS, pages 57—65, Rajagopalan, and A. Trawling the web for active members, compared to the Flickr community, but at the same emerging cyber-communities.

Is this represen- [22] J. Leskovec and J. Graphs over time: Densification laws, shrinking diameters, and possible explanations. In 11th KDD, pages —, tative of the underlying reality? Liben-Nowell, J. Novak, R. Geographic routing in social networks. PNAS, 33 —, Molloy and B. A critical point for random graphs with a given degree In this paper we studied the structure and evolution of two pop- sequence. Random Structures and Algorithms, Our [25] M. The structure and function of complex networks.

SIAM Review, 45, —, Newman, S. Strogatz, and D. Random graphs with arbitrary by keeping track the precise moments when each node and edge degree distributions and their applications. Physics Reviews E, 64, We show that these quantitatively different [27] A.

Ntoulas, J. Cho, and C. The evolution of graphs share many qualitative properties in common. In particular, the web from a search engine perspective. In 13th WWW, pages 1—12, Exploring complex networks. Wasserman and K. Based on these empirical observations, we [30] D. Watts and S. Since our model is fairly simple, we believe it is amenable to mathematical analyses. Statistical properties of community structure in large social and information networks By Jure Leskovec.

Dynamics of large networks By Jure Leskovec. Bagrow, J. X 3, Google Scholar. Baluja, S. Ben-Naim, E. Bianconi, G. Bonato, A.

Caldarelli, G. Catanzaro, M. Physical Review E 70, Google Scholar. Catone, J. Cattuto, C. Cha, M. Clauset, A. Science , — CrossRef Google Scholar.

Erdos, P. Estrada, E. Ferrara, E. Fortunato, S. Gaito, S. If the source is a linker, then the destination is chosen analyze the remaining core. For the core of the Flickr final graph, from among the existing linkers and inviters, again using preferen- the average diameter is 4.

For tial attachment. The parameters controlling the model are shown the core of the Yahoo! This suggests that there is a small Description of the parameter core inside the giant component of extremely high connectivity. Stars are the dominant explanation of the structure outside the p User type distribution passive, inviter, linker giant component. At any point in time, let the component? Let d u denote the degree them as they merge into the giant component. Based on this track- of node u.

Later we will discuss some possible implications of this observation. For each edge u, v , u is chosen from D0 , where the bias parameter is set to 0. Notice that the initiator of a link is cial networks. Our goal in developing this model is to explain the chosen from all non-passive nodes based only on degree. However, key aspects of network growth in as simple a manner as possible, once a linker decides to generate a node internal to the existing obviating the need for more complex behavioral explanations.

This reflects the fact that the middle region is more difficult Component structure. The model should produce an evolving com- to discover when navigating a social network. The fraction of users who are singletons, those in the middle region, and those in the 4. The non-giant We now evaluate the model with respect to the three families of component of each size should capture a fraction of the users which conditions we hope it will fulfill. We choose suitable parameters for matches the empirical observations and should analytically match our model and simulate the model.

We then examine the properties the observed power law. The following table Star structure. The non-giant components should be predominantly shows the appropriate parameter choices. Their growth rates should match the growth of the actual data. The nodes making up the giant com- Flickr 0. We start with the component structure of these sim- ulations and compare them against the actual data.

The following 4. There are three types of users: passive, linkers, and inviters. Pas- Data Singletons Middle Giant sive users join the network out of curiosity or at the insistence of region component a friend, but never engage in any significant activity.

Inviters are Flickr. Linkers At each timestep, a node arrives, and is determined at birth to be We now refine the middle region further and compare the simu- lated versus the actual data. From our simulation, we see that in terms of components and the structure of the middle region, our model can accurately capture the Acknowledgments.

We are grateful to the Flickr and Yahoo! Adamic and E. How to search a social network. Social Networks, The first is that online social networks often contain more than half 27 3 —, Albert and A. Statistical mechanics of complex networks.

The creation Reviews of Modern Physics, 74, 47, Albert, H. Jeong, and A. Diameter of the world wide web. Barabasi and R. Emergence of scaling in random networks.

A probabilistic proof of an asymptotic formula for the number of labeled regular graphs. European Journal of Combinatorics, —, The second key takeaway is that online social networks appears [6] B.

Random Graphs. Cambridge University Press, Bollobas and O. Mathematical results on scale-free random graphs, cific behavior in terms of density, diameter, and regularity of com- pages 1— Wiley—WCH, We have observed these changes by studying the [8] A.

Broder, S. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Graph structure in the web. Dodds, R. Muhamad, and D. An experimental study of search in gression. It would be attractive to develop a more detailed theory global social networks. Science, —, Dorogovtsev and J. Oxford University Press, Third, Figure 4 shows a surprising macroscopic component struc- [11] S. Evolution of networks. Advances in Physics, 51, ture in which the total mass of individuals is well spread across a On random graphs I.

Publications Mathematics oretic perspective, smaller components. We feel that a deeper un- Debrecen, —, Faloutsos, P. Faloutsos, and C. On power-law relationships of the internet topology. Leskovec, K. Lang, A. Dasgupta, and M. Statistical properties of community structure in large social and information networks. Liben-Nowell, J. Novak, R. Geographic routing in social networks. Proceedings of the National Academy of Sciences , 33 —, Molloy and B. A critical point for random graphs with a given degree sequence.

Random Structures and Algorithms , —, The structure and function of complex networks. SIAM Review , —, Newman, S. Strogatz, and D. Random graphs with arbitrary degree distributions and their applications. Physical Review E , 64 2 17 pages , Ntoulas, J. Cho, and C. Exploring complex networks. Wasserman and K. Social Network Analysis: Methods and Applications. Revised, reprinted edition, Watts and S. Research Sunnyvale USA 2. Google, Inc. Mountain View USA. Personalised recommendations.

Cite chapter How to cite? ENW EndNote.