# DEVELOPMENT OF A MATRIX REPRESENTATION OF GENERALIZED GRAPH STRUCTURES IN PROBLEMS OF BIG DATA DESCRIPTION AND ANALYSIS

( Pp. 9-15)

More about authors

Blyumin Semyon Lvovich
professor, doktor fiz.-mat. nauk, kafedra prikladnoy matematiki

Lipetsk State Technical University, Lipetsk, Russia Prinkov Alexey Sergeevich student, kafedra prikladnoy matematiki

Lipetsk State Technical University, Lipetsk, Russia

Lipetsk State Technical University, Lipetsk, Russia Prinkov Alexey Sergeevich student, kafedra prikladnoy matematiki

Lipetsk State Technical University, Lipetsk, Russia

Abstract:

Objective. To consider the practical aspects of graph-structural modeling in problems of describing and analyzing big data, and to develop matrix representations of generalized graph structures: graphs, hypergraphs, networks, hypernetworks and metagraphs [1-4]. To outline the results of preliminary studies and to outline the prospects for further research. Describe the set-theoretic and matrix variants of representation of graph structures in the context of optimization of computations in problems of describing and analyzing big data, highlighting the shortcomings and advantages of these approaches. On this basis, show the validity of the motivation for using generalized graph structures in such problems [5, 6]. Develop an algorithm that uses a matrix representation, transforming an arbitrary graph into a metagraph.Model and methods. The field of research is generalized graph structures and variants of their representation, especially matrix ones, as well as a practical application in the field of modeling and analysis of big data, complex systems and networks. Generalized graph structures are used as models [1-4].Conclusions. In this paper, graphs and generalized graph structures were considered and variants of their practical use are presented. The set-theoretic and matrix variants of the representation of these structures in the context of optimization of computations in problems of describing and analyzing big data are described. On this basis, the validity of the motivation for using generalized graph structures in such problems is shown. A heuristic algorithm is developed that uses a matrix representation, transforming an arbitrary graph into a metagraph. This algorithm transforms the incidence matrix of the graph into the incidence matrix of an isomorphic metagraph. A hierarchy is constructed that reflects the sequence of generalization of some structures by others. The features of generalized graph structures, in particular metagraphs, are identified as the most general and at the same time sufficient for modeling arbitrary relationships of the structure. Each chapter is accompanied by conclusions in the context of optimization of computations and modeling efficiency with the prospect of using parallel and distributed computing technologies. Bounds of the research and the possibility of subsequent use of the results of scientific work. In this paper, the main tools of graphstructural modeling in the problems of describing and analyzing big data were considered, including graphs, hypergraphs, networks, hypernetworks and metagraphs. The task of developing matrix algebra and matrix representation of these structures for application in the analysis and description of big data is promising, as is confirmed by the materials of this work. GraphBLAS [7] is a developed software library and the same direction of scientific research for the development of this library, the main idea of which is an attempt to describe algorithms on graphs in terms of operations of linear algebra. The final product of the study of the matrix representationof generalized graph structures will be the evolution of the GraphBLAS ideas.Practical significance. In this paper, we consider the application of the results obtained in the problems of describing and analyzing big data. There are two ways: presentation of the raw data and modeling of information systems with which to process this data. Particular attention is paid to the constructionof hybrid intelligent systems, which in general is possible only with the use of generalized graph structures. It is worth noting that practical significance is not limited to these areas. Also, the work mentions the possibility of solving classical problems by changing the formalization of the initial and limiting conditions by the example of the task of the Chinese postman.Originality/value. The article may be of interest to specialists in the field of discrete mathematics by formalization and its consequences with respect to graph structures, the development of a matrix representation and the developed algorithm for converting a graph to a metagraph. Also, the work is valuable for specialists in statistics and data analysis by using the results obtained from generalized graph structures in the problems of modeling and analysis of big data, reducing the complexity of interpreting intermediate and final results by raising the level of abstraction of the object under consideration and describing the structure and functional purpose of hybrid intelligent systems. All of the above topics can be useful to specialists engaged in the direct development of software in these and related application areas. This article is of value as a review of previously obtained results, links to materials on which can be found in the text.

