Spectral Graph Theory and its Applications

Spectral Graph Theoryand its ApplicationsDaniel A. SpielmanDept. of Computer ScienceProgram in Applied MathematicsYale UnviersityOutlineAdjacency matrix and LaplacianIntuition, Spectral Graph drawingPhysical intuitionIsomorphism testingRandom walksGraph Partitioning and clusteringDistributions of eigenvalues and compressionComputationWhat I m SkippingMatrix-tree of algebraic Graph graphs ( Cayley graphs).Connections to codes and of work by Adjacency Matrix1234 is eigenvalue and v is eigenvector ifThink of , or even better Symmetric -> n real eigenvalues andreal eigenvectors form orthonormal basis : invariant under : invariant under and Quadratic FormsView of A as an operator:View of A as quadratic form:if and

Spectral graph drawing: Tutte justification Gives for all i λsmall says x(i) near average of neighbors Tutte ‘63: If fix outside face, and let every other vertex be average of neighbors, get planar embedding of planar graph.

Loading..

Tags:

  Applications, Theory, Graph, Spectral, Spectral graph theory and its applications

Information

Related search queries