On the Mixing Time of Directed Social Graphs and Security Implications

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 612
  • Download : 497
While many social graphs are directed by nature, applica- tions that use social graphs are often evaluated on undi- rected versions of these graphs. Manipulating a social graph in this manner, however, may change important properties like the mixing time, a critical parameter for applications such as Sybil defense and anonymous communication. In this paper we measure the mixing time and behavior of several directed graphs and their undirected counterparts. Counter-intuitively, we find that some directed graphs are faster mixing than their undirected counterparts, whereas the general pattern is that directed graphs are slower mix- ing than undirected ones. To relate to the applications sug- gested in the literature, we measure how directionality of edges in several social graphs impact these applications, and find that evaluation on the undirected graphs always over- estimates the security provided by these schemes.
Publisher
ACM/SIGSAC
Issue Date
2012-10
Language
English
Citation

ACM Symposium on Information, Computer and Communications Security (ASIACCS 2012)

Citation
Journal of Control, Automation and Systems Engineering, Vol.10, No.12, pp.1217-1222
URI
http://hdl.handle.net/10203/8421
Appears in Collection
EE-Conference Papers(학술회의논문)
Files in This Item
asiaccs2012.pdf(367.14 kB)Download

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0