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.
