Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/ICDCSW.2011.48 | Distributed Computing Systems Workshops |
Keywords | DocType | ISSN |
understanding social networks properties,social network,graph degeneracy,fast-mixing graph,new property,sybil defenses,show quantitatively,social graph,algorithmic property,sybil defense mechanism,trustworthy computing,new direction,defense mechanism,logic gate,measurements,markov processes,physics,community structure,indexing terms,logic gates,markov process,social networks,graph theory,time measurement,mixing time | Conference | 1545-0678 E-ISBN : 978-0-7695-4386-4 |
ISBN | Citations | PageRank |
978-0-7695-4386-4 | 5 | 0.45 |
References | Authors | |
22 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abedelaziz Mohaisen | 1 | 338 | 30.36 |
| Huy Tran | 2 | 286 | 31.59 |
| Nicholas Hopper | 3 | 1469 | 95.76 |
| Yongdae Kim | 4 | 1944 | 125.44 |