0
$\begingroup$

i am studying the solver for PageRank problems which drived from the web link graph.

I have tried using METIS to divided the matrix into subdomains, but METIS can only produce subdomains with nearly equal size. For the web link graph, it usually has blocks with different sizes because the domain or host of pages has different sizes.

So, i want to find a method to divide the graph to subdomain with different sizes adaptively. Is there such a method or how can i do this?

Thank you

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ It's not entirely clear what you're trying to adapt for or what your end goal is. Are you solving the eigenvalue problem for the PageRank algorithm? The manner in which you decompose the matrix to solve this problem in parallel should not affect the solution you get. Or are you examining the more general problem of network community detection? $\endgroup$
    – Daniel Shapero
    Apr 2, 2015 at 18:13

1 Answer 1

Reset to default
3
$\begingroup$

If different nodes have different costs, for example because different rows of your matrix have different numbers of nonzero entries, then you need to attach weights to each node of your graph. Graph partitioning algorithms such as METIS allow you to do this, creating partitions where it is not the number of nodes that are about equal between partitions, but where the sum of weights of nodes are about equal.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.