How likely is a random network graph shift-enabled?

Chen, Liyan and Cheng, Samuel and Stankovic, Vladimir and Stankovic, Lina and Shi, Qingjiang (2022) How likely is a random network graph shift-enabled? IEEE Transactions on Signal and Information Processing over Networks, 8. pp. 973-982. ISSN 2373-7778 (https://doi.org/10.1109/TSIPN.2022.3216099)

[thumbnail of Chen-IEEETSIPN-2022-How-likely-is-a-random-network-graph-shift-enabled]
Preview
 Text. Filename: Chen_IEEETSIPN_2022_How_likely_is_a_random_network_graph_shift_enabled.pdf
Accepted Author Manuscript
License: Strathprints license 1.0
Download (1MB)| Preview

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.

  • Item type:Article
    ID code:82808
    Dates:
    Date
    Event
    7 December 2022
    Published
    10 October 2022
    Accepted
    Notes:© 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting /republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
    Subjects:Technology > Electrical engineering. Electronics Nuclear engineering
    Department:Faculty of Engineering > Electronic and Electrical Engineering
    Depositing user: Pure Administrator
    Date deposited:18 Oct 2022 09:33
    Last modified:29 Apr 2024 12:25
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/82808
CORE (COnnecting REpositories)