Performing centrality analysis on nodes from transportation networks are critical to identify important hubs, understand travel decisions, and assess system performances. Current centrality measures are based on topological characteristics of nodes and edges. When applying those measures to large-scale transportation networks, two problems remain unsolved. First, measures are computed based on simplified travel paths, which only include origins and destinations. Due to the lack of information about waypoints of routes, such network representation may not preserve fine level information about waypoints, routes, and traffic flow patterns, resulting in an inaccurate view of centrality. Second, most centrality measures are global measures that rank all nodes in a network, thus failing to detect nodes of regional importance. Therefore, this paper describes an approach that leverages the concept of sequences to identify key waypoints from frequent travel paths and detect community structures of transportation networks. This approach extends two complementary centrality measures to define the role of nodes within communities. The approach has been tested using tracking data of ships in a regional maritime transportation network. Compared to traditional measurement approaches, the proposed approach can construct compact communities, discover prominent waypoints, and add new insight with local centrality measure.

References

1. 1)
  - 33. Litvak, N., Scheinhardt, W.R., Volkovich, Y.: ‘In-degree and PageRank: why do they follow similar power laws?’, Internet. Math., 2007, 4, (2-3), pp. 175–198.
2. 2)
  - 8. Cao, H., Mamoulis, N., Cheung, D.W.: ‘Mining frequent spatio-temporal sequential patterns’. Fifth IEEE Int. Conf. on Data Mining (ICDM'05), Texas, USA, November 2005, p. 8–pp.
3. 3)
  - 12. Laxe, F.G., Seoane, M.J.F., Montes, C.P.: ‘Maritime degree, centrality and vulnerability: port hierarchies and emerging areas in containerized transport (2008–2010)’, J. Transp. Geogr., 2012, 24, pp. 33–44.
4. 4)
  - 1. Li, J., Wang, X., Zhang, T., et al: ‘Efficient parallel K best connected trajectory (K-BCT) query with GPGPU: A combinatorial min-distance and progressive bounding box approach’, ISPRS. Int. J. Geoinf., 2018, 7, (7), p. 239.
5. 5)
  - 13. Ducruet, C., Lee, S.-W., Ng, A.K.: ‘Centrality and vulnerability in liner shipping networks: revisiting the Northeast Asian port hierarchy’, Marit. Policy Manage., 2010, 37, (1), pp. 17–36.
6. 6)
  - 27. Ducruet, C., Notteboom, T.: ‘The worldwide maritime network of container shipping: spatial structure and regional dynamics’, Global Netw., 2012, 12, (3), pp. 395–423.
7. 7)
  - 28. Filipiak, D., Węcel, K., Stróżyna, M., et al: ‘Extracting maritime traffic networks from AIS data using evolutionary algorithm’, Bus. Inf. Syst. Eng., 2020, 62, (5), pp. 435–450.
8. 8)
  - 21. Newman, M.E.: ‘Communities, modules and large-scale structure in networks’, Nat. Phys., 2012, 8, (1), pp. 25–31.
9. 9)
  - 22. Rossetti, G., Pedreschi, D., Giannotti, F.: ‘Node-centric community discovery: from static to dynamic social network analysis’, Online Soc. Netw. Media, 2017, 3, pp. 32–48.
10. 10)
  - 16. Cummings, M.L., Buchin, M., Carrigan, G., et al: ‘Supporting intelligent and trustworthy maritime path planning decisions’, Int. J. Hum.-Comput. Stud., 2010, 68, (10), pp. 616–626.
11. 11)
  - 29. Shaw, A.A., Gopalan, N.P.: ‘Finding frequent trajectories by clustering and sequential pattern mining’, J. Traffic Transp. Eng. (English Edition), 2014, 1, (6), pp. 393–403.
12. 12)
  - 6. Wang, D., Miwa, T., Morikawa, T.: ‘Big trajectory data mining: a survey of methods, applications, and services’, Sensors, 2020, 20, (16), p. 4571.
13. 13)
  - 30. Page, L., Brin, S., Motwani, R., et al: ‘The pagerank citation ranking: bringing order to the web.’ (Stanford InfoLab, Stanford, 1999).
14. 14)
  - 7. Zheng, Y.: ‘Trajectory data mining: an overview’, ACM Trans. Intell. Syst. Technol. (TIST), 2015, 6, (3), pp. 1–41.
15. 15)
  - 5. Ghalmane, Z., El Hassouni, M., Cherifi, C., et al: ‘Centrality in modular networks’, EPJ Data Sci., 2019, 8, (1), p. 15.
