COMPACT PARTITIONS ON LARGE DIMENSION TOPOLOGICAL GRAPHS
Relevance. Distributed systems containing hundreds and thousands of objects are usually built in the form of hierarchical structures. In these structures, lower-level objects are combined into subsets for connection to the corresponding centers. The existing algorithms are not capable of successfull...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Tomsk Polytechnic University
2023-06-01
|
| Series: | Известия Томского политехнического университета: Промышленная кибернетика |
| Subjects: | |
| Online Access: | https://indcyb.ru/journal/article/view/26/21 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849433466495565824 |
|---|---|
| author | Alexander V. Pogrebnoy Andrey V. Pogrebnoy |
| author_facet | Alexander V. Pogrebnoy Andrey V. Pogrebnoy |
| author_sort | Alexander V. Pogrebnoy |
| collection | DOAJ |
| description | Relevance. Distributed systems containing hundreds and thousands of objects are usually built in the form of hierarchical structures. In these structures, lower-level objects are combined into subsets for connection to the corresponding centers. The existing algorithms are not capable of successfully solving structuring problems on sets of this dimension. Therefore, new algorithms are needed that are suitable for solving structuring problems on sets containing thousands of objects. Aim. To develop an algorithm for generating a compact partition on high-dimensional sets containing up to a thousand objects located in a given territory. Methods. Applied graph theory, linear programming methods, construction and analysis of the effectiveness of algorithms, the theory of compact partitions, compact sets of objects and their clusters. Results. It is proposed to represent the territorial location of many objects of a distributed system in the form of a topological graph. The paper introduces the concept of an active search zone for the nearest vertices to increase the efficiency of the algorithm for generating compact sets and identifying clusters. This makes it possible to replace the matrix of distances between graph vertices with a list of vertex incidentors generated based on the active search zone. The authors developed the algorithm for approximate solution to the problem of compact partitioning a set of objects of a topological graph, represented by a list of vertex incidentors, into a given number of subsets. For each object, the algorithm recursively increases the power of compact sets, analyzes the resulting clusters and, under certain conditions, proceeds to the formation of a compact partition. The problem of forming subsets of a compact partition based on clusters is formed as a linear programming problem of transport type. The algorithm presentation is accompanied by an example. |
| format | Article |
| id | doaj-art-0a37a74b8bb04a039b3f01503d235933 |
| institution | Kabale University |
| issn | 2949-5407 |
| language | English |
| publishDate | 2023-06-01 |
| publisher | Tomsk Polytechnic University |
| record_format | Article |
| series | Известия Томского политехнического университета: Промышленная кибернетика |
| spelling | doaj-art-0a37a74b8bb04a039b3f01503d2359332025-08-20T03:27:01ZengTomsk Polytechnic UniversityИзвестия Томского политехнического университета: Промышленная кибернетика2949-54072023-06-0112394510.18799/29495407/2023/2/26COMPACT PARTITIONS ON LARGE DIMENSION TOPOLOGICAL GRAPHSAlexander V. Pogrebnoy0Andrey V. Pogrebnoy1National Research Tomsk Polytechnic University, RussiaLimited Liability Company "Drom", RussiaRelevance. Distributed systems containing hundreds and thousands of objects are usually built in the form of hierarchical structures. In these structures, lower-level objects are combined into subsets for connection to the corresponding centers. The existing algorithms are not capable of successfully solving structuring problems on sets of this dimension. Therefore, new algorithms are needed that are suitable for solving structuring problems on sets containing thousands of objects. Aim. To develop an algorithm for generating a compact partition on high-dimensional sets containing up to a thousand objects located in a given territory. Methods. Applied graph theory, linear programming methods, construction and analysis of the effectiveness of algorithms, the theory of compact partitions, compact sets of objects and their clusters. Results. It is proposed to represent the territorial location of many objects of a distributed system in the form of a topological graph. The paper introduces the concept of an active search zone for the nearest vertices to increase the efficiency of the algorithm for generating compact sets and identifying clusters. This makes it possible to replace the matrix of distances between graph vertices with a list of vertex incidentors generated based on the active search zone. The authors developed the algorithm for approximate solution to the problem of compact partitioning a set of objects of a topological graph, represented by a list of vertex incidentors, into a given number of subsets. For each object, the algorithm recursively increases the power of compact sets, analyzes the resulting clusters and, under certain conditions, proceeds to the formation of a compact partition. The problem of forming subsets of a compact partition based on clusters is formed as a linear programming problem of transport type. The algorithm presentation is accompanied by an example.https://indcyb.ru/journal/article/view/26/21compact partitioncompact setcluster of objectscluster densitytopological graph |
| spellingShingle | Alexander V. Pogrebnoy Andrey V. Pogrebnoy COMPACT PARTITIONS ON LARGE DIMENSION TOPOLOGICAL GRAPHS Известия Томского политехнического университета: Промышленная кибернетика compact partition compact set cluster of objects cluster density topological graph |
| title | COMPACT PARTITIONS ON LARGE DIMENSION TOPOLOGICAL GRAPHS |
| title_full | COMPACT PARTITIONS ON LARGE DIMENSION TOPOLOGICAL GRAPHS |
| title_fullStr | COMPACT PARTITIONS ON LARGE DIMENSION TOPOLOGICAL GRAPHS |
| title_full_unstemmed | COMPACT PARTITIONS ON LARGE DIMENSION TOPOLOGICAL GRAPHS |
| title_short | COMPACT PARTITIONS ON LARGE DIMENSION TOPOLOGICAL GRAPHS |
| title_sort | compact partitions on large dimension topological graphs |
| topic | compact partition compact set cluster of objects cluster density topological graph |
| url | https://indcyb.ru/journal/article/view/26/21 |
| work_keys_str_mv | AT alexandervpogrebnoy compactpartitionsonlargedimensiontopologicalgraphs AT andreyvpogrebnoy compactpartitionsonlargedimensiontopologicalgraphs |