Computation of Graph Fourier Transform Centrality Using Graph Filter

Abstract

In this paper, the computation of graph Fourier transform centrality (GFTC) of complex network using graph filter is presented. For conventional computation method, it needs to use the non-sparse transform matrix of graph Fourier transform (GFT) to compute GFTC scores. To reduce the computational complexity of GFTC, a linear algebra method based on Frobenius norm of error matrix is applied to convert the spectral-domain GFTC computation task to vertex-domain one such that GFTC can be computed by using polynomial graph filtering method. There are two kinds of designs of graph filters to be studied. One is the graph-aware method; the other is the graph-unaware method. The computational complexity comparison and experimental results show that the proposed graph filter method is more computationally efficient than conventional GFT method because the sparsity of Laplacian matrix is used in the implementation structure. Finally, the centrality computations of social network, metro network and sensor network are used to demonstrate the effectiveness of the proposed GFTC computation method using graph filter.

Keywords

• Graph signal processing
• complex network
• node centrality
• graph Fourier transform
• graph filter