Clustered low rank approximation of graphs in information science applications
2011 (English)In: Proceedings of the SIAM International Conference on Data Mining (SDM), 2011, 164-175 p.Conference paper (Refereed)
In this paper we present a fast and accurate procedure called clusteredlow rank matrix approximation for massive graphs. The procedure involvesa fast clustering of the graph and then approximates each clusterseparately using existing methods, e.g. the singular value decomposition,or stochastic algorithms. The cluster-wise approximations are thenextended to approximate the entire graph. This approach has severalbenets: (1) important community structure of the graph is preserveddue to the clustering; (2) highly accurate low rank approximationsare achieved; (3) the procedure is ecient both in terms of computationalspeed and memory usage; (4) better performance in problems from variousapplications compared to standard low rank approximation. Further,we generalize stochastic algorithms to the clustered low rank approximationframework and present theoretical bounds for the approximation error.Finally, a set of experiments, using large scale and real-world graphs,show that our methods outperform standard low rank matrix approximationalgorithms.
Place, publisher, year, edition, pages
2011. 164-175 p.
Computational Mathematics Other Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-73728OAI: oai:DiVA.org:liu-73728DiVA: diva2:476343