New Feature: Laplacian Centrality

[SimonPop]

Hello there,

I am opening this issue to discuss the possibility of implementing a new centrality measure called Laplacian Centrality. I found it very interesting and would have liked to know if it would have its place in the Graphs.jl project.

Description

This metric is presented by (Qi et al. 2012) for having two major benefits over classic centrality measures (e.g. degree, betweenness):

1. It is naturally suited for weighted graphs.
2. It resorts to an intermediate between global (like betweenness centrality) and local (like degree centrality) scope to characterize a vertex.

It is based on the Laplacian Energy of a graph $G$ measured by:

$$E(G) = \sum_{i=1}^{n} \lambda_i^2$$

with $\lambda_i$ the $i^{th}$ eigenvalue of $G$.

The formula for the centrality of a given vertex is given by the drop of energy when removing this vertex from the graph:

$$C_L(v_i, G) = \frac{E_L(G) - E_L(G_i)}{E_L(G)}$$

with $G_i$ the graph obtained from removing vertex $v_i$ from G.

Implementation

Although not providing any pseudo code, (Qi et al. 2012) describes a way to compute this measure efficiently, with a complexity of $O(n\Delta^2)$ with $\Delta$ being the largest degree in the graph at hand.

The formula goes like this:

$$E_L(G) - E_L(G_i) = 2.NW^E_2(v_i) + 2.NW^M_2(v_i) + 4.NW^C_2(v_i)$$

with $NW^E_2(v_i)$ the number of 2-walks ending or starting with $v_i$, $NW^M_2(v_i)$ the number of 2-walks having $v_i$ as middle vertex and $NW^C_2(v_i)$ the number of closed 2-walks including $v_i$.

Each of them can be described as sums and multiplications of edge weights.

NetworkX implementation

A current implementation of that algorithm exists in Python's NetworkX package. However, it recomputes eigenvalues for each subgraph, leading to a simpler but potentially suboptimal algorithm according to (Qi et al. 2012).

Question about unit testing

I seemed to realize that the Graphs.jl library did not test its centrality measures using weighted graphs the likes of SimpleWeightedGraphs. If this algorithm is implemented, would it be suitable to test for these graphs here as well? (the only case of weighted graph test I found was for betweenness_centrality using an external distance matrix).

Would the implementation of such a metric be of interest to the project?

Thanks for reading me!

[etiennedeg]

You can open a pull request if you have an implementation. Improving the tests of the other centrality measures is of course welcome. We don't have tests on Graphs.jl that uses SimpleWeightedGraph (but with the 2.0, it could be very sensible to do so), but you can still add tests that use the distmx argument.