Graphs decomposition using modified spectral clustering method

Abstract

Among a large number of tasks on graphs, studies related to the placement of objects with the aim of increasing the information content of complex multi-parameter systems find wide practical application (for example, in transport and computer networks, piping systems, in image processing). Despite years of research, accurate and efficient algorithms cannot be found for placement problems. It is proposed to consider the solution of the allocation problem in the context of decomposition of the initial network into k regions, in each of which a vertex with some centrality property is searched. This article provides an analysis of sources for solving the problem of placement in graphs, as well as methods of decomposition of graph structures. Following the main provisions of the theory of spectral clustering, the disadvantages of the splitting applied criteria Rcut and Ncut are indicated. It is shown that the application of the distance minimization criterion Dcut proposed in this paper allows to obtain high results in the decomposition of the graph. The obtained results are based on the examples of searching for sensor placement vertices in the known ZJ and D-Тown networks of the EPANET hydraulic modeling system.