doi: 10.17586/2226-1494-2023-23-2-340-351

Role discovery in node-attributed public transportation networks: the model description

Y. V. Lytkin, P. V. Chunaev, T. A. Gradov, A. A. Boytsov, I. A. Saitov

Read the full article  ';
Article in Russian

For citation:
Lytkin Yu.V., Chunaev P.V., Gradov T.A., Boytsov A.A., Saitov I.A. Role discovery in node-attributed public transportation networks: the model description. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2023, vol. 23, no. 2, pp. 340–351. doi: 10.17586/2226-1494-2023-23-2-340-351

Modeling public transport systems from the standpoint of the theory of complex networks is of great importance to improve their efficiency and reliability. An important task here is to analyze the roles of nodes and weighted links in the network, respectively modeling groups of public transport stops and their linking routes. In previous works, this problem was solved based on only topological and geospatial information about the presence of routes between stops and their geographical location which led to the problem of uninterpretability of the discovered roles. In this article, to solve the problem, the model additionally considers information about the social infrastructure around the stops and discovers topological, geospatial, and infrastructure roles jointly. The public transport system is modeled using a special weighted network — with node attributes where nodes are non-overlapping groups of stops united by geospatial location, node attributes are vectors containing information about the social infrastructure around stops, and weighted links integrate information about the distance and number of transfers in routes between stops. To identify the model, it is sufficient to use only open urban data on the public transport system. Role discovery for stops is carried out by clustering network nodes in accordance with their topological and attributive features. An extended model of the public transport system and a new approach to solving the problem of discovering the roles of stops, providing interpretability from the topological, geospatial and infrastructural points of view, are proposed. The model was identified on the open data of Saint Petersburg about metro stations, trolleybus and bus stops as well as organizations and enterprises around the stations and stops. Based on the data, balanced parameters for grouping stops, assigning link weights and constructing attribute vectors are found for further use in the role discovery task. The results of the study can be used to identify transport and infrastructure shortcomings of real public transport systems which should be considered to improve the functioning of these systems in the future.

Keywords: node-attributed network, public transportation network, role discovery, network node classification, network topology, social infrastructure

