liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Clustered low rank approximation of graphs in information science applications
University of Texas at Austin..ORCID iD: 0000-0002-1542-2690
University of Texas at Austin..
2011 (English)In: Proceedings of the SIAM International Conference on Data Mining (SDM), 2011, 164-175 p.Conference paper (Refereed)
Abstract [en]

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.
National Category
Computational Mathematics Other Computer and Information Science
URN: urn:nbn:se:liu:diva-73728OAI: diva2:476343
Available from: 2012-01-12 Created: 2012-01-12 Last updated: 2013-10-11

Open Access in DiVA

No full text

Other links

Search in DiVA

By author/editor
Savas, Berkant
Computational MathematicsOther Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 251 hits
ReferencesLink to record
Permanent link

Direct link