# Time complexity of clustering based on random walk

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:

1. 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$.

2. 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}$.

3. 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.