Weitere Kapitel dieses Buchs durch Wischen aufrufen
Variety of real-life structures can be simplified by a graph. Such simplification emphasizes the structure represented by vertices connected via edges. A common method for the analysis of the vertices importance in a network is betweenness centrality. The centrality is computed using the information about the shortest paths that exist in a graph. This approach puts the importance on the edges that connect the vertices. However, not all vertices are equal. Some of them might be more important than others or have more significant influence on the behavior of the network. Therefore, we introduce the modification of the betweenness centrality algorithm that takes into account the vertex importance. This approach allows the further refinement of the betweenness centrality score to fulfill the needs of the network better. We show this idea on an example of the real traffic network. We test the performance of the algorithm on the traffic network data from the city of Bratislava, Slovakia to prove that the inclusion of the modification does not hinder the original algorithm much. We also provide a visualization of the traffic network of the city of Ostrava, the Czech Republic to show the effect of the vertex importance adjustment. The algorithm was parallelized by MPI (http://www.mpi-forum.org/) and was tested on the supercomputer Salomon (https://docs.it4i.cz/) at IT4Innovations National Supercomputing Center, the Czech Republic.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Xia, J., Sun, J., Jia, P., & Zhao, Z. (2011). Do cancer proteins really interact strongly in the human protein–protein interaction network? Computational Biology and Chemistry, 35, 121–125. CrossRef
Hagmann, P., Cammoun, L., Gigandet, X., Meuli, R., Honey, C. J., Wedeen, V. J., et al. (2008). Mapping the structural core of human cerebral cortex. PLoS Biology, 6, 1479–1493. CrossRef
Everett, M. G., & Borgatti, S. P. (1999). The centrality of groups and classes. Journal of Mathematical Sociology, 23, 181–201. CrossRef
Szell, M., & Thurner, S. (2010). Measuring social dynamics in a massive multiplayer online game. Social Networks, 32, 313–329. CrossRef
Wasserman, S., & Faust, K. (1994). Social network analysis: Methods and applications. Cambridge, England: Cambridge University Press. CrossRef
Clifton, A., Turkheimer, E., & Oltmanns, T. F. (2009). Personality disorder in social networks: Network position as a marker of interpersonal dysfunction. Social Networks, 31, 26–32. CrossRef
Vandenberghe, R., Wang, Y., Nelissen, N., Vandenbulcke, M., Dhollander, T., Sunaert, S., et al. (2013). The associative-semantic network for words and pictures: Effective connectivity and graph analysis. Brain and Language, 127, 264–272. CrossRef
He, T., Zhao, J., Li, J. (2006). Discovering relations among named entities by detecting community structure. In PACLIC20 (pp. 42–48).
Donges, J. F., Zou, Y., Marwan, N., & Kurths, J. (2009). The backbone of the climate network. EPL (Europhysics Letters), 87.
Zhang, G. Q., Wang, D., & Li, G. J. (2007). Enhancing the transmission efficiency by edge deletion in scale-free networks. Physical Review E, 76.
Zhou, S., & Mondragón, R. J. (2004). Accurately modeling the internet topology. Physical Review E, 70.
Comin, C. H., & Da Fontoura Costa, L. (2011). Identifying the starting point of a spreading process in complex networks. Physical Review E, 84.
Kawamoto, H., & Igarashi, A. (2012). Efficient packet routing strategy in complex networks. Physica A: Statistical Mechanics and its Applications, 391, 895–904. CrossRef
Daganzo, C. F. (1994). The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory. Transportation Research Part B: Methodological, 28, 269–287. CrossRef
Wang, Y., & Papageorgiou, M. (2005). Real-time freeway traffic state estimation based on extended Kalman filter: A general approach. Transportation Research Part B: Methodological, 39, 141–167. CrossRef
Ngoduy, D. (2007). Real time multiclass traffic flow modelling-English M25 freeway case study. In 12th Conference of the Hong-Kong Society for Transportation Studies (pp. 143–152).
Shang, P., Li, X., & Kamae, S. (2005). Chaotic analysis of traffic time series. Chaos, Solitons & Fractals, 25, 121–128. CrossRef
Galafassi, C., & Bazzan, A. L. C. (2013). Analysis of traffic behavior in regular grid and real world networks.
Kazerani, A., & Winter, S. (2009). Can betweenness centrality explain traffic flow? In 12th AGILE International Conference on Geographic Information Science (pp. 1–9).
Gao, S., Wang, Y., Gao, Y., & Liu, Y. (2012). Understanding urban traffic flow characteristics: A rethinking of betweenness centrality. Environment and Planning B: Planning and Design.
Zhao, P. X., & Zhao, S. M. (2016). Understanding urban traffic flow characteristics from the network centrality perspective at different granularities. International Archives of the Photogrammetry Remote Sensing and Spatial Information Sciences, 41, 263–268. CrossRef
Piggins, A. (2012). Rationality for mortals: how people cope with uncertainty, by gerd gigerenzer. The Journal of Positive Psychology, 7, 75–76. CrossRef
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40, 35–41. CrossRef
Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology.
- Vertex Importance Extension of Betweenness Centrality Algorithm
- Springer Singapore