1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.