Subgraph centrality for weighted graphs

Development
1

Hi,

I’ve been considering the subgraph centrality measure, and the current implementation for igraph has proven very useful.

However, I would also like to evaluate the subgraph centrality of weighted graphs. I don’t think there exists this option for the current implementation, and I haven’t found anything online about it either. I would imagine it’s easy to compute, one just needs to consider the eigenvalues of the weighted adjacency matrix.

Any help would be much appreciated,

2

Can you provide references for this concept (i.e. weighted subgraph centrality)?

3

Hello, thank you for your answer.

You can check the original text: https://arxiv.org/pdf/cond-mat/0504730.pdf (page 7). Weighted subgraph centrality is the exact same concept for weighted graphs (i.e., one considers the eigenvalues of the weighted adjacency matrix).

4

I do not see a weighted generalization on page 7.

If I understand you correctly, you are requesting that igraph include a weighted generalization simply by using the weighted adjacency matrix instead of the binary one. It’s not as simple as that. There are several questions to consider first: Is the metric you obtain this way meaningful? What is the interpretation of large/small weights? How do you handle multigaphs? Etc. It becomes a research level problem, in other words, it becomes very time consuming.

There have been cases when such a naive extension to the weighted case has been done in igraph without thinking it through (a long time ago), and the concept turned out to be completely flawed. See the edge betweenness based community detection function.

There are two reasonable paths to including this metric in igraph:

  • If someone has already investigated the weighted metric you propose, and wrote up the results, we can rely on that paper. Perhaps you can provide a reference?
  • Otherwise, someone must write up a detailed justification for this specific weighted generalization, discuss its interpretation (to provide guidance for future users), touching on all the issues I mentioned above. This is of course a lot of work, and I do not believe anyone on the igraph team can afford to take on such a project at the moment.
5

Hello,

Thanks a lot for your detailed answer. I understand what you mean. I would say that it is reasonable to extend this measure to weighted graphs, since one is counting walks in the graph together with their length, and it is natural and quite standard to weight walk lengths, but I am not aware of a paper that considers the subgraph centrality measure of weighted graphs. I myself I’m working on testing whether this measure would provide good results for a concrete empirical problem, hence my question.

However, I have come across at least one work in which such a generalisation is given thought to: https://diginole.lib.fsu.edu/islandora/object/fsu:360399/datastream/PDF/view, p. 21: “This form of SC can be generalized to weighted networks,where the adjacency matrix is given by the weights”

6

We can’t really go by a simple mention like this.

To illustrate some of the difficulties:

Consider a simple unweighted graph, and compute the subgraph centrality. Now assign the same weight a to each edge, and compute it again according to your proposal (i.e. simply using the weighted adjacency matrix). Here are some questions:

  • Will the values change? How do you interpret this change?
  • Will the values change relative to each other (e.g. the ratio in centrality between the first and second vertex)? How do you interpret this change?

I am not sure what you mean by this.

W^k no longer counts walks, unless the weights are integers that we interpret as edge multiplicities.

7

Hello,

I wrote to Ernesto Estrada, who initially introduced the measure, and he very kindly referred me to this work: https://royalsocietypublishing.org/doi/epdf/10.1098/rsif.2008.0484, in which a weighted subgraph centrality measure is proposed (note that SC is the same as self-communicability). They provide a normalisation step which evens out the difficulties you point out, I think (after this step, SC values are preserved w.r.t those of the unweighted graph when choosing the same weight).

I meant that when computing powers of the weighted adjacency matrix, one is weighting the length of the walk according to the walk edge weights, it’s the same idea that appears in the reference I gave.

8

As I understand, this is not the case.

The “subgraph centrality” was defined as

\operatorname{diag}(\exp(A))

This measure is defined as

\operatorname{diag}(\exp(D^{-1/2}A\,D^{-1/2}))

where D has the degrees on the diagonal. They use a symmetric normalization of the weight matrix.

In the end, there are many possible definitions of similar measures, and they are all relatively easy to compute with a system that has good support for linear algebra. Personally, I use Mathematica, but in R you could do something like diag(expm(as_adjacency_matrix(g))). It’s not the most efficient, but very simple to write.

I would not be in favour of adding this measure to igraph, in part because it’s just one of the many different possibilities (and people will always come up with different variations), and in part because it’s so easy to compute without a dedicated function.

An interesting observation about the “weighted self-communicability” measure you linked is that we could have used the D^{-1} A normalization as well to obtain the very same result (the diagonal of the matrix exponential is the same). This matrix has better interpretability as it relates to random walks. So we can think of it not as being based not on a plain enumeration of closed walks of given lengths, but assigning different weights to different closed walks according to their probability during a random walk process.

9

Yes, that was what I meant when I said “after this [normalisation] step”.

I see, thanks for the discussion and your last comment about interpretability.