  As decentralized computing scenarios get ever more popular, unstructured
topologies are natural candidates to consider running mix networks upon. We
consider mix network topologies where mixes are placed on the nodes of an
unstructured network, such as social networks and scale-free random networks.
We explore the efficiency and traffic analysis resistance properties of mix
networks based on unstructured topologies as opposed to theoretically optimal
structured topologies, under high latency conditions. We consider a mix of
directed and undirected network models, as well as one real world case study --
the LiveJournal friendship network topology. Our analysis indicates that
mix-networks based on scale-free and small-world topologies have, firstly,
mix-route lengths that are roughly comparable to those in expander graphs;
second, that compromise of the most central nodes has little effect on
anonymization properties, and third, batch sizes required for warding off
intersection attacks need to be an order of magnitude higher in unstructured
networks in comparison with expander graph topologies.
