English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

A Combinatorial View of Graph Laplacians

MPS-Authors
/persons/resource/persons83983

Huang,  J
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;
Max Planck Institute for Biological Cybernetics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

MPIK-TR-144.pdf
(Publisher version), 204KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Huang, J.(2005). A Combinatorial View of Graph Laplacians (144). Tübingen, Germany: Max Planck Institute for Biological Cybernetics.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0013-D499-0
Abstract
Discussions about different graph Laplacian, mainly normalized and unnormalized versions of graph Laplacian, have been ardent with respect to various methods in clustering and graph based semi-supervised learning. Previous research on graph Laplacians investigated their convergence properties to Laplacian operators on continuous manifolds. There is still no strong proof on convergence for the normalized Laplacian. In this paper, we analyze different variants of graph Laplacians directly from the ways solving the original graph partitioning problem. The graph partitioning problem is a well-known combinatorial NP hard optimization problem. The spectral solutions provide evidence that normalized Laplacian encodes more reasonable considerations for graph partitioning. We also provide some examples to show their differences.