A Novel Measure of Edge Centrality in Social Networks
arXiv:1303.1747 · doi:10.1016/j.knosys.2012.01.007
Abstract
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.
28 pages, 5 figures
References in corpus (2)
Cited by in corpus (11)
- Enhancing community detection using a network weighting strategy
- A Network Science perspective of Graph Convolutional Networks: A survey
- Correlations among Game of Thieves and other centrality measures in complex networks
- Correlation analysis of node and edge centrality measures in artificial complex networks
- Visualizing criminal networks reconstructed from mobile phone records
- Disentangling the Spectral Properties of the Hodge Laplacian: Not All Small Eigenvalues Are Equal
- Efficient Personalized Community Detection via Genetic Evolution
- A new method for community detection in social networks based on message distribution
- LUEM : Local User Engagement Maximization in Networks
- Detección de comunidades en redes: Algoritmos y aplicaciones
- SoReC: A Social-Relation Based Centrality Measure in Mobile Social Networks