The impossibility of low-rank representations for triangle-rich complex networks
Abstract
Our main message is that the popular method of low-dimensional embeddings provably cannot capture important properties of real-world complex networks. A widely used algorithmic technique for modeling these networks is to construct a low-dimensional Euclidean embedding of the vertices of the network, where proximity of vertices is interpreted as the likelihood of an edge. Contrary to common wisdom, we argue that such graph embeddings do not capture salient properties of complex networks. We mathematically prove that low-dimensional embeddings cannot generate graphs with both low average degree and large clustering coefficients, which have been widely established to be empirically true for real-world networks. This establishes that popular low-dimensional embedding methods fail to capture significant structural aspects of real-world complex networks.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Mar 02, 2020
- Source ID
- 10.1073/pnas.1911030117
Entities
People
- Andrew Stolman
- Aneesh Sharma
- Ashish Goel
- C. Seshadhri
Organizations
- Army Research Office
- National Science Foundation
- Stanford University
- University of California, Santa Cruz