2
$\begingroup$

The "average degree" of a graph $G = (V,E)$ is $$\frac{2|E|}{|V|}$$ or simply $2l/k$, i.e. twice the number of edges divided by the number of vertices.

With $H$ a graph, if we simply write $d(H)=2l/k$, we can then look at the maximum of $d$ of over subgraphs of H, i.e. with $m(H)$ the maximum average degree of a graph $H$, $$m(H)=\max\{d(F):F \subset H\}$$

A graph $H$ is balanced if the graph itself has an average degree equal or larger than the average degrees of all its subgraphs, i.e. $m(H)=d(H)$.

It is strictly balanced when the average degree of $H$ is strictly larger than all of its subgraphs. See Chapter 4 of B. Bollobás "Random Graphs" 2001.

Trees, cycles and complete graphs are always strictly balanced. See the examples of Bollobás below.

Is there a quick way to test whether a graph is strictly balanced? I am currently doing this by taking subsets of all its vertices, forming the induced subgraphs $F_1,F_2,\dots$ of each via Subgraph, then finding $d(F_1),d(F_2),\dots$ and comparing it to $m(H)$ until it is clear when the graph itself has strictly largest average degree, using 

AvDegree[x_] := N[2*Length[EdgeList[x]]/Length[VertexList[x]]]

but for a large dataset, this takes too long.

enter image description here

Improve this question
$\endgroup$
5
  • $\begingroup$ Simple examples of each type of graph would be helpful. $\endgroup$ – Carl Woll Jan 5 '18 at 16:46
  • $\begingroup$ I have added those given by Bollobás. $\endgroup$ – apkg Jan 5 '18 at 16:58
  • $\begingroup$ What sizes of graphs are you interested in? $\endgroup$ – Carl Woll Jan 5 '18 at 18:36
  • $\begingroup$ Quite small, say no bigger than 100 nodes $\endgroup$ – apkg Jan 6 '18 at 17:45
  • $\begingroup$ But this can get costly if I then repeat 100,000 times $\endgroup$ – apkg Jan 6 '18 at 17:46
1
$\begingroup$

Here is one slow possibility. You can cast the problem as a linear programming problem, with a vector consisting of indicator variables for the edges and vertices. Let the vector be: $(e_1, .., e_m, v_1, .., v_n)$ where there are $m = |E_G|$ edges and $n = |V_G|$ vertices in the graph. Then the graph has $d_G = 2 |E_G| / |V_G| $. Now, a subgraph $H$ will have $d_H = 2 |E_H| / |V_H|$. Then, we have:

$$|E_G| |V_H| - |E_H| |V_G| = d_G |V_G| |V_H|/2 -d_H |V_G| |V_H|/2 = (|V_G| |V_H|/2) ( d_G - d_H)$$

The sign of the minimum over all subgraphs $H$ of $|E_G| |V_H| - |E_H| |V_G|$ will determine whether the graph is unbalanced, balanced or strictly balanced.

The LinearProgramming constraints come from each vertex in the graph: if the vertex is not in the subgraph, then the associated edges must be absent from the subgraph. Here is the function:

balanceQ[g_] := Module[
    {e=EdgeList[g], ec=EdgeCount[g], v=VertexList[g], vc=VertexCount[g], res},

    res = Quiet[
        LinearProgramming[
            Join[
                -vc Table[1, {ec}],
                ec Table[1, {vc}]
            ],
            Join[
                Table[
                    With[{b = Boole[Not@*FreeQ[v[[i]]] /@ e]},
                        Join[b, PadRight[{-Total[b]},  vc, 0, {i-1}]]
                    ],
                    {i, vc}
                ],
                {
                    Join[Table[0, {ec}], Table[1, {vc}]],
                    Join[Table[0, {ec}], Table[1, {vc}]]
                }
            ],
            Join[
                Table[{0, -1}, {vc}],
                {
                    {1, 1}, (* at least one vertex *)
                    {vc-1,-1} (* not all vertices *)
                }
            ],
            Table[{0, 1}, {vc+ec}],
            Integers
        ],
        LinearProgramming::lpip
    ];
    Switch[Sign[-vc Total[res[[;;ec]]] + ec Total[res[[ec+1;;]]]],
        -1, "Unbalanced",
        0, "Balanced",
        1, "Strictly balanced"
    ]
]

As an example, consider graphs from GraphData:

g = GraphData /@ GraphData[30];

