Author Email: plosatik1208@mail.ru
Abstract
Among the many tasks on graphs, studies related to partitioning an initial graph into a predetermined number of connected disjoint components have found wide practical application – graph clustering, for example, is used in computer networks, transport, pattern recognition, and in many other areas. The decomposition methods of graph structures make a significant contribution to the performance of search algorithms, which is especially important in the context of restrictions on computing and time resources. And here we should pay special attention to the class of spectral clustering methods that combine elements of graph theory and linear algebra. In this paper, we consider the basic principles of the theory of spectral clustering, describe the main approach of normalized spectral clustering of graphs. Decomposition of any graph as a structure with inherent topology meets the criteria for optimality in connectedness and balanced subgraphs with a small number of clusters. With an increase in the number of sub-areas above a certain value, the probability of appearance of the disconnected subgraphs in the decomposition structure increases. To solve this problem, the authors propose an algorithm for the priority distribution of nodes based on iterative transfer of nodes of isolated areas to the most priority neighboring subgraphs. It is considered the question of optimal placement of objects in graph models of hydraulic networks by methods based on trial and error algorithms, greedy and spectral clustering.
Introduction
The piping system is a complex structure distributed in space. Its functioning is carried out in the conditions of information incompleteness and on the basis of a probabilistic assessment of its real state [1]. Thus, the management effectiveness of the pipeline system depends on the estimates of certain parameters that affect its functioning. The reliability of these estimates, in turn, depends on the number and location of objects. This paper discusses alternative solutions. The use of greedy algorithm [2] is based on iterative expansion of the initial sub-areas by including vertices adjacent to the node selected as the starting one [3]. Kernigan and Lin [4] proposed a method of phased transformations of sub-areas of the initial partition: a small number of vertices are exchanged at each iteration between subgraphs. The particle pairs move from one sub-area to another, provided that the maximum improvement in the partition quality is achieved [5]. The class of spectral decomposition methods [6–9] assumes a fundamentally different formulation of the optimal partitioning problem and combines elements of graph theory and linear algebra. Fedler [10] demonstrated that the eigenvector provides a solution to the problem of bipartite partitioning of the graph. In [11], the authors use the Fedler’s conclusions in solving the dicot partitioning problem and introduce the normalized cut criterion (NCut). Ng, Jordan, Weis [12] described in the article the spectral clustering algorithm based on the symmetrically normalized discrete Laplace operator.
Conclusion
In this paper, we consider the basic principles of the theory of spectral clustering, describe the main approach of normalized spectral clustering of graphs. To solve the problem of forming the disconnected subgraphs, we proposed an algorithm for the priority distribution of nodes based on iterative transmission of the vertices of isolated areas to the most priority neighboring subgraphs. It is considered the question of optimal placement of objects in graph models of hydraulic networks by methods based on trial and error algorithms, greedy and spectral clustering. It is shown that the application of spectral clustering algorithms to solve this problem makes it possible to obtain a quasi-optimal solution in a short time.
986 total views, no views today