The Mahout math package has a number of basic algorithms that use
algorithmic efficiencies when given sparse graphs.
A number of other algorithms use only the product of a sparse matrix on
another matrix or a vector. Since these algorithms never change the
original sparse matrix, they are safe against fillin problems.
The random projection technique avoids O(v^3) algorithms for computing SVD
or related matrix decompositions. See http://arxiv.org/abs/0909.4061 and
https://issues.apache.org/jira/browse/MAHOUT376
None of these these algorithms are specific to graph theory, but all deal
with methods that are useful with sparse graphs.
On Wed, Dec 22, 2010 at 10:46 AM, Ricky Ho <rickyphyllis@yahoo.com> wrote:
> Can you point me to Matrix algorithms that is tuned for sparse graph ?
> What I
> mean is from O(v^3) to O(v*e) where v = number of vertex and e = number of
> edges.
>