16. 16)
  - 10. Dobrkovic, A., Iacob, M.-E., van Hillegersberg, J.: ‘Maritime pattern extraction and route reconstruction from incomplete AIS data’, Int. J. Data Sci. Analytics, 2018, 5, (2-3), pp. 111–136.
17. 17)
  - 31. Luo, F., Wang, J.Z., Promislow, E.: ‘Exploring local community structures in large networks’, Web Intell. Agent Syst., Int. J., 2008, 6, (4), pp. 387–400.
18. 18)
  - 32. Wu, Y., Raschid, L.: ‘Subgraphrank: PageRank approximation for a subgraph or in a decentralized system’, 2007.
19. 19)
  - 18. Newman, M.E.: ‘A measure of betweenness centrality based on random walks’, Soc. Networks., 2005, 27, (1), pp. 39–54.
20. 20)
  - 15. Fiorini, M., Capata, A., Bloisi, D.D.: ‘AIS data visualization for maritime spatial planning (MSP)’, Int. J. E-Navig. Marit. Econ., 2016, 5, pp. 45–60.
21. 21)
  - 25. Fleming, D.K., Hayuth, Y.: ‘Spatial characteristics of transportation hubs: centrality and intermediacy’, J. Transp. Geogr., 1994, 2, (1), pp. 3–18.
22. 22)
  - 3. Dobrkovic, A., Iacob, M.-E., van Hillegersberg, J.: ‘Using machine learning for unsupervised maritime waypoint discovery from streaming AIS data’. Proc. of the 15th Int. Conf. on Knowledge Technologies and Data-driven Business, Graz, Austria, October 2015, pp. 1–8.
23. 23)
  - 24. Holme, P.: ‘Congestion and centrality in traffic flow on complex networks’, Adv. Complex Syst., 2003, 6, (2), pp. 163–176.
24. 24)
  - 11. Perera, L.P., Oliveira, P., Soares, C.G.: ‘Maritime traffic monitoring based on vessel detection, tracking, state estimation, and trajectory prediction’, IEEE Trans. Intell. Transp. Syst., 2012, 13, (3), pp. 1188–1200.
25. 25)
  - 20. Oldham, S., Fulcher, B., Parkes, L., et al: ‘Consistency and differences between centrality measures across distinct classes of networks’, PloS one, 2019, 14, (7), p. e0220061.
26. 26)
  - 17. Wang, Y., Cullinane, K.: ‘Determinants of port centrality in maritime container transportation’, Transp. Res. E, Log. Transp. Rev., 2016, 95, pp. 326–340.
27. 27)
  - 2. Wang, X., Li, J., Zhang, T.: ‘A machine-learning model for zonal ship flow prediction using AIS data: a case study in the south atlantic states region’, J. Mar. Sci. Eng., 2019, 7, (12), p. 463.
28. 28)
  - 9. Tetreault, B.J.: ‘Use of the automatic identification system (AIS) for maritime domain awareness (MDA)’. Proc. of Oceans 2005 Mts/Ieee, 2005, pp. 1590–1594.
29. 29)
  - 14. Arguedas, V.F., Pallotta, G., Vespe, M.: ‘Maritime traffic networks: from historical positioning data to unsupervised maritime traffic monitoring’, IEEE Trans. Intell. Transp. Syst., 2017, 19, (3), pp. 722–732.
30. 30)
  - 26. Guimera, R., Mossa, S., Turtschi, A., et al: ‘The worldwide air transportation network: anomalous centrality, community structure, and cities’ global roles’, Proc. Natl. Acad. Sci., 2005, 102, (22), pp. 7794–7799.
31. 31)
  - 23. Cheng, Y.-Y., Lee, R.K.-W., Lim, E.-P., et al: ‘Delayflow centrality for identifying critical nodes in transportation networks’. Proc. of the 2013 IEEE/ACM Int. Conf. on Advances in Social Networks Analysis and Mining, Ontario, Canada, August 2013, pp. 1462–1463.
32. 32)
  - 4. Ducruet, C., Lugo, I.: ‘Structure and dynamics of transportation networks: models, methods and applications’, in: ‘The SAGE handbook of transport studies’ (SAGE Publications, Ltd., London, 2013), pp. 347–364.
33. 33)
  - 19. Fortunato, S., Latora, V., Marchiori, M.: ‘Method to find community structures based on information centrality’, Phys. Rev. E, 2004, 70, (5), p. 056104.

Sequence-based centrality measures in maritime transportation networks

References

Related content