7
$\begingroup$

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?

$\endgroup$
9
+50
$\begingroup$

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.

Sample data.

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.

$\endgroup$
  • $\begingroup$ Very informative answer, thank you Jacob. How would one calculate the centralization once you have the Laplacians for each node in the network? $\endgroup$ – Patrick S. Forscher Dec 19 '13 at 6:09
  • $\begingroup$ L and E are for the entire graph. You calculate the centrality score of a node by forall node in nodes, A = subtract(node, L), Energy{node} = E(A). $\endgroup$ – Jessica Mick Dec 19 '13 at 13:37
  • $\begingroup$ I have another question. On pg. 242 of the article that you linked, the authors state, "Since we only consider undirected networks without loops, $w_{ij} = w_{ji}$ and $w_{ii} = 0$. Is there any reason why one couldn't use the Laplacian centrality for directed networks? $\endgroup$ – Patrick S. Forscher Dec 19 '13 at 20:26
  • $\begingroup$ In directed networks, $w_{ij} \neq w_{ji}$. Further the Laplacian like matrix isn't positive definite, thus that equality assuredly doesn't hold as the eigenvalues can be complex. $\endgroup$ – Jessica Mick Dec 19 '13 at 22:40
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hello @fmassica. CentiServer looks amazing! The problem is that it doesn't work with my R version 3.3.2. Can I ask you, please, how do you read this library? Which version do you use? I tried these steps stackoverflow.com/questions/25721884/… with no success so far :/ $\endgroup$ – Übel Yildmar Aug 3 '17 at 8:14
  • $\begingroup$ @ÜbelYildmar My RStudio Version is 1.0.143. Try to do that: Download the centiserve_1.0.0.tar.gz at cran.r-project.org/web/packages/centiserve/index.html and install with this command: install.packages(path_to_file, repos = NULL, type="source") $\endgroup$ – fmassica Aug 7 '17 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.