TY - GEN
T1 - On the mixing time of directed social graphs and security implications
AU - Mohaisen, Abedelaziz
AU - Tran, Huy
AU - Hopper, Nicholas
AU - Kim, Yongdae
PY - 2012
Y1 - 2012
N2 - Many graphs in general, and social graphs in particular, are directed by nature. However, applications built on top of social networks, including Sybil defenses, information routing and dissemination, and anonymous communication require mutual relationships which produce undirected graphs. When undirected graphs are used as testing tools for these applications to bring insight on their usability and potential deployment, directed graphs are converted into undirected graphs by omitting edge directions or by augmenting graphs. Unfortunately, it is unclear how altering these graphs affects the quality of their mixing time. Motivated by the lack of prior work on this problem, we investigate mathematical tools for measuring the mixing time of directed social graphs and its associated error bounds. We use these tools to measure the mixing time of several benchmarking directed graphs and their undirected counterparts. We then measure how this difference impacts two applications built on top of social networks: a Sybil defense mechanism and an anonymous communication system.
AB - Many graphs in general, and social graphs in particular, are directed by nature. However, applications built on top of social networks, including Sybil defenses, information routing and dissemination, and anonymous communication require mutual relationships which produce undirected graphs. When undirected graphs are used as testing tools for these applications to bring insight on their usability and potential deployment, directed graphs are converted into undirected graphs by omitting edge directions or by augmenting graphs. Unfortunately, it is unclear how altering these graphs affects the quality of their mixing time. Motivated by the lack of prior work on this problem, we investigate mathematical tools for measuring the mixing time of directed social graphs and its associated error bounds. We use these tools to measure the mixing time of several benchmarking directed graphs and their undirected counterparts. We then measure how this difference impacts two applications built on top of social networks: a Sybil defense mechanism and an anonymous communication system.
UR - http://www.scopus.com/inward/record.url?scp=84871985239&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84871985239&partnerID=8YFLogxK
U2 - 10.1145/2414456.2414476
DO - 10.1145/2414456.2414476
M3 - Conference contribution
AN - SCOPUS:84871985239
SN - 9781450313032
T3 - ASIACCS 2012 - 7th ACM Symposium on Information, Computer and Communications Security
SP - 36
EP - 37
BT - ASIACCS 2012 - 7th ACM Symposium on Information, Computer and Communications Security
T2 - 7th ACM Symposium on Information, Computer and Communications Security, ASIACCS 2012
Y2 - 2 May 2012 through 4 May 2012
ER -