Simulation Model of Subgraph Search at Semantic Net

This paper’s object of research is the software implementation of the simulation model of isomorphic subgraph search in a semantic net, with the aim of studying the algorithm, its benefits, and improvements over existing approaches. In the model, the semantic net is approximated as a weighted, not oriented graph. The work is composed of two parts. The first one describes the theoretical problems of this field. It contains the overview, classification and comparison of existing algorithms, notations and software products, aimed at the problem of subgraph search. The second part is dedicated to describing the practical implementation of the simulation model and using it to study the properties of the algorithm of isomorphic subgraph search. The algorithm, for which the simulation model is created, is aimed at speeding up the process of subgraph search by using a new intermediate data structure. This structure represents the graph, and is called a topological puff. The puff’s information is enough to define the graph’s topology and the values in its vertices. This paper also contains a description of the algorithm of isomorphic subgraph search using the puff approach, as well as its software implementation. In addition, this study describes the results of the research into the space and time complexity of the algorithm, based on the data collected from the software implementation. This work contains 171 pages. The work uses 3 tables and 21 pictures. During the study, 33 sources were used.