Graph theory is an interesting topic and a powerful tool for tackling non-Euclidean data, such as social networks, molecular structures, telecommunication networks, and traffic networks. These kind of data are of unregular non-grid structure, which can be represented more effectively by graph.
These are some real-life examples of networks. Even though they have different semantic meanings, all of them can be represented by a GRAPH.
So… a graph has three key elements: nodes, edges and weighting function.
Based on feature similarity, edges are built between pairwise nodes, which can be unweighted or weighted value. In the unweighted case, edges are equal to 1 if two nodes are connected, otherwise edge = 0. In the weighted case, we use a weighting function to produce a weighted edge value between pairwise nodes. Gaussian (heat) kernel is a simple but effective fuction commonly used.
With these three key elements, we consider two aspects to construct a graph:
1). Similarity metric:
Euclidean distance and Spectral angle distance are two popular metric used in many research. The definition is as follows, respectively:
2). Graph creation method:
Graph creation method is used to decide which edges to keep, then we assign appropriate weights to the connected edges via a weighting function. $$E_0=mc^2$$
$$\epsilon$$
Take Hyperspectral imagery (HSI) data as example, it’s a 3-D datacube, denoted by [H,W,B], here H/W is the number of row/column of 2D spatial image, which referred to as one slice in the datacube, B is the number of spectral bands.