Transcription of Spectral Graph Theory and its Applications
{{id}} {{{paragraph}}}
Example: tourism industry
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 graphs likeCourant-Fischer defi
Adjacency matrix and Laplacian Intuition, spectral graph drawing Physical intuition Isomorphism testing ... Fundamental solutions are x and y coordinates ... Some pairs have an exponential number of isomorphisms. Ex.: Strongly regular graphs with only 3 eigenvalues,
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: