Fast Computing Betweenness Centrality with Virtual Nodes on Large Sparse Networks
Author Information
Author(s): Yang Jing, Chen Yingwu
Primary Institution: National University of Defense Technology, Changsha, China
Hypothesis
Can a new algorithm using virtual nodes compute betweenness centrality more efficiently in large sparse networks?
Conclusion
The proposed VN algorithm significantly reduces computation time for betweenness centrality in large sparse networks with low average edge weights.
Supporting Evidence
- The VN algorithm performs better when the average edge weight is low.
- Numerical simulations show that the VN algorithm is faster than the Brandes algorithm in large sparse networks.
- The VN algorithm can be generalized to calculate other network properties.
Takeaway
This study shows a new way to calculate how important a point is in a network, making it much faster for big networks with few weights.
Methodology
The study proposes a new algorithm that replaces weighted edges with virtual nodes to compute betweenness centrality using breadth-first search.
Limitations
The VN algorithm is sensitive to network density and may not outperform the Brandes algorithm in dense networks with high weights.
Digital Object Identifier (DOI)
Want to read the original?
Access the complete publication on the publisher's website