Community detection in complex networks to identify bottlenecks and resource waste in bus systems

• Carlos Caminha UNIFOR
• Vasco Furtado UNIFOR
• Vládia Pinheiro UNIFOR
• Caio Ponte UNIFOR

DOI: https://doi.org/10.5753/brasnam.2017.3262

Abstract

Recently it was found that the most part of the population of the world is in large metropolises. This population growth brings with it a series of challenges and public transport appears as a recurrent solution to tackle mobility problems in these big cities. In this work, we carried out a case study to help to understand the shortcomings of public transportation in a city via the mining of complex networks representing the supply and demand of public transport. A process of characterization of the supply and demand networks of the bus system of a large Brazilian metropolis was conducted and it also shed light on the potential overload of demand and waste in the supply of resources that can be mitigated through strategies of supply and demand balance.

References

Banavar, J. R., Damuth, J., Maritan, A., and Rinaldo, A. (2002). Supply–demand balance and metabolic scaling. Proceedings of the National Academy of Sciences, 99(16), 10506-10509.

Barabási, A. L., Albert, R., and Jeong, H. (2000). Scale-free characteristics of random networks: the topology of the world-wide web. Physica A: statistical mechanics and its applications, 281(1), 69-77.

Blondel, V. D., Guillaume, J. L., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10), P10008.

Caminha, C., Furtado, F., Pinheiro, V., and Ponte, P. (2016) Micro-interventions in urban transportation from pattern discovery on the flow of passengers and on the bus network. In Smart Cities Conference (ISC2), 2016 IEEE International, pp. 1–6, IEEE.

Caminha C, Furtado V, Pequeno THC, Ponte C, Melo HPM, Oliveira EA, et al. (2017) Human mobility in large cities as a proxy for crime. PLoS ONE 12(2): e0171609. DOI: 10.1371/journal.pone.0171609,

Chang, S. K., and Schonfeld, P. M. (1991). Multiple period optimization of bus transit systems. Transportation Research Part B: Methodological, 25(6), 453-478.

Chaves, L. (2015). Analisando a mobilidade de pesquisadores através de registros curriculares na Plataforma Lattes. IV Brazilian Workshop on Social Network Analysis and Mining (BraSNAM 2015)

Clauset, A., Shalizi, C. R., and Newman, M. E. (2009). Power-law distributions in empirical data. SIAM review, 51(4), 661-703.

Domencich, T. A., and McFadden, D. (1975). Urban travel demand-a behavioral analysis (No. Monograph).

Elmasry, G. F., and McCann, C. J. (2003, October). Bottleneck discovery in large-scale networks based on the expected value of per-hop delay. In Military Communications Conference, 2003. MILCOM'03. 2003 IEEE (Vol. 1, pp. 405-410). IEEE.

GAO, Z. Y., Wu, J. J., Mao, B. H., and Huang, H. J. (2005). Study on the complexity of traffic networks and related problems [J]. Communication and Transportati0n Systems Engineering and Information, 2, 014.

Girvan, M., and Newman, M. E. (2002). Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12), 7821-7826.

Gordillo, F. (2006). The value of automated fare collection data for transit planning: an example of rail transit od matrix estimation (Doctoral dissertation, Massachusetts Institute of Technology).

Hamon, R., Borgnat, P., Flandrin, P., and Robardet, C. (2013). Networks as signals, with an application to a bike sharing system. In Global Conference on Signal and Information Processing (GlobalSIP), 2013 IEEE (pp. 611-614). IEEE.

Hua-ling, R. (2007, August). Origin-destination demands estimation in congested dynamic transit networks. In Management Science and Engineering, 2007. ICMSE 2007. International Conference on (pp. 2247-2252). IEEE.

Kleiber, M. (1961). The fire of life. An introduction to animal energetics. The fire of life. An introduction to animal energetics.

Lenormand, M., Tugores, A., Colet, P., and Ramasco, JJ (2014). Tweets na estrada. PloS one, 9 (8), e105407.

Munizaga, M. A., and Palma, C. (2012). Estimation of a disaggregate multimodal public transport Origin–Destination matrix from passive smartcard data from Santiago, Chile. Transportation Research Part C: Emerging Technologies, 24, 9-18.

Nadaraya, E. A. (1964). On estimating regression. Theory of Probability & Its Applications, 9(1), 141-142.

Oppenheim, N. (1995). Urban travel demand modeling: from individual choices to general equilibrium. John Wiley and Sons.

Sienkiewicz, J., and Hołyst, J. A. (2005). Statistical analysis of 22 public transport networks in Poland. Physical Review E, 72(4), 046127.

Wang, J., Mo, H., Wang, F., and Jin, F. (2011). Exploring the network structure and nodal centrality of China’s air transport network: A complex network approach. Journal of Transport Geography, 19(4), 712-721.

Watson, G. S. (1964). Smooth regression analysis. Sankhyā: The Indian Journal of Statistics, Series A, 359-372.

Wilkinson, D. M., and Huberman, B. A. (2004). A method for finding communities of related genes. proceedings of the national Academy of sciences, 101(suppl 1), 52415248.