Method of combinatorial topology or a simplicial complex...

Combinatorial topology or simplicial complex method

This method, developed to analyze the connectivity of components in systems, can also be used as a method for organizing complex examinations. Topological studies of complex systems based on the study of their structural properties were started in the 1960s and 1970s. The mathematical foundations of the method were laid down K. Drucker (C. Droucer ) and were developed in the works of the British physicist P. Atkin, (R. Atkin), who developed the first simplicial analysis tool, called q-analysis. These studies served as the beginning of a study of the complexity of system structures by the method of q-analysis or polyhedral dynamics. The method of combinatorial topology is most fully developed by J. Caste (J. Casti) [40].

The q-connection analysis technique allows us to judge the connectivity of the system more deeply than traditional studies of the connectivity of a graph, and to order the estimated components in the order of increasing or decreasing connectivity.

In order to visually examine the connectivity of the structure, it is necessary to consider the concept of a complex. A simplicial complex is a natural mathematical generalization of the concept of a planar graph reflecting the multidimensional nature of a binary relation. Since the simplicial complex is essentially none other than a family of simplexes connected by means of common faces, the dimension of a face common to two simplexes could serve as a natural characteristic of the connection. If we are interested in the complex as a whole, then it is more appropriate to use the concept of "chain of connection", reflecting the fact that two simplexes may not have a common face, but can be connected by a sequence of intermediate simplexes.

Taking into account dimensionality, the notion of the & q; q-connection can be formulated as follows. The concept of communication chains - q-connectedness - is formulated as follows: the two simplexes σr and σp (r,

p are the geometric dimensions of q corresponding simplexes) of the complex K are connected by a q-connection chain if there exists a sequence simplexes σαq, q = 1, 2, ..., n in K such that - the face - face and have a common face dimension for ; (the lower index of the simplex corresponds to its geometric dimension, that is, dim ).

The problem of studying the connection structure of the complex K reduces to the consideration of classes of q-equivalence. For each dimension value you can define the number of different equivalence classes . This operation is called the q-analysis of the complex K, and the vector - the first structural vector of the complex.

Symbols are connected through a set of relations A, the so-called incidence matrix (or incidence matrix):

Thus, the ratio between two different sets F and W is a subset of the Cartesian product . If the pair , then it is said that is in relation to to. This ratio is represented as an incidence matrix :



A simplicial complex consists of the following four simplexes:

graphically on a plane can be represented by a simplex of dimension

Algorithm of q-contamination analysis.

1. Counting the units in each t-th line and calculating the dimension of simplexes of the complex :


2. Counting the units in each j-th column and calculating the dimensions of the simplices of the complex :


3. Matrix transformation.

Converting the matrix to - ordering i-x lines from top to bottom by rule:


Converting the matrix to - arranging the jx columns from left to right on rule:


4. Construction of simplicial complexes.

Construction of the complex ; the sequence of simplices is ordered by the rule (2.23) of decreasing their dimension. Construction of the complex ; the sequence of simplexes is ordered by the rule (2.24) of decreasing their dimension.

5. Definition of the matrix of the first structural vector complex . For each dimension the number of simplexes in each mass of equivalence is set by the rule: if at least one vertex of the simplex is not belongs to the previous simplex of greater dimension, then this is a separate mass (that is, if at least one unit of the i-th line does not enter the previous lines then corresponding to this line simplex forms a separate equivalence mass).

6. Definition of the matrix of the first structural vector complex . For each dimension the number of simplexes in each equivalence class is set by the rule: if at least one vertex of the simplex is not it is a separate class (that is, if at least one unit of the j-column does not enter the previous columns then the simplex corresponding to this column a separate equivalence class).

Despite the fact that q-analysis proves to be quite effective in studying the global connectivity of a structure, nevertheless it does not provide the necessary information about how each individual simplex is included in the entire complex. Since the individual properties of simplexes can be very significant in the problem under consideration, it is important to be able to determine the degree of integration of each individual simplex in the structure of the entire complex. To this end, the concept of "eccentricity" is introduced.

The eccentricity of the simplex σ is given by the formula


where - the dimension of the simplex - the largest value of q, for where σ becomes connected with some other simplex of K.

Thus, based on binary estimates of the elements of the incidence matrix (which experts can do more easily than give quantitative estimates), we can obtain more differentiated eccentricity estimates that allow us to order the components by the connectivity criterion.

Currently, a modeling direction is developing, combining the methods of combinatorial topology with the cognitive approach [28], according to which the incidence matrix is ​​formed on the basis of the cognitive graph.

thematic pictures

Ошибка в функции вывода объектов.