Text
Spectrum Consistent Coarsening Approximates Edge Weights
Finding coarse representations of large graphs which preserve particular features is important in many fields of study, including clustering, numerical approximation, and the creation of reduced order models. Likewise, preserving spectral properties of the original graph during coarsening is also of particular interest for several domains of study. Our contributions are twofold. First, we generalize previous work on coarsening graphs while preserving eigenvalues of the normalized Laplacian by merging nodes with similar adjacencies, and we show that a similar analysis can be done in the case of the combinatorial Laplacian. We additionally show that when the lifted graph of a coarsening spectrally approximates the original graph, the difference between the edge weights of the graph and the edge weights of the lift depend only on the quality of spectral approximation and the strength of connectivity of the graph. It is then shown that in the case of weighted regular graphs the difference between the edge weights of the graph and the edge weights of the lift are bounded purely by the quality of spectral approximation.
Barcode | Tipe Koleksi | Nomor Panggil | Lokasi | Status | |
---|---|---|---|---|---|
art147307 | null | Artikel | Gdg9-Lt3 | Tersedia namun tidak untuk dipinjamkan - No Loan |
Tidak tersedia versi lain