Hubbiness of a graph

Question

Is there any statistic that can tell how "hubby" is a graph?

By this I mean a number that is small when a graph has no hubs, that is, when all nodes are more or less equal degree-wise, and big when there are hubs, nodes that concentrate most of the connectivity.

I expect it to be zero (or minimal) for a fully connected graph and 1 (or maximal) for a "star shaped" graph with one node with degree N-1 and N-1 nodes with degree 1.

I was thinking to use some measure of the dispersion of the degree distribution (degree entropy, degree variance, ...). Or maybe to define a hub as a node that, when cut out, turns a connected graph in a non-connected graph and define its "hubbiness" as the number of connected components after I cut it from the graph (and define the hubbiness of the graph as the average hubbiness of the nodes).

But I'm not a specialist in this field, so I don't know if there is an already tried and established measure in the specific community, easy to estimate.

EDIT:

my graphs are usually small (in the worst case 100 graphs with 100 nodes each, but typically 20 graphs with 20 nodes each), so I'm slightly (not absolutely) more interested in theoretical soundness than efficiency.

Answer 1

Here are some concepts that might be helpful to you:

1. A vertex $v$ of a connected graph $G$ is an articulation point if the removal of $v$ from $G$ causes $G$ to be disconnected. My interpretation is that an articulation point corresponds to a "hub". This may or may not match your intuition. On the one hand, the center vertex in a star is an articulation point, but then so is any interior point in a path.

2. A connected graph $G$ is biconnected if it does not contain any articulation points (i.e.: the removal of any single vertex from $G$ does not disconnect $G$). By convention, the graph consisting of just two vertices and one edge is considered biconnected.

3. A biconnected component of a graph $G$ is a maximal, biconnected subgraph.

4. Finally, we can define the block tree $BT(G)$ of a connected graph $G$ as follows: The vertices of $BT(G)$ are the biconnected components of $G$ and an edge $(u,v)$ exists in $BT(G)$ iff the biconnected components corresponding to $u$ and $v$ share a vertex (in $G$). This Wikipedia article has a nice illustration of this concept and a description of an algorithm for constructing the block tree.

I would suggest that the degree of "hubbiness" of a graph $G$ is related to the size of $BT(G)$. Let $G$ be a graph with $n$ vertices. Then:

• If $G$ is biconnected, then $|BT(G)| = 1$
• If $G$ is a star, then $|BT(G)| = n$
• If $G$ is a path, then $|BT(G)| = n-2$
• In general, if $G$ is a tree, then$|BT(G)|$ equals the number of interior vertices

Answer 2

Look at http://en.wikipedia.org/wiki/Scale-free_network. These are graphs whose degree distributions obey a power law, and they are exactly what you are talking about. There is a huge literature on power law graphs, because they tend to show up in examples (e.g., the internet). You can probably approximate a graph's distribution by a power law and use the exponent to define your metric.

Edit: Another relevant topic is centrality (http://en.wikipedia.org/wiki/Centrality), which is a measure of vertex importance. There are a lot of these, one of which is Google's PageRank. If you look at the centrality distribution, I think your idea of hubbiness is basically that relatively few vertices have high centrality, and most don't.

Answer 3

I'm no graph theorist, but if you're only interested in how many nodes have different degrees then what you want is surely just a statistical property of the frequency distribution. Your "hubbiness" property sounds like it corresponds to positive skewness, or perhaps to the ratio (standard deviation / mean) being large (edit: this ratio is apparently known as the coefficient of variation).