Acknowledgements. This study is supported by the Russian Science Foundation, Agreement No. 17-71-30029, with co-financing of the “Bank Saint Petersburg”.

  1. Sen P., Dasgupta S., Chatterjee A., Sreeram P.A., Mukherjee G., Manna S.S. Small-world properties of the indian railway network. Physical Review E, 2003, vol. 67, no. 3, pp. 036106.
  2. Sienkiewicz J., Hołyst J. Statistical analysis of 22 public transport networks in Poland. Physical Review E, 2005, vol. 72, no. 4, pp. 046127.
  3. Haznagy A., Fi I., London A., Nemeth T. Complex network analysis of public transportation networks: A comprehensive study. Proc. of the 2015 International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), 2015, pp. 371–378.
  4. Yang X.-H., Chen G., Chen S.-Y., Wang W.-L., Wang L. Study on some bus transport networks in china with considering spatial characteristics. Transportation Research Part A: Policy and Practice, 2014, vol. 69, no. 1, pp. 1–10.
  5. Zhang J., Zhao M., Liu H., Xu X. Networked characteristics of the urban rail transit networks. Physica A: Statistical Mechanics and its Applications, 2013, vol. 392, no. 6, pp. 1538–1546.
  6. Wang L.-N., Wang K., Shen J.-L. Weighted complex networks in urban public transportation: Modeling and testing.Physica A: Statistical Mechanics and its Applications, 2020, vol. 545, pp. 123498.
  7. Shanmukhappa T., Ho I.W.-H., Chi K.T. Spatial analysis of bus transport networks using network theory. Physica A: Statistical Mechanics and its Applications, 2018, vol. 502, pp. 295–314.
  8. Wang Y., Deng Y., Ren F., Zhu R., Wang P., Du T., Du Q. Analysing the spatial configuration of urban bus networks based on the geospatial network analysis method. Cities, 2020, vol. 96, pp. 102406.
  9. Lantseva A., Ivanov S. Modeling transport accessibility with open data: Case study of st. Petersburg. Procedia Computer Science, 2016, vol. 101, pp. 197–206.
  10. Bothorel C., Cruz J., Magnani M., Micenková B. Clustering attributed graphs: Models, measures and methods. Network Science, 2015, vol. 3, no. 3, pp. 408–444.
  11. Chunaev P. Community detection in node-attributed social networks: A survey. Computer Science Review, 2020, vol. 37, pp. 100286.
  12. Atzmueller M., Günnemann S., Zimmermann A. Mining communities and their descriptions on attributed graphs: a survey. Data Mining and Knowledge Discovery, 2021, vol. 35, no. 3, pp. 661–687.
  13. Rossi R.A., Ahmed N.K. Role discovery in networks. IEEE Transactions on Knowledge and Data Engineering, 2015, vol. 27, no. 4, pp. 1112–1131.
  14. Ahmed N.K., Rossi R.A., Willke T.L., Zhou R. Revisiting role discovery in networks: From node to edge roles. ArXiv, 2016, arXiv:1610.00844.
  15. Martínez V., Berzal F., Cubero J.-C. An automorphic distance metric and its application to node embedding for role mining. Complexity, 2021, vol. 2021, pp. 1–17.
  16. Gupte P.V., Ravindran B., Parthasarathy S. Role discovery in graphs using global features: Algorithms, applications and a novel evaluation strategy. Proc. of the IEEE 33rd International Conference on Data Engineering (ICDE), 2017, pp. 771–782.
  17. Revelle M., Domeniconi C., Johri A. Persistent roles in online social networks. Lecture Notes in Computer Science, 2016, vol. 9852, pp. 47–62.
  18. Rossi R.A., Gallagher B., Neville J., Henderson K. Modeling dynamic behavior in large evolving graphs. Proc. of the Sixth ACM International Conference on Web Search and Data Mining (WSDM’13), 2013, pp. 667–676.
  19. Vega D., Meseguer R., Freitag F., Magnani M. Role and position detection in networks: Reloaded. Proc. of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 2015, pp. 320–325.
  20. Yang Z., Algesheimer R., Tessone C.J. A comparative analysis of community detection algorithms on artificial networks. Scientific Reports, 2016, vol. 6, no. 1, pp. 30750.
  21. Fortunato S. Community detection in graphs. Physics Reports, 2010, vol. 486, no. 3-5, pp. 75–174.
  22. Souravlas S., Sifaleras A., Tsintogianni M., Katsavounis S. A classification of community detection methods in social networks: a survey. International Journal of General Systems, 2021, vol. 50, no. 1, pp. 63–91.
  23. Bartal A., Ravid G. Member behavior in dynamic online communities: Role affiliation frequency model. IEEE Transactions on Knowledge and Data Engineering, 2020, vol. 32, no. 9, pp. 1773–1784.
  24. Ni W., Guo H., Liu T., Zeng Q. Automatic role identification for research teams with ranking multi-view machines. Knowledge and Information Systems, 2020, vol. 62, no. 12, pp. 4681–4716.
  25. Liu S., Toriumi F., Nishiguchi M., Usui S. Multiple role discovery in complex networks. Studies in Computational Intelligence, 2022, vol. 1016, pp. 415–427.
  26. Liu Y., Du F., Sun J., Silva T., Jiang Y., Zhu T. Identifying social roles using heterogeneous features in online social networks. Journal of the Association for Information Science and Technology, 2019, vol. 70, no. 7, pp. 660–674.
  27. Zhang L., Lu J., Fu B., Li S. A review and prospect for the complexity and resilience of urban public transit network based on complex network theory. Complexity, 2018, vol. 2018, pp. 1–36.
  28. Shanmukhappa T., Ho I.W.-H., Tse C.K., Leung K.K. Recent development in public transport network analysis from the complex network perspective. IEEE Circuits and Systems Magazine, 2019, vol. 19, no. 4, pp. 39–65.
  29. Xu Q., Mao B., Bai Y. Network structure of subway passenger flows. Journal of Statistical Mechanics: Theory and Experiment, 2016, vol. 2016, no. 3, pp. 033404.
  30. Feng J., Li X., Mao B., Xu Q., Bai Y. Weighted complex network analysis of the beijing subway system: Train and passenger flows. Physica A: Statistical Mechanics and its Applications, 2017, vol. 474, pp. 213–223.
  31. Faust K., Wasserman S. Blockmodels: Interpretation and evaluation. Social Networks, 1992, vol. 14, no. 1, pp. 5–61.
  32. Batagelj V., Mrvar A., Ferligoj A., Doreian P. Generalized blockmodeling with Pajek. Metodološki zvezki, 2004, vol. 1, no. 2, pp. 455–467.
  33. Luczkovich J., Borgatti S., Johnson J.C., Everett M.G. Defining and measuring trophic role similarity in food webs using regular equivalence. Journal of theoretical biology, 2003, vol. 220, no. 3, pp. 303–21.
  34. Ma H., Zhou D., Liu C., Lyu M.R., King I. Recommender systems with social regularization. Proc. of the Fourth ACM International Conference on Web Search and Data Mining (WSDM’11), 2011, pp. 287–296.
  35. Golder S.A., Donath J. Social roles in electronic communities. Internet Research, 2004, vol. 5.
  36. Yue H., Guan Q., Pan Y., Chen L., Lv J., Yao Y. Detecting clusters over intercity transportation networks using k-shortest paths and hierarchical clustering: a case study of mainland China. International Journal of Geographical Information Science, 2019, vol. 33, no. 5, pp. 1082–1105.
  37. Bereznyi D., Qutbuddin A., Her Y., Yang K. Node-attributed spatial graph partitioning. Proc. of the 28th International Conference on Advances in Geographic Information Systems (SIGSPATIAL’20), 2020, pp. 58–67.
  38. MacQueen J. Some methods for classification and analysis of multivariate observations. Proc. of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. V. 1. Statistics, 1967, pp. 281–297.

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Copyright 2001-2024 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.