Software implementation of Dijkstra's algorithm in graphstructural modeling of socio-economic systems using metagraphs

The developing of social networks, various data collection and storage systems and the accumulation of large amounts of information graph structures received another incentive for development. Since one of their main advantages is the ability to present compact and understandable models of complex systems. The graph-structural approach is especially productive in solving problems related to the analysis of various nature networks such as social networks, web graphs, traffic road networks and others. These objects are characterized by a large volume and complex structure so the question of using generalized graph structures to describe them is very relevant. A number of advantages can be distinguished as a justification: reducing the dimension of the source data without losing information, reducing the complexity of interpreting intermediate results, the ability to remodel tasks at several stages and others. The article is devoted to issues related to the development of the mathematical apparatus for constructing graphostructural models of complex systems. Generalizations of the concept of a graph such as undirected and oriented hypergraphs and metagraphs are considered. An example of a software implementation of a hierarchical system based on a metagraph is given. This approach allows to vary the degree of data detail without its modification.

1. Biggs N. Algebraic Graph Theory. Cambrige University Press. 1993.

2. Even Sh. Graph Algorithms: Second Edition. Cambrige University Press.2012

3. Bretto A. Hypergraph Theory: An Introduction. Springer, Heidelberg. 2013.

4. Catalyurek U.V., Boman E.G., Devine K.D., Bozdag D. Hypergraph-based Dynamic Load Balancing for Adaptive Scientific Computations. In: 2007 IEEE International Parallel and Distributed Processing Symposium. Rome. 2007.

5. Kwang H., Lee K. Fuzzy hypergraph and fuzzy partition. IEEE Transactions on Systems, Man, and Cybernetics. 1995;25(1):196-201.

6. Lee J., Cho M., Lee K.M. Hyper-graph matching via reweighted random walks. In: CVPR 2011. Providence, RI. 2011.

7. Huang Y., Liu Q., Zhang S., Metaxas D.N. Image retrieval via probabilistic hypergraph ranking. In: 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Francisco, CA. 2010.

8. Basu A., Blanning R. Metagraphs: A Tool for Modeling Decision Support Systems. Management Science. 1994;40(12):1579-1763.

9. Fang Y., Lin W., Zheng V.W., Wu M. Semantic proximity search on graphs with metagraph-based learning. In: IEEE 32nd International Conference on Data Engineering (ICDE). Helsinki. 2016.

10. Zhao H., Yao Q., Li J., Song Y., Lee D. Meta-Graph Based Recommendation Fusion over Heterogeneous Information Networks. In: KDD '17: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Canada. 2017

11. Gaur D., Shastri A., Biswas R. Metagraph-Based Substructure Pattern Mining. In: International Conference on Advanced Computer Theory and Engineering. Phuket. 2008.

12. Miroshnikov A., Zhbanova N. Describing the Structures of Socio-economic Systems Using Metagraphs. In: 1st International Conference on Control Systems, Mathematical Modelling, Automation and Energy Efficiency. Lipetsk, Russia. 2019.

13. Blyumin S.L. Graphs, hypergraphs, metagraphs associated with 2D systems. Proceedings of the international science and practical conf. “Modern mathematics and its applications”. Sterlitamak. 2017

14. Blyumin S.L. Grafostructural modeling. Metagraphs and their matrices. Bulletin of Lipetsk State Technical University. 2015;1(23):7-13.

15. Gerasimenko O.N., Miroshnikov A.I. Managing production tasks in socio-economic systems considering seasonal environmental impact. Ecology of the Central Black Earth Region of the Russian Federation. 2012;2:87-88.