What is the time complexity of the following algorithm (from this paper suggested by Zhou) to partition directed graph?Can I use the complexity of eigen vector computation for this purpose?The Algorithm: Given a directed graph $G = (V,E)$, it may be partitioned into two parts as follows:  Define a random walk over $G$ with a transition probability matrix $P$ such that it has a unique stationary distribution. In this part I need to compute the eigen vectror transition matrix $P$.  Let $\Pi$ denote the diagonal matrix with its diagonal elements being the stationary distribution of the random walk. Form the matrix $ = \frac{(\Pi^{1/2}P\Pi^{-1/2} + \Pi^{-1/2}P{T}\Pi^{1/2})}{2}$.Compute an eigenvector $\phi$ of $\theta$ corresponding to the second largest eigenvalue, and then partition the vertex set $V$ of $G$ into the two parts.
Time complexity of clustering based on random walk
graph algorithms;optimization;time complexity;linear algebra;clustering