Two-level clustering fast betweenness centrality computation for requirement-driven approximation

Autor: Angelo Furno, N. E. El Faouzi, Eugenio Zimeo, Rajesh Sharma
Přispěvatelé: Laboratoire d'Ingénierie Circulation Transport (LICIT UMR TE), Université de Lyon-École Nationale des Travaux Publics de l'État (ENTPE)-Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR), University of Tartu, University of Sannio [Benevento]
Rok vydání: 2017
Předmět:
Theoretical computer science
CONTINUOUS MONITORING
BIG DATA
Computer science
Computation
REQUIREMENT-DRIVEN
RESEAU DE TRANSPORT
02 engineering and technology
GRAPH THEORY
CALCUL D'ERREURS
PETROLEUM RESERVOIR EVALUATION
Betweenness centrality
APPROXIMATION ERRORS
ALGORITHME
Approximation error
SURVEILLANCE
ROUTE
CALCUL
0502 economics and business
OPERATIONAL MONITORING
0202 electrical engineering
electronic engineering
information engineering
MONITORING
SINGLE SOURCE SHORTEST PATHS
Cluster analysis
Graph property
Time complexity
COMPLEX NETWORKS
TOPOLOGICAL PROPERTIES
ROADS AND STREETS
050210 logistics & transportation
TRANSPORTATION NETWORK
05 social sciences
TOPOLOGIE
Approximation algorithm
RESEAU ROUTIER
[INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation
Graph
CLUSTERING ALGORITHMS
REPRESENTATION GRAPHIQUE
APPROXIMATION ALGORITHMS
MOTOR TRANSPORTATION
Metric (mathematics)
BETWEENNESS CENTRALITY
020201 artificial intelligence & image processing
Algorithm design
Zdroj: IEEE BigData
BIGDATA 2017 IEEE International Conference on Big Data
BIGDATA 2017 IEEE International Conference on Big Data, Dec 2017, Boston, United States. pp.1289-1294, ⟨10.1109/BigData.2017.8258057⟩
DOI: 10.1109/bigdata.2017.8258057
Popis: BIGDATA 2017 IEEE International Conference on Big Data, Boston, ETATS-UNIS, 11-/12/2017 - 14/12/2017; Betweenness centrality is a metric widely used in several domains (social, biological, transportation, computer) to identify critical nodes of networks. Its exact computation is very demanding, with an O(nm) time complexity for unweighted graphs (where n is the number of nodes and m is the number of edges). Such complexity becomes an obstacle to the adoption of betweenness centrality for continuous monitoring of critical nodes in very large networks. Several solutions have been proposed to reduce computation time, mainly via parallelism, approximation or incremental recalculation. In this paper, we propose an algorithm for computing approximated values of betweenness that allows for tuning its performance on the basis of a tolerable error. The algorithm aims at reducing the number of single-source shortest-paths explorations via a pivot-based technique that exploits topological properties of graphs and clustering. It is evaluated by identifying the vulnerabilities (critical nodes) of a real-world, very-large road network. The evaluation shows that the approximation error does not significantly affect the most critical nodes, thus making the algorithm well-suited for on-line operational monitoring of road networks.
Databáze: OpenAIRE
Externí odkaz: