This paper presents a concise tutorial on spectral clustering for broad spectrum graphs which include unipartite (undirected) graph, bipartite graph, and directed graph. We show how to transform bipartite graph and directed graph into corresponding unipartite graph, therefore allowing a unified treatment to all cases. In bipartite graph, we show that the relaxed solution to the @math -way co-clustering can be found by computing the left and right eigenvectors of the data matrix. This gives a theoretical basis for @math -way spectral co-clustering algorithms proposed in the literatures. We also show that solving row and column co-clustering is equivalent to solving row and column clustering separately, thus giving a theoretical support for the claim: column clustering implies row clustering and vice versa''. And in the last part, we generalize the Ky Fan theorem---which is the central theorem for explaining spectral clustering---to rectangular complex matrix motivated by the results from bipartite graph analysis.
@cite_16 discuss how to extend the so-called modularity---which is equivalent to the graph cuts objective---of unipartite graph to directed graph. They form an asymmetric modularity matrix @math by applying modularity function to emphasizes the importance of the edge directions to the original asymmetric af finity matrix @math , and then transform @math into a symmetric matrix by adding @math to its transpose. The clustering is done by calculating the first @math eigenvectors of this symmetric matrix. This is equivalent to applying to @math .
@cite_16
2063251739
We consider the problem of finding communities or modules in directed networks. In the past, the most common approach to this problem has been to ignore edge direction and apply methods developed for community discovery in undirected networks, but this approach discards potentially useful information contained in the edge directions. Here we show how the widely used community finding technique of modularity maximization can be generalized in a principled fashion to incorporate information contained in edge directions. We describe an explicit algorithm based on spectral optimization of the modularity and show that it gives demonstrably better results than previous methods on a variety of test networks, both real and computer generated.