It Is Better to Be Semi-Regular When You Have a Low Degree
Theodore Kolokolnikov, Lu Wei · 2024
Read It Is Better to Be Semi-Regular When You Have a Low Degree by Theodore Kolokolnikov, Lu Wei (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/pmc-11727215.txt.
Description
How well connected a network is can be read from a number called algebraic connectivity, and random regular graphs are the usual benchmark. Theodore Kolokolnikov and Lu Wei ask in 2024 whether semi-regular graphs, where two camps of nodes carry unlike degrees, can do better. For large random semi-regular bipartite graphs, they compute the connectivity and the full spectrum exactly.
For low degrees, from three to seven, their families of semi-regular graphs beat regular graphs with the same size. From degree eight up, regular graphs win again. They also handle non-integer average degree with a sixth-degree polynomial rule, and they build a small-world style network of average degree two and a half with strikingly high connectivity. Open problems close the paper.
Catalog record
| CREATOR | Theodore Kolokolnikov, Lu Wei |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | CC BY 4.0 |
| RIGHTS | CC BY |
| SOURCE | Europe PMC |