# Graph-Based Resource Allocation for Integrated Space and Terrestrial Communications
## 3 Graphs for Signal Processing in Wireless Networks  
Applying Graph Theory to signal processing has recently attracted significantly more attention in the Telecommunications Engineering community, which is emphasized by the successful implementation of such approaches for diverse problems in the areas of services supplied via social networks, cognitive radio, and vehicular networks organization, and more [14,15]. These and other potential applications require rigorous analysis of the different domains which are involved in the explored data's generation. The graph consists of three primary elements: vertices, edges, and directivity (the last one being optional). Vertices are the data points on a graph, and they usually carry information about the amplitude/value and physical position of the signal measurement sample. The vertices are labeled according to their physical meaning, and therefore the labels are not necessarily ordered numbers. The edges connect these vertices, which are related to each other in some domain. Their relationships between two vertices can be binary (0--they are not related and thus, there is no edge between them, and 1--otherwise) or variable (each existing relationship has a certain weight (weighted graphs)). Should there be any directionality in the way vertices are organized (hence introducing yet another information domain), arrows are placed on the edges to signify the direction in which two data points are related to one another. Such graphs are directed, whereas their alternatives are called undirected. A graph is analytically defined as \(\mathcal{G}=\{\mathcal{V},\mathcal{B}\}\), i.e., a set of vertices \(\mathcal{V}\) connected by the edges contained in the set \(\mathcal{B}\), such that \(\mathcal{B}\subset\mathcal{V}\times\mathcal{V}\), \(\times\) being the direct product operator. The relationship (edge) between vertices (nodes) \(m\) and \(n\) is described as \((m,n)\subset\mathcal{B}\). The complete set of \(\mathcal{B}\) is composed of all connections between the vertices which are related to each other. In an indirected graph, the connections are in both directions, whereas for the directed, they are made in a specified direction. In order to describe the way in which the sets of vertices and edges are related, a number of matrices are used to find solutions inspired by the relationships in different domains modeled via graphs [16]:  
* Adjacency matrix \(\mathbf{A}\). The most important mathematical description of the graph, the adjacency matrix of size \(N\times N\) (\(N\) is the number of vertices) which describes the connectivity between edges and vertices. The columns of \(\mathbf{A}\) show the connections of each vertex to the rest. * Incidence matrix \(\mathbf{B}\). It is similar to the adjacency matrix, but its dimensions are \(M\times N\) (\(M\) is the number of edges). For undirected graphs, there are ones on all positions which indicate a vertex connected to an edge. * Weight \(\mathbf{W}\) matrix. Its dimensions and the positions of the non-zero elements match those of the adjacency matrix. The weight matrix can be obtained by replacing the non-zero values of \(\mathbf{A}\) with coefficients (the edges' weights) that carry physical meaning in some domain and are defined according to it. * Degree matrix \(\mathbf{D}\). Its dimensions are \(N\times N\), and it contains the sum of the weights of all edges connected to each of the vertices. So \(\mathbf{D}\) shows that the importance of each vertex in the overall graph structure can be determined. * Laplacian matrix \(\mathbf{L}\). This is derived from the matrices above and is significant for practical signal processing applications. The Laplacian matrix is defined as \(\mathbf{L}=\mathbf{D}-\mathbf{W}\). Its dimensions are \(N\times N\), and it is characterized by positive elements on the diagonal and negative on the off-diagonal non-zero elements. Some metrics that arise from the connected structure of the graph are the following.