This is the third post of a series on the concept of “network centrality” with
applications in R and the package netrankr. The last part introduced the concept of
neighborhood-inclusion and its implications for centrality. In this post, we
extend the concept to a broader class of dominance relations by deconstructing indices
into a series of building blocks and introduce new ways of evaluating centrality.
library(igraph)
library(ggraph)
library(tidyverse)
library(netrankr)
Introduction
Neighborhood-inclusion seems to underlie many different centrality indices and as such
serves (or better: could serve) as a defining property of a centrality index. That is:
An index is a measure of centrality if and only if it preserves the partial ranking induced by neighborhood-inclusion
While this gives as a theoretical basis for centrality, it comes with a bit of problem.
Namely, that we do not expect many comparable pairs in (large) real-world networks.
Take the third example network from the first post.
g3 % aggregate_positions(type='invsum')
#betweenness
g %__% indirect_relations(type='depend_sp') %__% aggregate_positions(type='sum')
#eigenvector
g %__% indirect_relations(type='walks',FUN=walks_limit_prop) %__% aggregate_positions(type='sum')
#subgraph g %__% indirect_relations(type='walks',FUN=walks_exp) %__% aggregate_positions(type='self')
(Consult the help for indirect_relations() to see all options)
Note that we make use of the %__% operator. This should appeal to the recipe
idea from above: network %__% indirect_relation %__% aggregation. The package also
includes a handy RStudio addin, which can be used to build the pipelines more easily.
Defining indices in this way is certainly more cumbersome than using, say, betweennes(g).
However, it allows us to intervene at any step and do something else.
Extended Dominance Relations
To illustrate the “something else”, we look at our small example network again.
g1 % aggregate_positions(type=&quot;invsum&quot;)
#harmonic closeness
c_HC % indirect_relations(type=&quot;dist_sp&quot;,FUN=dist_inv) %__% aggregate_positions(type=&quot;sum&quot;)
#residual-type closeness
c_RC % indirect_relations(type=&quot;dist_sp&quot;,FUN=dist_2pow) %__% aggregate_positions(type=&quot;sum&quot;)
Any of the above indices starts with the derivation of distances, but then proceeds with
a different form of aggregation:
\[
c_C(i)=\frac{1}{\sum dist(i,j)},\quad c_{HC}(i)=\sum\frac{1}{dist(i,j)}, \quad c_{RC}(i)=\sum 2^{-dist(i,j)}
\]
Possibilities are virtually endless for aggregating distances into an index.
From the previous part, we know that any of these indices preserve neighborhood-inclusion.
Once we have settled for a relation, as in this case, we can extend the partial ranking
using the following considerations: If a \(dist(i,k)\) is larger than \(dist(j,k)\) for all
nodes \(k\), then no matter how we aggregate the relations (as long as it is monotonic),
\(i\) will always be less central then \(j\). With a bit more formalism:
\[
dist(i,k) \geq dist(j,k) \text{ for all } k \implies c_x(i)\leq c_x(j)
\]
where \(c_x\) is an arbitrary centrality index based on distances. This actually defines
a new dominance relation among nodes. In fact, we can go a step further. It does
not really matter in which order we aggregate the distances, the result will always be the same.
Hence, we can permute all relations of a single node without affecting the result.
A convenient choice of permutation is simply to reorder all relations in descending
order. Afterwards, we can compute the dominance relations as above. (More formal details on these dominance relations can be found in this article.)
We can compute this new dominance relation using the function positional_dominance().
The benefit parameter is set to FALSE since large distances are not beneficial for
a node to have. Setting map=TRUE invokes the above mentioned reordering. For comparison,
we also compute neighborhood-inclusion again.
P % positional_dominance(benefit=FALSE,map=TRUE)
c(&quot;neighborhood-inclusion&quot;=comparable_pairs(P),&quot;distance dominance&quot;=comparable_pairs(D))
## neighborhood-inclusion distance dominance ## 0.1636364 0.8727273
By fixing our relation of interest to distances and allowing reordering of relations, we
went from only 16% of comparable pairs to 87%! Hence, no matter what index based on distance we use,
results will always be very similar. As a sanity check, we can verify that all distance based indices from above preserve the dominance relations.
c(&quot;classic&quot;=is_preserved(D,c_C),&quot;harmonic&quot;=is_preserved(D,c_HC),&quot;residual&quot;=is_preserved(D,c_RC))
## classic harmonic residual ## TRUE TRUE TRUE
Partial Centrality
By now, we should have understood that there are various kinds of partial rankings in networks,
which form the basis of centrality. Indices extend these partial rankings into one possible ranking,
but, as we will see later, there might be hundreds of thousands of possible rankings. And hence, hundreds of
thousands of indices that produce these rankings. Instead of inventing hundreds of thousands of
indices, why not just study the partial rankings? Or why not be extremely bold, and try to
analyse all possible rankings at once?
In this section, we consider the former question, by introducing rank intervals. A rank interval
of a node is the set of ranks a node can have in any ranking that extends a given partial ranking.
Let us consider two extreme cases. A node that is neither dominated nor dominates any other node can potentially
have any rank. So its rank interval is \([1,n]\). (We use the convention, that \(n\) is the top rank and \(1\) the lowest possible rank).
On the other hand, if a node dominates all other nodes, it can only be ranked on the top. So its rank interval is just a point.
netrankr includes the function rank_intervals() which returns the rank intervals for all nodes in the network.
A visual representation of the intervals can be obtained with the plot_rank_intervals() function, as done below for the
first example network and neighborhood-inclusion as partial ranking input. We also included an optional data.frame
containing centrality scores of five indices.
cent_scores