On the Mixing Time of Directed Social Graphs and Security Implications

Abstract

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.