How likely is a random graph shift-enabled?

Abstract

The shift-enabled property of an underlying graph is essential in designing distributed filters. This article discusses when a random graph is shift-enabled. In particular, popular graph models ER, WS, BA random graph are used, weighted and unweighted, as well as signed graphs. Our results show that the considered unweighted connected random graphs are shift-enabled with high probability when the number of edges is moderately high. However, very dense graphs, as well as fully connected graphs, are not shift-enabled. Interestingly, this behaviour is not observed for weighted connected graphs, which are always shift-enabled unless the number of edges in the graph is very low.

arXiv comment9 pages

References in corpus (8)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Discrete Signal Processing on Graphs
• GSPBOX: A toolbox for signal processing on graphs
• Stationary Graph Processes and Spectral Estimation
• Graph signal processing for machine learning: A review and new perspectives
• Signal Processing on Graphs: Causal Modeling of Unstructured Data