Measuring the mixing time of social graphs

Abedelaziz Mohaisen, Aaram Yun, Yongdae Kim

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

130 Scopus citations


Social networks provide interesting algorithmic properties that can be used to bootstrap the security of distributed systems. For example, it is widely believed that social networks are fast mixing, and many recently proposed designs of such systems make crucial use of this property. However, whether real-world social networks are really fast mixing is not verified before, and this could potentially affect the performance of such systems based on the fast mixing property. To address this problem, we measure the mixing time of several social graphs, the time that it takes a random walk on the graph to approach the stationary distribution of that graph, using two techniques. First, we use the second largest eigenvalue modulus which bounds the mixing time. Second, we sample initial distributions and compute the random walk length required to achieve probability distributions close to the stationary distribution. Our findings show that the mixing time of social graphs is much larger than anticipated, and being used in literature, and this implies that either the current security systems based on fast mixing have weaker utility guarantees or have to be less efficient, with less security guarantees, in order to compensate for the slower mixing.

Original languageEnglish
Title of host publicationIMC'10 - Proceedings of the 2010 ACM Internet Measurement Conference
PublisherAssociation for Computing Machinery
Number of pages7
ISBN (Print)9781450300575
StatePublished - 2010
Event10th Internet Measurement Conference, IMC 2010 - Melbourne, Australia
Duration: 1 Nov 20103 Nov 2010

Publication series

NameProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC


Conference10th Internet Measurement Conference, IMC 2010


  • Measurement
  • Mixing time
  • Social networks
  • Sybil defenses


Dive into the research topics of 'Measuring the mixing time of social graphs'. Together they form a unique fingerprint.

Cite this