Читать книгу Artificial Intelligence and Quantum Computing for Advanced Wireless Networks - Savo G. Glisic - Страница 92

Graph signals: A graph signal is a collection of values defined on a complex and irregular structure modeled as a graph. In this appendix, a graph is represented as , where is the set of vertices (or nodes) and W is the weight matrix of the graph in which an element w_ij represents the weight of the directed edge from node j to node i. A graph signal is represented as an

N‐dimensional vector f = [f(1), f(2), …, f(N)]^T ∈ ℂ^N, where f(i) is the value of the graph signal at node i and is the total number of nodes in the graph.

Directed Laplacian: As discussed in Appendix 5.A, the graph Laplacian for undirected graphs is a symmetric difference operator L=D − W, where D is the degree matrix of the graph, and W is the weight matrix of the graph. In the case of directed graphs (or digraphs), the weight matrix W of a graph is not symmetric. In addition, the degree of a vertex can be defined in two ways: in‐degree and out‐degree. The in‐degree of a node i is estimated as , whereas the out‐degree of the node i can be calculated as . We consider an in‐degree matrix and define the directed Laplacian L of a graph as

(5.B.1)

where D_in= diag is the in‐degree matrix. Figure 5.B.1 shows an example of weighted directed graph, with the corresponding matrices [68]. The Laplacian for a directed graph is not symmetric; nevertheless, it follows some important properties: (i) the sum of each row is zero, and hence λ = 0 is certainly an eigenvalue, and (ii) real parts of the eigenvalues are non‐negative for a graph with positive edge weights.

Figure 5.B.1 A directed graph and the corresponding matrices.

Graph Fourier transform based on directed Laplacian: Using Jordan decomposition, the graph Laplacian is decomposed as

(5.B.2)

where J, known as the Jordan matrix, is a block diagonal matrix similar to L, and the Jordan eigenvectors of L constitute the columns of V. We define the graph Fourier transform (GFT) of a graph signal f as

(5.B.3)

Here, V is treated as the graph Fourier matrix whose columns constitute the graph Fourier basis. The inverse graph Fourier transform can be calculated as

(5.B.4)

In this definition of GFT, the eigenvalues of the graph Laplacian act as the graph frequencies, and the corresponding Jordan eigenvectors act as the graph harmonics. The eigenvalues with a small absolute value correspond to low frequencies and vice versa. Before discussing the ordering of frequencies, we consider a special case when the Laplacian matrix is diagonalizable.

Diagonalizable Laplacian matrix: When the graph Laplacian is diagonalizable, Eq. (5.B.2) is reduced to

(5.B.5)

Here, Λ ∈ ℂ^{N × N} is a diagonal matrix containing the eigenvalues λ₀, λ₁ , …, λ_{N − 1} of L, and V = [v₀, v₁, …, v_{N − 1}] ∈ ℂ^{N × N} is the matrix with columns as the corresponding eigenvectors of L. Note that for a graph with real non‐negative edge weights, the graph spectrum will lie in the right half of the complex frequency plane (including the imaginary axis).

Undirected graphs: For an undirected graph with real weights, the graph Laplacian matrix L is real and symmetric. As a result, the eigenvalues of L turn out to be real, and L constitutes orthonormal set of eigenvectors. Hence, the Jordan form of the Laplacian matrix for undirected graphs can be written as

(5.B.6)

where V^T = V⁻¹, because the eigenvectors of L are orthogonal in th undirected case. Consequently, the GFT of a signal f can be given as , and the inverse can be calculated as f=V. One can show that for the example from Figure 5.B.1 for the signal f = [0.12 0.38 0.81 0.24 0.88] we have the GFT as