Learning low-rank latent mesoscale structures in networks.

Researchers in many fields use networks to represent interactions between entities in complex systems. To study the large-scale behavior of complex systems, it is useful to examine mesoscale structures in networks as building blocks that influence such behavior. In this paper, we present an approach to describe low-rank mesoscale structures in networks. We find that many real-world networks possess a small set of latent motifs that effectively approximate most subgraphs at a fixed mesoscale. Such low-rank mesoscale structures allow one to reconstruct networks by approximating subgraphs of a network using combinations of latent motifs. Employing subgraph sampling and nonnegative matrix factorization enables the discovery of these latent motifs. The ability to encode and reconstruct networks using a small set of latent motifs has many applications in network analysis, including network comparison, network denoising, and edge inference. Network structures can be examined at different scales, and subnetworks in the form of motifs can provide insights into global network properties. The authors propose an approach to decompose a network into a set of latent motifs, which can be used for network comparison, network denoising, and edge inference. [ABSTRACT FROM AUTHOR]