A novel measure of edge centrality in social networks

P De Meo, E Ferrara, G Fiumara, and A Ricciardello.
Knowledge-based Systems 30:136-150 (2012).

Useful links: PDF | BibTex | Journal page.

Download WERW-Kpath !

In this paper we presented the K-path edge centrality, a novel measure of edge centrality for social networks based on the paradigm of information diffusion.

In addition, we provide a near-linear time algorithm (called WERW-Kpath) to compute this centrality index and we provide a theoretical proof of the approximation of the error introduced by this algorithm.

The strength of the K-path edge centrality is that it can be adopted to weight unweighted networks, assigning to each edge a weight proportional to its tendency to spread information over the networks.

The rationale behind the K-path edge centrality is rooted in random walks theory: in particular, WERW-Kpath simulates a fixed number of simple (i.e, acyclic) random paths of bounded length up to K (called K-paths) and, at each iteration, increases the weight of each edge composing the given K-path.