Christoph Helmberg, Susanna Reiss : A note on Fiedler vectors interpreted as graph realizations
- Author(s):
-
Christoph Helmberg
Susanna Reiss
- Title:
- A note on Fiedler vectors interpreted as graph realizations
- Electronic source:
-
application/pdf
- Preprint series:
- Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 1, 2010
- Mathematics Subject Classification:
-
05C50 [ Graphs and matrices ] 90C22 [ Semidefinite programming ] 90C35 [ Programming involving graphs or networks ] 05C10 [ Topological graph theory, imbedding ] 05C78 [ Graph labelling ] - Abstract:
- The second smallest eigenvalue of the Laplace matrix of a graph and its eigenvectors, also known as Fiedler vectors in spectral graph partitioning, carry significant structural information regarding the connectivity of the graph. Using semidefinite programming duality we offer a geometric interpretation of this eigenspace as optimal solution to a graph realization problem. A corresponding interpretation is also given for the eigenspace of the maximum eigenvalue of the Laplacian.
- Keywords:
-
spectral graph theory,
semidefinite programming,
eigenvalue optimization,
embedding,
graph partitioning
- Language:
- English
- Publication time:
- 01/2010
