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_9 propose a method for transforming the af finity matrix induced from a directed graph into a symmetric matrix without ignoring the edge directions. So, clustering algorithms built for unipartite graph can be applied unchanged.
@cite_9
1551713770
To identify communities in directed networks, we propose a generalized form of modularity in directed networks by presenting the quantity LinkRank, which can be considered as the PageRank of links. This generalization is consistent with the original modularity in undirected networks and the modularity optimization methods developed for undirected networks can be directly applied to directed networks by optimizing our modified modularity. Also, a model network, which can be used as a benchmark network in further community studies, is proposed to verify our method. Our method is supposed to find communities effectively in citation- or reference-based directed networks.