Mvtree for hierarchical network representation based on geometric algebra subspace. (English) Zbl 1403.90216
Summary: Most hierarchical representation methods are designed from engineering perspectives, lacking an appropriate mathematical foundation to integrate different problem definitions. To solve this problem, a hierarchical network representation model based on geometric algebra (GA) subspace is proposed. In this paper, we give a new definition of hierarchical network representation, in which the network nodes are divided into several independent components and multi-level network is constructed based on it. Then these network nodes are coded with basis vectors and the subspace in GA is utilized to represent these nodes of component. Within a subspace or between different subspaces, the topological relation between different basis vectors is defined to connect different subspaces and the complete multi-level network can be formed according to these topological relations in subspaces of different level. A case study is used to show how GA is used to realize the hierarchical network representation and the result indicates that GA can provide an appropriate mathematical foundation for hierarchical network representation.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | Breuils, S., Nozick, V., Fuchs, L.: a geometric algebra implementation using binary tree. Adv. Appl. Clifford Algebras 1-19 (2017) · Zbl 1382.65051 |
| [2] | Cruz-Sánchez, H., Staples, G.S., Schott, R., et al.: Operator calculus approach to minimal paths: Precomputed routing in a store and forward satellite constellation. In: Global Communications Conference (GLOBECOM), pp. 3431-3436. IEEE (2013). https://doi.org/10.1109/GLOCOM.2012.6503645 |
| [3] | Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: McGeoch, C.C. (ed.) Experimental Algorithms. WEA 2008. Lecture Notes in Computer Science, vol 5038, pp. 319-333. Springer, Berlin, Heidelberg (2008) · Zbl 1291.90213 |
| [4] | Geisberger, R; Sanders, P; Schultes, D; etal., Exact routing in large road networks using contraction hierarchies, Transp. Sci., 46, 388-404, (2012) · doi:10.1287/trsc.1110.0401 |
| [5] | Holzer, M; Schulz, F; Wagner, D, Engineering multilevel overlay graphs for shortest-path queries, J. Exp. Algorithmics, 13, 156-170, (2009) · Zbl 1284.05289 · doi:10.1145/1412228.1412239 |
| [6] | Huang, P; Pi, Y, An improved location service scheme in urban environments with the combination of GPS and mobile stations, Wirel. Commun. Mobile Comput., 14, 1287-1301, (2015) · doi:10.1002/wcm.2232 |
| [7] | Jagadeesh, GR; Srikanthan, T; Quek, KH, Heuristic techniques for accelerating hierarchical routing on road networks, IEEE Trans. Intell. Transp. Syst., 3, 301-309, (2002) · doi:10.1109/TITS.2002.806806 |
| [8] | Luo, W; Hu, Y; Yu, Z; etal., A hierarchical representation and computation scheme of arbitrary-dimensional geometrical primitives based on CGA, Adv. Appl. Clifford Algebr, 27, 1977-1995, (2017) · Zbl 1382.65055 · doi:10.1007/s00006-016-0697-3 |
| [9] | Papachristodoulou, A; Li, L; Doyle, JC, Methodological frameworks for large-scale network analysis and design, ACM SIGCOMM Comp. Comm. Rev., 34, 7-20, (2004) · doi:10.1145/1031134.1031138 |
| [10] | Quaglia, A; Sarup, B; Sin, G; etal., Design of a generic and flexible data structure for efficient formulation of large scale network problems, Comp. Aided Chem. Eng., 32, 661-666, (2013) · doi:10.1016/B978-0-444-63234-0.50111-1 |
| [11] | Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In: Brodal, G.S., Leonardi, S. (eds.) Algorithms-ESA 2005. ESA 2005. Lecture Notes in Computer Science, vol 3669, pp. 568-579. Springer, Berlin, Heidelberg (2005) · Zbl 1162.68505 |
| [12] | Schott, R., Staples, S.: Cycles and components in geometric graphs: adjacency operator approach. Probability (2009) |
| [13] | Schultes, D., Sanders, P.: Dynamic highway-node routing. In: Demetrescu, C. (ed.) Experimental Algorithms. WEA 2007. Lecture Notes in Computer Science, vol 4525, pp. 66-79. Springer, Berlin, Heidelberg (2007) · Zbl 1121.68003 |
| [14] | Schulz, F., Wagner, D., Zaroliagis, C.: Using Multi-level Graphs for Timetable Information in Railway Systems. In: Revised Papers From the, International Workshop on Algorithm Engineering and Experiments. pp. 43-59. Springer-Verlag, Heidelberg (2002) · Zbl 1014.68902 |
| [15] | Sims, B.H., Sinitsyn, N., Eidenbenz, S.J.: Visualization and modeling of structural features of a large organizational email network. In: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (Proceeding ASONAM ’13), pp. 787-791. IEEE, Niagara, Ontario, Canada (2013) |
| [16] | Song, Q; Wang, X, Efficient routing on large road networks using hierarchical communities, IEEE Trans. Intell. Transp. Syst., 12, 132-140, (2011) · doi:10.1109/TITS.2010.2072503 |
| [17] | Thorup, M, Integer priority queues with decrease key in constant time and the single source shortest paths problem, J. Comput. Syst. Sci., 69, 330-353, (2004) · Zbl 1084.68030 · doi:10.1016/j.jcss.2004.04.003 |
| [18] | Willhalm, T.: Engineering Shortest Path and Layout Algorithms for Large Graphs. PhD thesis, Universität Karlsruhe (TH), Fakultät für Informatik (2005) · Zbl 1382.65055 |
| [19] | Yu, Z; Luo, W; Yuan, L; etal., Geometric algebra model for geometry-oriented topological relation computation, Trans. GIS, 20, 259-279, (2016) · doi:10.1111/tgis.12154 |
| [20] | Yu, Z; Wang, J; Luo, W; etal., A dynamic evacuation simulation framework based on geometric algebra, Comput. Environ. Urban Syst., 59, 208-219, (2016) · doi:10.1016/j.compenvurbsys.2016.07.003 |
| [21] | Yu, Z., Li, D., Zhu, S., et al.: Multisource multisink optimal evacuation routing with dynamic network changes: a geometric algebra approach. Math. Methods Appl. Sci. 2017(1) (2017). https://doi.org/10.1002/mma.4465 · Zbl 1394.90166 |
| [22] | Yuan, L; Zhao, Y; Luo, W; etal., Geometric algebra for multidimension-unified geographical information system, Adv. Appl. Clifford Algebras, 23, 497-518, (2013) · Zbl 1286.68470 · doi:10.1007/s00006-012-0375-z |
| [23] | Yuan, L; Yu, Z; Luo, W; etal., Clifford algebra method for network expression, computation, and algorithm construction, Math. Methods Appl. Sci., 37, 1428-1435, (2014) · Zbl 1291.90213 · doi:10.1002/mma.2904 |
| [24] | Yuan, L; Yu, Z; Luo, W; etal., Multidimensional-unified topological relations computation: a hierarchical geometric algebra-based approach, Int. J. Geogr. Inf. Sci., 28, 2435-2455, (2014) · doi:10.1080/13658816.2014.929136 |
| [25] | Zhiyuli, A., Liang, X., Zhou, X.: Learning structural features of nodes in large-scale networks for link prediction. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI’16), pp. 4286-4287. AAAI Press, Phoenix, Arizona (2016) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
