Transcription of Spectral Graph Theory and its Applications
{{id}} {{{paragraph}}}
Example: confidence
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 definition of eigvals/vecs(here ) Embedding Graph in plane (Hall 70)minimizemaptrivial solution.
What I’m Skipping Matrix-tree theorem. Most of algebraic graph theory. Special graphs (e.g. Cayley graphs). Connections to codes and designs. Lots of work by theorists.
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: