Structure and Evolution of Online Social Networks

Structure and evolution of two popular online social networks: Flickr and Yahoo! 360.

Analysis of the graphs from an evolutionary point of view, by keeping track the precise moments when each node and edge arrives in the graph.

A surprising segmentation of these networks into three regions:
1. singletons who do not participate in the network;
2. isolated communities which overwhelmingly display star structure; and
3. a giant component anchored by a well-connected core region which persists even in the absence of stars.

The key points from the experiments:
1. Online social networks often contain more than half their mass outside the giant component, and the structure outside the giant component is largely characterized by stars. The creation of stars is largely a result of the dynamics of invitation, in which many people are invited to the social network, but only a small fraction choose to engage more deeply than simply responding to
an invitation from a friend.
2. Online social networks appears to travel through distinct stages of growth, characterized by specific behavior in terms of density, diameter, and regularity of component structure.

From Ravi Kumar, Jasmine Novak and Andrew Tomkins, Structure and Evolution of Online Social Networks, Link Mining: Models, Algorithms, and Applications 2010, Part 4, 337-357.


About Kyoung Jun Lee
Professor of Kyung Hee Univ.

Comments are closed.

%d bloggers like this: