Centralization measures in weighted graphs

Question

I'm using the igraph package in R to analyze network data. I'm currently trying to calculate some centrality measures for the vertices of my graph and the corresponding centralization scores. My network is both directed and weighted.

require(igraph)
set.seed(12152)

m <- expand.grid(from = 1:4, to = 1:4)
m <- m[m$from != m$to, ]
m$weight <- sample(1:7, 12, replace = T)

g <- graph.data.frame(m)

I have no trouble using the closeness function to obtain the closeness centrality for each vertex:

closeness(g, mode = "in")
closeness(g, mode = "out")
closeness(g, mode = "total")

However, it appears that the centralization.closeness function from igraph does not work for directed graphs. igraph does include a way to calculate a custom centralization from the individual centrality scores in a graph (the centralize.scores function), but that function requires the user to specify the theoretical maximum of the centrality measure, and it's not obvious to me what that would be in this weighted example (I believe the built-in centralization.closeness.tmax function in igraph assumes an unweighted graph).

Does anyone know how to calculate a centralization score in a weighted graph? Is there a good way to accomplish this in R with igraph or some other package?

Answer 1

All centrality measures are dependent on the shape of your data. Laplacian centrality is a convincing measure of centrality for weighted graphs.

Define a matrix to store our weights.

$ W_{ij} = \left\{ \begin{array}{lr} w_{ij} & : i \neq j\\ 0 & : i = j \end{array} \right. $

Define a matrix, where the diagonal is the sum of the weights associated with a node.

$ X_{ij} = \left\{ \begin{array}{lr} 0 & : i \neq j\\ \sum\limits_{i=0}^n W_{i}& : i = j \end{array} \right. $

The Laplacian is then defined by

$L = X - W$

We can define a property of the graph, Laplacian energy.

$E = \sum\limits_{i=0}^n\lambda_i^2$

Where $\lambda$s are the eigenvalues associated with the Laplacian.

Rather than eigensolving our matrices, we can equivalently solve.

$E = \sum\limits_{i=0}^n x_i^2 + 2\sum\limits_{i<j}w_{ij}^2$

To define the importance of a particular node in a graph, we remove that node and calculate the energy.

Consider the following data, generated from an RBF kernel of 1000 multivariate normal observations centered at the origin with a standard deviation of unity. The indices are the same for both figures. The data was presorted according to the distance of each observation $\in \mathbb R^n$ from the origin.

The importance of the Laplacian is beyond the scope of this answer. Laplacians are central to many piercing theorems in spectral graph theory and many practical results in the literature of manifold learning and clustering. I'd highly recommend reading up on the subject if you think you'll be dealing with weighted graphs in the near future.

Answer 2

In order to answer this:

Does anyone know how to calculate a centralization score in a weighted graph? Is there a good way to accomplish this in R with igraph or some other package?

I think the best way to do this is using the library centiserve. This library contains a lot of centrality methods and one of them is Laplacian Centrality. And the best thing it works with igraph.