The impossibility of low-rank representations for triangle-rich complex networks.

ABSTRACT: The study of complex networks is a significant development in modern science, and has enriched the social sciences, biology, physics, and computer science. Models and algorithms for such networks are pervasive in our society, and impact human behavior via social networks, search engines, and recommender systems, to name a few. A widely used algorithmic technique for modeling such complex 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 the common view, we argue that such graph embeddings do not capture salient properties of complex networks. The two properties we focus on are low degree and large clustering coefficients, which have been widely established to be

SUBMITTER: Seshadhri C 

PROVIDER: S-EPMC7084093 | biostudies-literature | 2020 Mar

REPOSITORIES: biostudies-literature