Computing Vertex Centrality Measures in Massive Real Networks with a Neural Learning Model
arXiv:1811.12809 · doi:10.1109/IJCNN.2018.8489690
Abstract
Vertex centrality measures are a multi-purpose analysis tool, commonly used in many application environments to retrieve information and unveil knowledge from the graphs and network structural properties. However, the algorithms of such metrics are expensive in terms of computational resources when running real-time applications or massive real world networks. Thus, approximation techniques have been developed and used to compute the measures in such scenarios. In this paper, we demonstrate and analyze the use of neural network learning algorithms to tackle such task and compare their performance in terms of solution quality and computation time with other techniques from the literature. Our work offers several contributions. We highlight both the pros and cons of approximating centralities though neural learning. By empirical means and statistics, we then show that the regression model generated with a feedforward neural networks trained by the Levenberg-Marquardt algorithm is not only the best option considering computational resources, but also achieves the best solution quality for relevant applications and large-scale networks. Keywords: Vertex Centrality Measures, Neural Networks, Complex Network Models, Machine Learning, Regression Model
arXiv comment8 pages, 5 tables, 2 figures, version accepted at IJCNN 2018. arXiv admin note: text overlap with arXiv:1810.11760
References in corpus (7)
- Finding and evaluating community structure in networks
- Characterization of complex networks: A survey of measurements
- Community structure and scale-free collections of Erdös-Rényi graphs
- Robust network community detection using balanced propagation
- A Scalable Generative Graph Model with Community Structure
- Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality
- An Analysis of Centrality Measures for Complex and Social Networks