SortBy[AbsoluteTiming[balanceQ[#]]& /@ g, First]

{{0.001414, "Balanced"}, {0.002054, "Unbalanced"}, {0.002168, "Unbalanced"}, {0.002208, "Balanced"}, {0.024167, "Unbalanced"}, {0.043445, "Unbalanced"}, {0.049372, "Strictly balanced"}, {0.069279, "Balanced"}, {0.083165, "Strictly balanced"}, {0.086195, "Strictly balanced"}, {0.094856, "Strictly balanced"}, {0.100238, "Balanced"}, {0.103429, "Strictly balanced"}, {0.110622, "Strictly balanced"}, {0.123556, "Strictly balanced"}, {0.133809, "Strictly balanced"}, {0.138439, "Strictly balanced"}, {0.157034, "Strictly balanced"}, {0.195019, "Strictly balanced"}, {0.226968, "Strictly balanced"}, {0.237197, "Strictly balanced"}, {0.267112, "Strictly balanced"}, {0.267291, "Strictly balanced"}, {0.322829, "Strictly balanced"}, {0.327068, "Strictly balanced"}, {0.333683, "Strictly balanced"}, {0.344322, "Strictly balanced"}, {0.352541, "Strictly balanced"}, {0.373047, "Strictly balanced"}, {0.384115, "Strictly balanced"}, {0.411243, "Strictly balanced"}, {0.423324, "Strictly balanced"}, {0.433958, "Strictly balanced"}, {0.443956, "Strictly balanced"}, {0.448159, "Strictly balanced"}, {0.460425, "Strictly balanced"}, {0.47054, "Strictly balanced"}, {0.479184, "Strictly balanced"}, {0.485696, "Strictly balanced"}, {0.502723, "Strictly balanced"}, {0.51482, "Strictly balanced"}, {0.528539, "Strictly balanced"}, {0.536904, "Strictly balanced"}, {0.538585, "Strictly balanced"}, {0.546364, "Strictly balanced"}, {0.55003, "Strictly balanced"}, {0.614187, "Balanced"}, {0.709653, "Strictly balanced"}, {0.710389, "Unbalanced"}, {0.742609, "Strictly balanced"}, {0.781095, "Strictly balanced"}, {0.885017, "Strictly balanced"}, {0.925772, "Strictly balanced"}, {1.1346, "Strictly balanced"}, {1.21853, "Strictly balanced"}, {1.30096, "Balanced"}, {1.32248, "Strictly balanced"}, {1.3259, "Strictly balanced"}, {1.33169, "Strictly balanced"}, {1.49999, "Strictly balanced"}, {1.77298, "Strictly balanced"}, {2.14196, "Strictly balanced"}, {2.19037, "Strictly balanced"}, {2.26871, "Strictly balanced"}, {2.33642, "Strictly balanced"}, {2.49905, "Strictly balanced"}, {2.58194, "Strictly balanced"}, {2.58368, "Strictly balanced"}, {2.70069, "Strictly balanced"}, {2.86718, "Strictly balanced"}, {2.86911, "Strictly balanced"}, {2.87815, "Strictly balanced"}, {2.90138, "Strictly balanced"}, {3.24567, "Strictly balanced"}, {3.4512, "Strictly balanced"}, {4.92757, "Strictly balanced"}, {4.95015, "Strictly balanced"}, {4.9556, "Strictly balanced"}, {5.0526, "Strictly balanced"}, {5.05777, "Strictly balanced"}, {5.25303, "Strictly balanced"}, {5.51572, "Strictly balanced"}, {5.93311, "Strictly balanced"}, {7.65476, "Strictly balanced"}, {8.4197, "Strictly balanced"}, {9.07264, "Strictly balanced"}, {9.89535, "Strictly balanced"}, {10.352, "Strictly balanced"}, {11.3917, "Strictly balanced"}, {151.473, "Strictly balanced"}, {215.75, "Strictly balanced"}}

Even for graphs with 30 vertices, the timing for balanceQ ranges from .001 to 215, so it is very slow, but should be much faster than checking $|E_H|/|V_H|$ for all 2^30 subgraphs.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you, I’ll run this and give you some feedback. $\endgroup$ – apkg Jan 7 '18 at 14:21
  • $\begingroup$ Yes this is ideal, it is able to list which graphs are balanced, strictly balanced, or unbalanced very quickly. $\endgroup$ – apkg Nov 6 '19 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.