ENG
РУС
Search
Menu
About the Edition
Open Access Statement
Editorial Board
Editorial Policy
Editorial Ethics
Rules for peer-review
Rules for presentation of papers
Forms of Submitted Documents
Recommendations for the Design of References to Our Journal
Editorial Staff
Information for Subscribers
Summaries of the Issue
List of Authors
Issues
Publishers license agreement
Procedure of work with personal data
Publications
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.
Partners













































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


Abstract
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”.

References
  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. https://doi.org/10.1103/physreve.67.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. https://doi.org/10.1103/physreve.72.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. https://doi.org/10.1109/mtits.2015.7223282
  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. https://doi.org/10.1016/j.tra.2014.08.004
  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. https://doi.org/10.1016/j.physa.2012.11.036
  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. https://doi.org/10.1016/j.physa.2019.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. https://doi.org/10.1016/j.physa.2018.02.111
  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. https://doi.org/10.1016/j.cities.2019.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. https://doi.org/10.1016/j.procs.2016.11.024
  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. https://doi.org/10.1017/nws.2015.9
  11. Chunaev P. Community detection in node-attributed social networks: A survey. Computer Science Review, 2020, vol. 37, pp. 100286. https://doi.org/10.1016/j.cosrev.2020.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. https://doi.org/10.1007/s10618-021-00741-z
  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. https://doi.org/10.1109/tkde.2014.2349913
  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. https://doi.org/10.48550/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. https://doi.org/10.1155/2021/5571006
  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. https://doi.org/10.1109/icde.2017.128
  17. Revelle M., Domeniconi C., Johri A. Persistent roles in online social networks. Lecture Notes in Computer Science, 2016, vol. 9852, pp. 47–62. https://doi.org/10.1007/978-3-319-46227-1_4
  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. https://doi.org/10.1145/2433396.2433479
  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. https://doi.org/10.1145/2808797.2809412
  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. https://doi.org/10.1038/srep30750
  21. Fortunato S. Community detection in graphs. Physics Reports, 2010, vol. 486, no. 3-5, pp. 75–174. https://doi.org/10.1016/j.physrep.2009.11.002
  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. https://doi.org/10.1080/03081079.2020.1863394
  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. https://doi.org/10.1109/tkde.2019.2911067
  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. https://doi.org/10.1007/s10115-020-01504-w
  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. https://doi.org/10.1007/978-3-030-93413-2_35
  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. https://doi.org/10.1002/asi.24160
  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. https://doi.org/10.1155/2018/2156309
  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. https://doi.org/10.1109/mcas.2019.2945211
  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. https://doi.org/10.1088/1742-5468/2016/03/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. https://doi.org/10.1016/j.physa.2017.01.085
  31. Faust K., Wasserman S. Blockmodels: Interpretation and evaluation. Social Networks, 1992, vol. 14, no. 1, pp. 5–61. https://doi.org/10.1016/0378-8733(92)90013-w
  32. Batagelj V., Mrvar A., Ferligoj A., Doreian P. Generalized blockmodeling with Pajek. Metodološki zvezki, 2004, vol. 1, no. 2, pp. 455–467. https://doi.org/10.51936/ofaw1880
  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. https://doi.org/10.1006/jtbi.2003.3147
  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. https://doi.org/10.1145/1935826.1935877
  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. https://doi.org/10.1080/13658816.2019.1566551
  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. https://doi.org/10.1145/3397536.3422198
  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.

Яндекс.Метрика