Beyond the expanders

DOI10.1155/2011/787596MaRDI QIDQ666522zbMATH OpenOpenAlexWikidataFDO

Authors Marianna Bolla

Publication date 8 March 2012

Published in International Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.5926

zbMATH Keywords

random walkspectral walk

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (including graph drawing) in computer science (68R10) Random walks on graphs (05C81) Network design and communication in computer systems (68M10)

Abstract: Expander graphs are widely used in communication problems and construction of error correcting codes. In such graphs, information gets through very quickly. Typically, it is not true for social or biological networks, though we may find a partition of the vertices such that the induced subgraphs on them and the bipartite subgraphs between any pair of them exhibit regular behavior of information flow within or between the subsets. Implications between spectral and regularity properties are discussed.

Recommendations

• Expander graphs in pure and applied mathematics
• Expander graphs and their applications
• scientific article; zbMATH DE number 7052900
• scientific article; zbMATH DE number 5010757
• On new expanders of unbounded degree for practical applications in informatics

Cites work

• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Community structure in social and biological networks
• Eigenvalues and expanders
• Expander graphs and their applications
• Generalized quasirandom graphs
• Noisy random graphs and their laplacians
• Optimization problems for weighted graphs and related correlation estimates
• Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
• Quasi‐random graphs with given degree sequences
• Spectra and optimal partitions of weighted graphs
• Szemerédi's lemma for the analyst
• The spectral gap of random graphs with given expected degrees

Cited in

(16)

• Extended rate, more GFUN
• Dimension expanders
• Spectra and structure of weighted graphs
• A continuum of expanders
• DEX: self-healing expanders
• Beyond the KdV: Post-explosion development
• Expanders -- how to find them, and what to find in them
• Bipartite multigraphs with expander-like properties
• Modularity spectra, eigen-subspaces, and structure of weighted graphs
• Extended Vuza canons
• Expander graphs in pure and applied mathematics
• 60/102 null boundary cellular automata based expander graphs
• Better expanders and superconcentrators
• On new expanders of unbounded degree for practical applications in informatics
• Expanders and dimensional expansion
• Löwner Expansions

This page was built for publication: Beyond the expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q666522)