It Is Better to Be Semi-Regular When You Have a Low Degree Authors: Theodore Kolokolnikov, Lu Wei Published: 2024 ABSTRACT AbstractWe study the algebraic connectivity for several classes of random semi-regular graphs. For large random semi-regular bipartite graphs, we explicitly compute both their algebraic connectivity as well as the full spectrum distribution. For an integer d∈3,7, we find families of random semi-regular graphs that have higher algebraic connectivity than random d-regular graphs with the same number of vertices and edges. On the other hand, we show that regular graphs beat semi-regular graphs when d≥8. More generally, we study random semi-regular graphs whose average degree is d, not necessarily an integer. This provides a natural generalization of a d-regular graph in the case of a non-integer d. We characterize their algebraic connectivity in terms of a root of a certain sixth-degree polynomial. Finally, we construct a small-world-type network of an average degree of 2.5 with relatively high algebraic connectivity. We also propose some related open problems and conjectures.Keywords: algebraic connectivity, spectral gap, diffusion on graphs, computational graph theory, extremal graph theory 1. Introduction Algebraic connectivity (AC; also called the spectral gap) of a graph is a fundamental property that measures how fast information diffuses throughout the graph [1,2]. It corresponds to the second smallest eigenvalue of the graph Laplacian matrix (the smallest eigenvalue is always zero). In many applications, it is desirable to maximize the algebraic connectivity (i.e., speed of diffusion) subject to certain constraints; this and related problems have a long history [3,4,5,6,7,8,9]. For example, in communications, the “cost” of a network increases with the number of links. It is therefore desirable to have as few edges as possible, while at the same time maximizing the algebraic connectivity. This leads to a natural question: For a fixed average degree d, what is the graph that maximizes algebraic connectivity as the number of vertices n→∞? Numerous papers address various aspects of this question, see e.g., [6,7,8,9]. This is one of those situations where the best answer is elusive [10], but a decent answer can be found relatively quickly [3,4]. Graphs with high algebraic connectivity are related to expander graphs, and are important in many applications [11,12]. In this paper, we study the algebraic connectivity of sparse random graphs in the case when the number of edges m scales linearly with the number of vertices n, i.e., m=O(n). In other words, we fix the average degree d=2m/n=O(1) while letting n→∞. It is well known that a random Erdos–Renyi graph (where m edges are taken at random) needs O(nlogn) edges to be fully connected [13,14], and as such, they are poor candidates for maximizing algebraic connectivity in this sparse regime (since the AC of a disconnected graph is zero). A good candidate is a d-regular graph for which every vertex has a degree d. It is well known that random regular d-graphs have an algebraic connectivity that is asymptotic to μ∼d−2d−1 as n→∞ with fixed d [15,16,17,18,19]. For integer d≥3, this quantity is strictly positive, which assures that these graphs have good expander properties [20,21]. A natural question is whether one can perform better than a regular graph, but without “too much work” (in, say, O(n) time). In this paper, we give an affirmative answer when d≤7: we introduce a class of semi-regular random graphs (whose vertices have a degree of either d1 or d2≠d1), which is as easy to construct as random d-regular graphs, but which has better AC. Another question is whether “expander-type” graphs (which we define to be graphs with AC bounded away from 0 as n→∞) are possible when the average degree d is less than 3, with n→∞. For 2d1. Label the components of the eigenvector x1…xn1 and y1…yn2, corresponding to vertices of degree d1 and d2, respectively. A zero eigenvalue satisfies ∑xj∈nbr(yk)xj=0, k=1…n2 and ∑yj∈nbr(xk)yj=0, k=1…n1. Look for solutions of the form where yj=0, j=1…n2. This corresponds to solving n2 linear equations ∑xj∈nbr(yk)xj=0, for the n1 unknown x1…xn1. This is an under-determined system, since n2d1, so that, indeed, ∫−∞∞ρ=1. This completes the derivation of the spectral density (3). Finally, another derivation of the delta weight, as pointed out by James Mingo, is to use Proposition 3.8 in [24]. It says that if 1xϕ1x has a singularity at x=a, then the associated measure ρ(x) has a delta mass at x=a, whose weight is given by limx→ax−a1xϕ1x. Here, a=0 and the mass weight is then given by limx→0ϕ1x=d1d2d1+d2r−2r+2d1d2=d2−d1d1+d2 in agreement with direct computation. ▪ Derivation of AC formula for RSRB (5). Next, we derive the formula for algebraic connectivity (5). For d-regular graphs, the Laplacian graph is given by dI−A, where I is the identity and A is the adjacency matrix. This allows us to characterize the AC in terms of the second-largest eigenvalue λ of A: μ=d−λ. Of course, this is not true if the graph is not regular. The trick is to regularize the graph by adding enough self-loops to vertices until all vertices have the same degree. Each self-loop counts as a single additional edge (i.e., adding a loop to vertex j corresponds to adding “1” to the j-th diagonal entry of the associated adjacency matrix) and crucially, adding self-loops does not change the Laplacian of the graph. For a d1,d2 semi-regular graph, assume that d1d−2d−1 case) while the converse is true when d≥15. While complete bipartite graphs have a relatively high AC when d<15, they are also fragile, in the sense that removing any single edge causes the AC to decrease by one. Random graphs are more robust with respect to edge deletions as they seem to have some redundancy built-in. Consider the limit of large d2 for the RSRB model. From (2) and (5), one obtains that d∼2d1 and μ∼d2−1 as d2→∞. This is one less than the AC of the complete bipartite graph Kd/2,n−d/2 (which also has the average degree d as n→∞). More generally, let μd1,d2 be as in (5) and let μd=d−2d−1, where d=2d1d2/(d1+d2) is the average degree. It can be shown that μd1,d2<μd for any d1,d2 when d≥10. This discussion suggests the following question. Find a family of random graphs which has a higher algebraic connectivity than d-regular random graphs when the average degree d≥10. Explore if a more complex degree distribution (e.g., tri-regular) can be better than semi-regular for, say, d=3. There are several notions of graph connectivity, with AC being just one. Another notion is using the average of reliability polynomial [26,27] to compute the effect of edge deletions on graph connectivity. While the full reliability polynomial requires exponential time to compute, we performed the following simple experiment to quickly measure graph robustness. Start with a random 6-regular graph on 500 vertices (i.e., containing 1500 edges). Then, delete edges at random one by one until the graph becomes disconnected. Over 100 simulations, it took on average 460 edge deletions until the graph became disconnected (and in every instance, disconnectivity first occurred when a single vertex lost all of its edges). We then repeated this experiment with d1,d2=4,12 RSRB graph with 500 vertices (which also contains 1500 edges, but has higher AC than a 6-regular random graph). It took on average 325 edge deletions until the disconnection was achieved. These preliminary experiments indicate that d-regular graphs are more reliable with respect to edge deletions than semi-regular bipartite graphs, even though the latter might have a higher AC. We state this as a conjecture. For a given average degree d, the most reliable graph is a d-regular graph. Generally speaking, cubic graphs of high girth are good candidates for high-AC graphs [7]. Since RSRB can have a higher AC, they are also natural candidates for searching high-girth graphs. We pose this as a challenge. For a fixed average degree d and fixed number of vertices n, find graphs (not necessarily d-regular) with the highest possible girth. A d-regular graph with the smallest possible n for a given girth g is called a cage. The literature for looking for high-girth graphs is extensive; see [28,29] for an overview. There are powerful methods to perform computer searches for high-girth d-regular graphs [30,31]. As an example, consider 2,6 RSRB graphs, whose average degree is d=3. Do 2,6 semi-regular graphs give better cages than cubic graphs with the same number of vertices? The answer is, it depends. Note that that 2,6 graphs can be obtained from 6-regular graphs by inserting a vertex in the middle of each edge; conversely, any 2,6 graph yields a 6-regular graph by vertex contraction: just delete all 2-degree vertices. According to [28,32], a 6-regular 5-cage graph has 40 vertices. By vertex insertion, this yields a girth 10 2,6 semi-regular graph with 80 vertices. On the other hand, there are three cubic graphs having girth 10 and only 70 vertices [28]. So, the cubic is better for girth 10. Similarly, a 6-regular cage of girth 6 has 62 vertices [28], which induces a (2,6) graph of girth 12 and 124 vertices. On the other hand, a cubic graph of girth 12 has at least 126 vertices [28,33]. So, a (2,6) semi-regular graph is superior for girth 12. The techniques in this paper are rather general, and can be used to derive algebraic connectivity for many other random graph families. As an example, consider the “small-world”-type graph illustrated in Figure 1c. Start with a cycle of n vertices, then connect all odd-numbered vertices to each other at random. See Appendix A for the Matlab code that generates such a graph. The resulting graph has an average degree of 2.5. To compute its AC, as in the derivation of (5), we add a self-loop to even-numbered vertices so that each vertex has a degree of 3. We leave it as an exercise to the reader that the average walk-counting sequence ϕs has the generating function that satisfies Looking at the radius of convergence of the generating functions as before, we find that in the limit n→∞, its AC is asymptotic to the smallest root of the polynomial explicitly given by μ=0.0521926. This is validated using Monte Carlo simulations; the average AC of 1000 of such random graphs with n=1000 vertices is 0.0557 (std = 0.0029), i.e., a difference of about 7%. This is significantly higher than an RSR graph with (p,d1,d2)=0.5,2,3, which also has an average degree of 2.5, but whose AC is μ∼0.044241. Appendix A. Matlab and Maple Code RSRB model (Figure 1a): d1=2; d2=3; n1=30; n2=20; bag1=mod([0:n1*d1-1], n1)+1; bag2=mod([0:n2*d2-1], n2)+1+n1; bag2=bag2(randperm(numel(bag2))); G=graph(bag1, bag2); plot(G); RSR model (Figure 1b): p=0.4; d1=2; d2=3; n=50; n1=(1-p)*n; n2=p*n; v1=mod([0:n1*d1-1], n1)+1; v2=mod([0:n2*d2-1], n2)+1+n1; bag=[v1, v2]; bag=bag(randperm(numel(bag))); G=graph(bag(1:end/2), bag(end/2+1:end)); plot(G); Small-world-like model (Figure 1c): n=52; v1=[1:n]; v2=[2:n,1]; bag=[1:2:n]; bag=bag(randperm(numel(bag))); v1=[v1,bag(1:end/2)]; v2=[v2,bag(end/2+1:end)]; G=graph(v1,v2); t=(1:n)/n*2*pi; plot(G, ’XData’, cos(t), ’YData’, sin(t)); Maple code to compute AC of RSR graphs: Institutional Review Board Statement Not applicable. Data Availability Statement Data is contained within the article. Conflicts of Interest The author declares no conflicts of interest. Funding Statement T.K. is funded by NSERC Discovery grant, Canada. Footnotes Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content. References Associated Data Data Availability Statement Data is contained within the article.