How to Cite:

Blyumin S.L., Prinkov A.S., (2018), DEVELOPMENT OF A MATRIX REPRESENTATION OF GENERALIZED GRAPH STRUCTURES IN PROBLEMS OF BIG DATA DESCRIPTION AND ANALYSIS. Computational Nanotechnology, 2: 9-15.

Reference list:

Voloshin V. Introduction to Graph and Hypergraph Theory. Nova Kroshka Books. UK edition, 2013. 231 p.

Basu A., Blanning R. Metagraphs and Their Applications. NY: Springer, 2007. 172 r.

Anokhin K.V. Kognitom: gipersetevaya model mozga // XVII Vserossiyskaya nauch.-tekhn. konf. Neyroinformatika-2015 . Sb. nauch. tr. CH. 1. M.: MIFI, 2015. S. 14-15.

CHernen kiy V.M., Gapanyuk YU.E., Revunkov G.I., Terekhov V.I., Kaganov YU.T. Metagrafovyy podkhod dlya opisaniya gibridnykh intellektual nykh informatsionnykh sistem // Prikladnaya informatika. T. 12. № 3 (69). M.: Izd-vo Mosk. fin.-prom. un-ta Sinergiya , 2017. S 57-79.

Huang J., Zhang R., Xu Yu J. Scalable Hypergraph Learning and Processing // Data Mining (ICDM), International Conference on. Atlantic City, NJ, USA, 14-17 Nov. 2015.

Zhou D., Huang J., Sch lkopf B. Learning with Hypergraphs: Clustering, Classification and Embedding // Advances in Neural Information Processing Systems. 19, 2007. R. 1601-1608.

Kepner J., Aaltonen P., Bader D. Mathematical foundations of the GraphBLAS // High Performance Extreme Computing Conference. Waltham, MA, USA, 13-15 Sept. 2016.

Prin kov A.S. Grafostrukturnoe remodelirovanie metagrafami slozhnykh sistem na primere moskovskogo metropolitena // Materialy XII mezhdunar. nauch.-prakt. konf. HTCS 2017 , 25-27 oktyabrya 2017 g. V 2 ch. CH. 1. Izd-vo LGTU, 2017. S. 125-129.

Prin kov A.S. Razrabotka programmnogo obespecheniya dlya grafostrukturnogo remodelirovaniya slozhnykh sistem. V 2 ch. CH. 2. // Materialy XII mezhdunar. nauch.-prakt. konf. HTCS 2017 , 25-27 oktyabrya 2017 g. Izd-vo LGTU, 2017. S. 65-69.

Blyumin S.L. Itergipergrafy: rasshirennyy klass grafovykh modeley bol shikh sistem // Trudy konf. Teoriya aktivnykh sistem-2011 (TAS) v ramkakh Mezhdunar. nauch.-prakt. mul tikonf. Upravlenie bol shimi sistemami (UBS-2011). M.: IPU RAN, 2011. S. 11-15.

Blyumin S.L., Prin kov A.S. Grafostrukturnye tendentsii razvitiya IIS: primenenie gipergrafov, metagrafov, itergrafov i ikh matrichnykh predstavleniy // Problemy fundamental noy i prikladnoy informatiki v upravlenii, avtomatizatsii i mekhatronike. Kursk: Izd-vo YUgo-Zap. gos. un-ta ZAO Universitetskaya kniga , 2017. S. 5-13.

Drexl M. On the generalized directed rural postman problem // J. of the Operational Research Society. V. 65, Issue 8. NY: Springer, August 2014. Rp. 1143-1154.

CHernen kiy V.M., Terekhov V.I., Gapanyuk YU.E. Struktura gibridnoy intellektual noy informatsionnoy sistemy na osnove metagrafov // Neyrokomp yutery: razrabotka, primenenie. M.: Radiotekhnika, 2016. C. 3-13.

Blyumin S.L. Orgipergipergrafy: matritsy intsidentnosti i laplasiany // Vestnik LGTU. № 1 (21), 2013. S. 15-27.

