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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.