Understanding social networks properties for trustworthy computing

Abedelaziz Mohaisen, Huy Tran, Nicholas Hopper, Yongdae Kim

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

The ever-increasing popularity of social networks opens new directions for leveraging social networks to build primitives for security and communication, in many contexts. Such primitives utilize the trust in these social networks to ensure collaboration and algorithmic properties exhibited in such networks to argue for the effectiveness of such primitives. Despite the importance of such properties and their quality to the operation of these primitives, less effort is made to measure these properties and understand the relationship among them and to other characteristics of social networks. We extend our earlier results measuring the mixing time, to investigate a new property used for building Sybil defenses, namely the expansion of social graphs. We measure the expansion of social graphs, and show quantitatively that, with a few exceptions, it is sufficient to support Sybil defense mechanisms based on expansion. We relate the mixing time of social graphs to graph degeneracy, which captures cohesiveness of the graph. We experimentally show that fast-mixing graphs tend to have a larger single core whereas slow mixing graphs tend to have smaller multiple cores. While this study provides quantitative evidence relating the mixing time to coreness of the graph, it also agrees with our previous observations about the tight-knit community structure in slow mixing social graphs.

Original languageEnglish (US)
Title of host publicationProceedings - 31st International Conference on Distributed Computing Systems Workshops, ICDCSW 2011
Pages154-159
Number of pages6
DOIs
StatePublished - Sep 9 2011
Event31st International Conference on Distributed Computing Systems Workshops, ICDCSW 2011 - Minneapolis, MN, United States
Duration: Jun 20 2011Jun 24 2011

Publication series

NameProceedings - International Conference on Distributed Computing Systems

Other

Other31st International Conference on Distributed Computing Systems Workshops, ICDCSW 2011
CountryUnited States
CityMinneapolis, MN
Period6/20/116/24/11

Keywords

  • Social networks
  • Sybil defenses
  • expanders
  • measurements
  • mixing time

Fingerprint Dive into the research topics of 'Understanding social networks properties for trustworthy computing'. Together they form a unique fingerprint.

Cite this