Measuring the mixing time of social graphs

Abedelaziz Mohaisen, Aaram Yun, Yongdae Kim

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

121 Scopus citations

Abstract

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
Pages383-389
Number of pages7
DOIs
StatePublished - 2010
Event10th Internet Measurement Conference, IMC'10 - Melbourne, VIC, Australia
Duration: 1 Nov 20103 Nov 2010

Publication series

NameProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC

Conference

Conference10th Internet Measurement Conference, IMC'10
Country/TerritoryAustralia
CityMelbourne, VIC
Period1/11/103/11/10

Keywords

  • Measurement
  • Mixing time
  • Social networks
  • Sybil defenses

Fingerprint

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

Cite this