How likely is a random network graph shift-enabled?

Liyan Chen, Samuel Cheng, Vladimir Stankovic, Lina Stankovic, Qingjiang Shi

Research output: Contribution to journalArticlepeer-review

Abstract

In graph signal processing, the shift-enabled property of an underlying graph is essential in designing distributed filters. This article discusses when a random network graph is shift-enabled. In particular, popular network graph models Erdos–Renyi (ER), Watts–Strogatz (WS), Barabasi–Albert (BA) for both weighted and unweighted are considered. Moreover, both balanced and unbalanced signed graphs constructing using ER are considered. Our results show that the considered unweighted connected random network 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. Finally, we evaluate the shift-enabled property of nine real-world graphs. The experimental results are consistent with our findings on randomly generated data. The results provide the basis for the filter design in a graph network.
Original languageEnglish
Pages (from-to)973-982
Number of pages10
JournalIEEE Transactions on Signal and Information Processing over Networks
Volume8
DOIs
Publication statusPublished - 7 Dec 2022

Keywords

  • graph signal processing
  • shift-enabled graphs
  • random network graph
  • filtering

Fingerprint

Dive into the research topics of 'How likely is a random network graph shift-enabled?'. Together they form a unique fingerprint.

Cite this