Exploration of local and global properties of complex networks with random walks
| When |
May 20, 2022
from 02:00 to 03:00 |
|---|---|
| Where | Room M7 101 |
| Attendees |
Alexandre Morozov |
| Add event to calendar |
vCal
iCal
|
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 also present two novel algorithms for partitioning network nodes into non-overlapping communities - a key step in revealing network modularity and hierarchical organization [2]. The walk-likelihood algorithm (WLA) produces an optimal partition of network nodes into a given number of communities, while the walk-likelihood community finder (WLCF) can predict both the optimal number of communities and the corresponding network partition. I will discuss applications of these tools to various benchmarks, including a large-scale map of roads and intersections in the state of Colorado. These applications will demonstrate how random walks can be used to reveal modular organization and global structure of complex networks.
References
1. Kion-Crosby, W.B. and Morozov, A.V. (2018) Phys Rev Lett 121, 038301
2. Ballal, A., Kion-Crosby, W.B. and Morozov, A.V. (2022) arXiv:2202.11171