Thermodynamics of complex networks and other discrete systems from non-equilibrium ensembles of random walks

Large-scale networks represent a broad spectrum of systems in nature, science, and technology. Computer networks such as the World Wide Web and the Internet, social networks such as Twitter and Facebook, and knowledge-sharing online platforms such as Wikipedia exert considerable influence on our everyday lives. Many of these networks are very large and evolve with time, making investigation of their statistical properties a challenging task. I will describe a novel methodology, based on random walks, for the inference of statistical properties of complex networks with weighted or unweighted edges [1]. I will show how this formalism can yield reliable estimates of various network statistics, such as the network size, after only a small fraction of network nodes has been explored. I will introduce two novel algorithms for partitioning network nodes into non-overlapping communities - a key step in revealing network modularity and hierarchical organization [2]. These clustering tools will be applied to various benchmarks, including a large-scale map of roads and intersections in the state of Colorado. Finally, I will demonstrate how these ideas can be extended to computing various thermodynamic quantities in discrete systems such as spin glasses from small non-equilibrium samples of states. In summary, I will demonstrate how random walks can be used to reveal modular organization and global structure of complex networks and infer key statistical mechanics quantities that are otherwise not easily accessible.