On an Algorithm for Graph Coarsening
Abstract Generated abstract
The paper addresses the problem of reducing large graph models while preserving essential topology and metric information, motivated by operational planning and control systems where specified vertices must be excluded from a network model. It proposes an iterative coarsening algorithm that selects local “bushes” associated with the excluded vertices, repeatedly merges their mappings while applying an arbitrary equivalent metric transformation, and then reinserts the coarsened structures into the original topology. The method is independent of whether the graph is specified by direct or inverse mappings, does not require prior ordering by vertex ordinal function, and in the limiting case can reduce a model to sources and sinks. An implementation for the Ural-11B computer is reported, with a 450-instruction program processing a 4000-vertex graph with 400 exclusions in 3.5 minutes.
Full Text
On an Algorithm for Graph Coarsening
Yu. N. Efimov, V. I. Kizev, V. I. Nevraev, P. A. Sedelnikov
(Presented by the scientific seminar of the UVL)
Continuous technical progress inevitably brings forth a number of new problems and requirements for all branches of science and technology, and gives rise to new scientific directions.
A pressing problem of our time is the problem of controlling large systems with complex interrelationships. The diversity and complexity of the functions inherent in large systems impose specific conditions on the approach to their analysis and synthesis.
In a number of cases, graph theory can be successfully applied to the analysis of large systems; at present it is finding broad application in solving a wide variety of problems.
In some cases it is inconvenient to use graphs of large dimension; therefore the problem arises of transforming (coarsening) a given graph into a graph of smaller dimension that preserves the principal interrelationships and parameters of the original. Known algorithms for such a transformation [1, 2], used in SPU systems, presuppose a preliminary partition of the network model into separate fragments or blocks. Under the conditions of operation of a system for operational planning and control of an enterprise with discrete production, the network model is compiled according to general or node specifications. In this case, because of differences in design and technological documentation, part of the complete product nomenclature may turn out to be uncontrollable and must be excluded from the model being analyzed. In this case the problem arises of coarsening the graph according to a given list of vertices to be excluded. It is then necessary to carry out an equivalent transformation of its methodology.
In the present work an algorithm is proposed for solving this problem. Let the original graph be given by the set of vertices \(I\) and their direct or inverse mapping \(\Gamma_i\).
\[ G = (I, \Gamma). \]
Also given is a subset of vertices subject to exclusion, \(I' = \{i'\}\), of the set \(I\).
We shall assume that the metric \(r\) of the graph is assigned to arcs. In the case when the metric \(r\) is assigned to vertices, it may be assumed without loss of generality that it is assigned to all arcs entering the given vertex. However, in what follows, for simplicity of exposition, the indexing of the metric will be carried out by the vertices of the graph \(i\). The coarsening of the graph is carried out—
is carried out by means of a series of successive transformations during the examination of the original graph and its fragments.
During the first examination of the graph topology, “bushes” are selected from it: vertices \(i\) and their mappings \(\Gamma_i\), with the metric \(r_i\) belonging to them, for which \(i \in I'\), and zeros are entered in their place in the topology. As a result, “bushes” will be singled out, represented in the following form:
\[ (i', \Gamma_{i'}, r_{i'}). \]
After this, the “bushes” are coarsened. For this purpose, two fields are allocated in the computer memory. The selected “bushes” are located in the first field. The coarsening process begins with an examination of the first field and the writing of the coarsening result into the second field; then the second field is examined and the coarsening result is written into the first field, and so on.
During the first examination of the “bushes,” such vertices \(i'\) are selected that enter into the mapping \(\Gamma_{i'_k}\) of some vertex \(i'_k\). The elements of the mapping of the vertices found, \(\Gamma_{i'}\), are included in the mapping of the vertex \(i_k\), while from the mapping of this vertex those of its elements are discarded that form intersections with the remaining vertices. Thus, after the first examination the “bush” will be written into the second field in the following form:
\[ i'_k\left(\Gamma_{i'_k}' \cup \Gamma_{i'} \setminus \underset{i'\ne i'_k}{\Gamma_{i'_k}' \cap i'}\right)/ \left(\underset{i'\ne i'_k}{\Gamma_{i'_k}' \cap i'}\right) \ne \varnothing . \]
At the same time, an equivalent transformation of the metric is performed:
\[ (r_{i'_k} R r_{i'})/ \left(\underset{i'\ne i'_k}{\Gamma_{i'_k}' \cap i'}\right) \ne \varnothing, \]
where \(R\) is the symbol of an arbitrary operation.
Analogous operations are performed on all vertices of the “bushes.” Then the first field is cleared, and the procedure described above is performed on the “bushes” of the second field. The process terminates when
\[ \underset{i'\ne i'_k}{\Gamma_{i'_k}' \cap i'} = \varnothing . \]
In the worst case, \(\varphi_{\max}(i) + 2\) examinations of the “bushes” are required, where \(\varphi(i)\) is the ordinal function of the graph vertices [3].
Upon completion of the process of coarsening the “bushes,” they are inserted into the original topology in place of the mappings of the excluded vertices, after which the topology “bushes” will have the form
\[ i_k\left(\Gamma_{i_k} \cup \Gamma_{i'} \setminus \underset{i'\ne i_k}{\Gamma_{i_k} \cap i'}\right)/ \left(\underset{i'\ne i_k}{\Gamma_{i_k} \cap i'}\right) \ne \varnothing . \]
At the same time, the metric is also transformed:
\[ (r_{i_k} R r_{i'})/ \left(\underset{i'\ne i_k}{\Gamma_{i_k} \cap i'}\right) \ne \varnothing . \]
Thus, as a result of the operation of the algorithm, the topology of the graph is coarsened with an equivalent transformation of the metric. In the limiting case, the algorithm considered makes it possible, in the original graph, to exclude all vertices except sources and sinks, which can be used in obtaining the most general model of the manufacture of a product.
The algorithm is invariant with respect to the method of specifying the initial graph, i.e., the graph may be given in the form
\[ G=(I,\Gamma_i)\quad \text{or}\quad G=(I,\Gamma_i^{-1}). \]
The proposed algorithm does not require preliminary ordering of the initial graph in increasing order of the ordinal function of its vertices.
On the basis of the algorithm described above, a program was written for the Ural-11B computer. The program consists of a number of sequentially operating blocks.
Block 1 selects “bushes” from the initial topology of the graph according to the list of vertices to be excluded. Block 2 carries out the coarsening of the bushes with transformation of the metric. Block 3 composes the result of the coarsening of the “bushes” and the initial topology of the graph.
The program contains 450 instructions. The running time of the program for a graph with 4000 vertices, complexity coefficient 5, and number of vertices subject to exclusion equal to 400 was 3.5 min.
REFERENCES
- S. I. Zukhovitskii, I. A. Radchik. Mathematical Methods of Network Planning. Moscow, Nauka Publishing House, 1965.
- Yu. N. Efimov. Time analysis of large network schedules of block structure. Izv. TPI, vol. 203. Tomsk State University Publishing House (in press).
- C. Berge. The Theory of Graphs and Its Applications. Moscow, Foreign Literature Publishing House, 1962.