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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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
Identifiers
URN: urn:nbn:se:liu:diva-73728OAI: oai:DiVA.org:liu-73728DiVA: 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

http://siam.omnibooksonline.com/2011datamining/data/papers/080.pdf#page=1

Authority records BETA

Savas, Berkant

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 366 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf