Dynamix

In this paper we advance communication using social networks in two directions by considering dynamics of social graphs. First, we formally define the problem of routing on dynamic graphs and show an interesting and intuitive connection between graph dynamics and random walks on weighted graphs; graphs in which weights summarize history of edge dynamics and allow for future dynamics to be used as weight adjustment. Second, we present several measurements of our proposed model on dynamic graphs extracted from real-world social networks and compare them to static structures driven from the same graphs. We show several interesting trade-offs and highlight the potential of our model to capture dynamics, enrich graph structure, and improves the quantitative sender anonymity when compared to the case of static graphs.