Etsuji T., Akira T., Haruhisa T. The worstcase time complexity for generating all maximal cliques and computational experiments // Theoretical Computer Science. V. 363, Issue 1, 2006. Rp. 28-42.

Basu A., Blanning R. Metagraphs and Their Applications. NY: Springer, 2007. 172 r.

Anokhin K.V. Kognitom: gipersetevaya model mozga // XVII Vserossiyskaya nauch.-tekhn. konf. Neyroinformatika-2015 . Sb. nauch. tr. CH. 1. M.: MIFI, 2015. S. 14-15.

CHernen kiy V.M., Gapanyuk YU.E., Revunkov G.I., Terekhov V.I., Kaganov YU.T. Metagrafovyy podkhod dlya opisaniya gibridnykh intellektual nykh informatsionnykh sistem // Prikladnaya informatika. T. 12. № 3 (69). M.: Izd-vo Mosk. fin.-prom. un-ta Sinergiya , 2017. S 57-79.

Huang J., Zhang R., Xu Yu J. Scalable Hypergraph Learning and Processing // Data Mining (ICDM), International Conference on. Atlantic City, NJ, USA, 14-17 Nov. 2015.

Zhou D., Huang J., Sch lkopf B. Learning with Hypergraphs: Clustering, Classification and Embedding // Advances in Neural Information Processing Systems. 19, 2007. R. 1601-1608.

Kepner J., Aaltonen P., Bader D. Mathematical foundations of the GraphBLAS // High Performance Extreme Computing Conference. Waltham, MA, USA, 13-15 Sept. 2016.

Prin kov A.S. Grafostrukturnoe remodelirovanie metagrafami slozhnykh sistem na primere moskovskogo metropolitena // Materialy XII mezhdunar. nauch.-prakt. konf. HTCS 2017 , 25-27 oktyabrya 2017 g. V 2 ch. CH. 1. Izd-vo LGTU, 2017. S. 125-129.

Prin kov A.S. Razrabotka programmnogo obespecheniya dlya grafostrukturnogo remodelirovaniya slozhnykh sistem. V 2 ch. CH. 2. // Materialy XII mezhdunar. nauch.-prakt. konf. HTCS 2017 , 25-27 oktyabrya 2017 g. Izd-vo LGTU, 2017. S. 65-69.

Blyumin S.L. Itergipergrafy: rasshirennyy klass grafovykh modeley bol shikh sistem // Trudy konf. Teoriya aktivnykh sistem-2011 (TAS) v ramkakh Mezhdunar. nauch.-prakt. mul tikonf. Upravlenie bol shimi sistemami (UBS-2011). M.: IPU RAN, 2011. S. 11-15.

Blyumin S.L., Prin kov A.S. Grafostrukturnye tendentsii razvitiya IIS: primenenie gipergrafov, metagrafov, itergrafov i ikh matrichnykh predstavleniy // Problemy fundamental noy i prikladnoy informatiki v upravlenii, avtomatizatsii i mekhatronike. Kursk: Izd-vo YUgo-Zap. gos. un-ta ZAO Universitetskaya kniga , 2017. S. 5-13.

Drexl M. On the generalized directed rural postman problem // J. of the Operational Research Society. V. 65, Issue 8. NY: Springer, August 2014. Rp. 1143-1154.

CHernen kiy V.M., Terekhov V.I., Gapanyuk YU.E. Struktura gibridnoy intellektual noy informatsionnoy sistemy na osnove metagrafov // Neyrokomp yutery: razrabotka, primenenie. M.: Radiotekhnika, 2016. C. 3-13.

Blyumin S.L. Orgipergipergrafy: matritsy intsidentnosti i laplasiany // Vestnik LGTU. № 1 (21), 2013. S. 15-27.

Etsuji T., Akira T., Haruhisa T. The worstcase time complexity for generating all maximal cliques and computational experiments // Theoretical Computer Science. V. 363, Issue 1, 2006. Rp. 28-42.

Keywords:

gradostroitelnaya modeling, matrix representation, hypergraph, metagraf, big data.