Measurement and Analysis of Online Social Networks

At IMC, it has been presented the first study to examine multiple online social networks at scale. The paper analyzes “data gathered from four popular online social networks: Flickr, YouTube, LiveJournal, and Orkut”.


  • “the indegree of user nodes tends to match the outdegree;
  • the networks contain a densely connected core of high-degree nodes;
  • this core links small groups of strongly clustered, low-degree nodes at the fringes of the network”.

Implications on info dissemination and search

  • “The existence of a small, well-connected core implies that information seeded via a core node will rapidly spread through the entire network.”
  • “Similarly, searches that proceed along social network links will quickly reach the core. This suggests that simple unstructured search algorithms could be designed if the core users were to store some state about other users.”

Implications on trust
“In a social network, the underlying user graph can potentially be used as a means to infer some level of trust in an unknown user, to check the validity of a public key certificate, and to classify potential spam”.

  • “The tight core coupled with link reciprocity implies that users in the core appear on a large number of short paths. Thus, if malicious users are able to penetrate the core, they can skew many trust paths (or appear highly trustworthy to a large fraction of the network).”
  • “However, these two properties also lead to small path lengths and many disjoint paths, so the trust inference algorithms should be adjusted to account for this observation. In particular, given our data, an unknown user should be highly trusted only if multiple short disjoint paths to the user can be discovered.”
  • “The correlation in link degrees implies that users in the fringe will not be highly trusted unless they form direct links to other users. The “social” aspect of these networks is selfreinforcing: in order to be trusted, one must make many “friends”, and create many links that will slowly pull the user into the core.”

3 Responses to “Measurement and Analysis of Online Social Networks”

  1. Neal Lathia says:

    There is an interesting facebook application called Socialistics (social + statistics = original name) That allows you to examine your own social network, from your perspective. You can see charts showing th e break down of your network according to age, location, etc. It doesn’t give you the same insights as the above work but definitely some interesting stuff!

  2. Michael says:

    This is an excellent study. However, it is not the first one.
    Ahn et al. published in the WWW’07 conference (~3 months before IMC’07} the paper “Analysis of Topological Characteristics of Huge Online Social Networking Services”.

    They compare the structures of three online social networking services: Cyworld, MySpace, and Orkut, each with more than 10 million users.

    They use the complete data of Cyworld’s friend relationships and analyze its degree distribution, clustering property, degree correlation, and evolution over time. They also use Cyworld data to evaluate the validity of the snowball sampling method, which they use to crawl and obtain partial network topologies of MySpace and Orkut.

    Their study shows that Cyworld, the oldest of the three, demonstrates a changing scaling behavior over time in degree distribution. The latest Cyworld data’s degree distribution exhibits a multi-scaling behavior (varying power-law exponents), while those of MySpace and Orkut have simple scaling behaviors with a single different exponent each.

  3. Michael, thanks for your pointer!