1
$\begingroup$

Among the many centrality measures that I have heard of, I miss the following (but maybe I'm just blind).

Consider a graph $G$ with $k$ connected components $G_i$ of size $|G_i|$. The number of node pairs in $G$ that are not connected by any path in $G$ is

$$D(G) = \frac{1}{2}\sum_{i=1}^{k} |G_i|\cdot|G\setminus G_i|$$

For connected graphs $D(G)$ is $0$, for empty graphs $D(G)$ is $\frac{1}{2}|G|(|G|-1)$. Let

$$d(G) = \frac{2}{|G|(|G|-1)} D(G)$$

be the proportion of node pairs that are not connected in $G$, so the empty graphs have $d(G)=1$.

Now consider $G$ as the vertex-deleted subgraph of another graph $G\cup\{\nu\}$ with $\nu \not\in G$, where $\nu$ is connected to all nodes in $G$. In this case $G\cup\{\nu\}$ is obviously connected, and $\nu$ connects all pairs of nodes that have been disconnected in $G$. So it's natural to assign the number $d(G)$ to the node $\nu$ and call it for example its connecting centrality in $G\cup\{\nu\}$ (just to give it a name).

Connecting centrality in this sense is only defined for nodes that are connected with all other nodes in a graph. But graphs with nodes that are connected to all other nodes are very rare, and so are graphs that become disconnected by removing one single node. so this concept might seem pointless. But every graph $G$ contains as many such graphs as there are nodes: the ego-networks $N(\nu) \cup\{\nu\} $, i.e. the induced subgraphs consisting of the node $\nu$ and all of its neighbours $N(\nu)$.

From a local perspective these ego-networks are interesting objects in themselves, even though they don't tell so much about the global properties of the surrounding graph. Ego-networks have two important properties: They contain a node that is connected to all other nodes, and the vertex-deleted subgraph $N(\nu)$ is disconnected more often than not, at least in sparse graphs. So it is quite natural to assign in any graph $G$ to any node $\nu$ its local connecting centrality $d(N(\nu))$ which now may be called neighbourhood centrality.

I have the following questions:

  1. Under which name is this centrality measure already investigated?

  2. How do neighbourhood and betweenness centrality (based on the number of shortest paths that go through a node $\nu$) correlate for some typical graphs? (Think of a scatterplot.)

  3. What might this correlation tell about the graph?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ This seems to convey essentially the same information (but not saying it is the same thing) as a flavor of efficiency (en.wikipedia.org/wiki/Efficiency_(network_science)) with respect to a modified version of the discrete metric that takes the value $\infty$ when a target is unreachable from a source. $\endgroup$
    – Steve Huntsman
    Commented May 6, 2021 at 19:16
  • 1
    $\begingroup$ @SteveHuntsman: Thanks for the hint. The article also considers ego-deleted ego-networks $N(\nu)$, only under the name $G_i$. $\endgroup$
    – Hans-Peter Stricker
    Commented May 6, 2021 at 19:45
  • $\begingroup$ I would contest the statement that the ego-nets tend to be disconnected in general. In a graph with high local clustering coefficient, I would expect then to be connected more frequently than not. $\endgroup$
    – Leo
    Commented May 7, 2021 at 1:13
  • $\begingroup$ I think Leo has a point, and I would go further: ego-networks in a given network are very different from each other. Think of their size, which is nothing but vertex degrees: they are very heterogeneous in many (most?) practical cases; in addition, many degrees are extremely small. Although interesting, comparing the properties of graphs with such differences and such small sizes seems difficult. $\endgroup$
    – Matthieu Latapy
    Commented May 7, 2021 at 8:57
  • $\begingroup$ @MatthieuLatapy: I didn't suggest to compare ego-networks (which may differ a lot) but large graphs (of a given class, e.g. $G(n,m)$). For each such graph the distribution of neighbourhood centrality can be determined (which will reveal the diversity and heterogeneity of nodes and their ego-nets) and will be roughly the same in large classes (of large graphs). $\endgroup$
    – Hans-Peter Stricker
    Commented May 7, 2021 at 11:51

0

Reset to default

You must log in to answer this question.