The graph Laplacian is a tool which is commonly used in different applications, amongst which spectral clustering. This report contains a research in different def- initions for the graph Laplacian applied on directed graphs, since it is rarely used in applications neither occurs
...
The graph Laplacian is a tool which is commonly used in different applications, amongst which spectral clustering. This report contains a research in different def- initions for the graph Laplacian applied on directed graphs, since it is rarely used in applications neither occurs often in literature. Two definitions are discussed into more detail. The first definition considers a directed graph as a bipartite graph between the node set containing all nodes with outgoing edges and the node set containing all nodes with incoming edges. A Laplacian is defined on both sets distinctly and later on the two Laplacians are convexly combined to define a Laplacian on the whole directed graph. The second definition considers a random walk on a directed graph. We will see why a random walk on a directed graph is equivalent to a finite Markov Chain with a corresponding transition probability matrix. This definition will be used for clustering. The method for clustering as well as the definition for the directed graph Lapla- cian require a unique stationary distribution associated with the transition proba- bilities on the node set of the graph. The existence and uniqueness of the stationary distribution became an important part of this report, because the given data set has to meet up with these properties to be able to use this method. Furthermore, the introduced definitions are used in a MATLAB based model, to get more insights about the spectrum of the directed graph Laplacian. The biggest conclusions to be drawn are that for strongly connected directed graphs, it seems that there is a correlation between the multiplicity of eigenvalues that are close to 1 and the numbers of subsets such that all nodes in the subset are adjacent.