Learning low-rank latent mesoscale structures in networks

Hanbaek Lyu; Yacoub H Kureh; Joshua Vendrow; Mason A Porter

doi:10.1038/s41467-023-42859-2

Learning low-rank latent mesoscale structures in networks

Nat Commun. 2024 Jan 3;15(1):224. doi: 10.1038/s41467-023-42859-2.

Authors

Hanbaek Lyu¹, Yacoub H Kureh², Joshua Vendrow³, Mason A Porter^{2

4

5}

Affiliations

¹ Department of Mathematics, University of Wisconsin-Madison, Madison, WI, 53706, USA. hlyu@math.wisc.edu.
² Department of Mathematics, University of California, Los Angeles, CA, 90095, USA.
³ Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA.
⁴ Department of Sociology, University of California, Los Angeles, CA, 90095, USA.
⁵ Santa Fe Institute, Sante FE, NM, 87501, USA.

Abstract

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.

Abstract

Grants and funding