  The problem of assigning centrality values to nodes and edges in graphs has
been widely investigated during last years. Recently, a novel measure of node
centrality has been proposed, called k-path centrality index, which is based on
the propagation of messages inside a network along paths consisting of at most
k edges. On the other hand, the importance of computing the centrality of edges
has been put into evidence since 1970's by Anthonisse and, subsequently by
Girvan and Newman. In this work we propose the generalization of the concept of
k-path centrality by defining the k-path edge centrality, a measure of
centrality introduced to compute the importance of edges. We provide an
efficient algorithm, running in O(k m), being m the number of edges in the
graph. Thus, our technique is feasible for large scale network analysis.
Finally, the performance of our algorithm is analyzed, discussing the results
obtained against large online social network datasets.
