Transcription of Spectral Graph Theory and its Applications
{{id}} {{{paragraph}}}
Example: air traffic controller
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 then Laplacian: natural quadratic form on graphswhere D is diagonal matrix of degrees1234 Laplacian: fast factsso, zero is an eigenvalueIf k connected components, Fiedler ( 73) called algebraic connectivity of a Graph The further from 0, the more Graph in line (Hall 70)mapminimizetrivial solution: So, requireSolutionAtkins, Boman, Hendrickson 97:Gives correct embedding for gr
Spectral graph drawing: FEM justification If apply finite element method to solve Laplace’s equation in the plane with a Delaunay triangulation Would get graph Laplacian, but with some weights on edges Fundamental solutions are x and y coordinates (see Strang’s Introduction to Applied Mathematics)
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: