Recovering the structure of random linear graphs

DOI10.1016/j.laa.2018.07.029zbMath1396.05103arXiv1704.03189OpenAlexW2963470155MaRDI QIDQ1790469

Israel Rocha, Nauzer Kalyaniwalla, Jeannette C. M. Janssen

Publication date: 2 October 2018

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1704.03189

zbMATH Keywords

random matricesrandom graphsToeplitz matricesstochastic block modelrank correlation coefficientseriation problem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Reconstruction of line-embeddings of graphons ⋮ Projective, sparse and learnable latent position network models ⋮ Layout of random circulant graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple linear time recognition of unit interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Layout of random circulant graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Random matrices: universality of local spectral statistics of non-Hermitian matrices
• Modern Aspects of Random Matrix Theory
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Random Geometric Graphs
• A Simple SVD Algorithm for Finding Hidden Partitions
• Seriation and matrix reordering methods: An historical overview
• Finding Hidden Cliques in Linear Time with High Probability
• The Rotation of Eigenvectors by a Perturbation. III
• Spectral Properties of Banded Toeplitz Matrices

This page was built for publication: Recovering the structure of random linear graphs