Reducing pivots of approximated betweenness computation by hierarchically clustering complex networks
| Autor: | Rajesh Sharma, Eugenio Zimeo, Angelo Furno, Nour-Eddin El Faouzi |
|---|---|
| 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] |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
050402 sociology
Theoretical computer science Computer science Computation ROAD NETWORKS 02 engineering and technology CLASSIFICATION Computational science 0504 sociology Betweenness centrality ALGORITHME CALCUL 0202 electrical engineering electronic engineering information engineering Cluster analysis Time complexity Parametric statistics COMPLEX NETWORKS 05 social sciences Complex network RESEAU ROUTIER [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation REPRESENTATION GRAPHIQUE Large networks Obstacle 020201 artificial intelligence & image processing BETWEENNESS CENTRALITY |
| Zdroj: | Complex Networks 2017, 6th International Conference on Complex Networks and Their Applications Complex Networks 2017, 6th International Conference on Complex Networks and Their Applications, Nov 2017, Lyon, France. pp.65-77, ⟨10.1007/978-3-319-72150-7_6⟩ Complex Networks & Their Applications VI ISBN: 9783319721491 COMPLEX NETWORKS |
| DOI: | 10.1007/978-3-319-72150-7_6⟩ |
| Popis: | Complex Networks 2017, 6th International Conference on Complex Networks and Their Applications, Lyon, FRANCE, 29-/11/2017 - 01/12/2017; Betweenness centrality is a widely adopted metric to analyze the impact of critical nodes of graphs in several domains (social, biological, transportation, service, computer networks). Its exact computation is very demanding due to an O(nm) time complexity on a graph with n nodes and m edges. This represents an obstacle to the adoption of betweenness centrality for continuous monitoring of critical nodes in very large networks. In this paper, we analyze the performance of a parametric two-level clustering algorithm for computing approximated values of betweenness with different kinds of graph. The analysis aims at evaluating how the properties of different complex networks impact the reduction of the number of single-source shortest-paths explorations of Brandes' algorithm. The results confirm that one-level clustering strongly reduces the number of pivots (and consequently the computation time) on scale-free graphs, while small-world (and random) graphs need an additional level of clustering to achieve acceptable results. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|