Paper Info
Title
Bounds on the Spectral Radius of Digraphs from Subgraph Counts
Abstract
The spectral radius of a directed graph is a metric that can only be computed when the structure of the network is completely known. However, in many practical scenarios, it is not possible to exactly retrieve the whole structure of the network; hence, the exact value of the spectral radius is not computable. Even in these scenarios, it is typically possible to extract local structural properties of a network using, for example, graph crawlers. In this paper, we develop a novel measure-theoretic framework to upper and lower bound the spectral radius of a directed graph using local structural information, in particular, using the counts of a collection of small subgraphs or motifs. Our framework is based on recent results relating the multivariate moment problem with semidefinite programming. Using these results, we develop a hierarchy of (small) semidefinite programs whose solutions provide upper and lower bounds on the spectral radius of a directed graph using, solely, subgraph and motif counts. We numerically validate the quality of our bounds using both random and real-world directed graphs.
Year
DOI
Venue
2020
10.1137/19M1256312
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS
Keywords
DocType
Volume
directed graph,spectral radius,moment problem,semidefinite programming
Journal
41
Issue
ISSN
Citations 
2
0895-4798
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Ximing Chen142.12
Masaki Ogura24413.38
Victor M. Preciado320529.44