Methods of decomposition theory and graph labeling in the study of social network structure⋆ Leonid Hulianytskyi1, , Marina Semeniuta2 and Serhii Yakymenko3, 1 V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Academician Glushkov Avenue, 40, Kyiv, 03187, Ukraine 2 Central Ukrainian National Technical University (CUNTU), Prospekt Universytetskyi,8, Kropyvnytskyi, 25006, Ukraine 3 Central Ukrainian National Technical University (CUNTU), Prospekt Universytetskyi,8, Kropyvnytskyi, 25006, Ukraine Abstract The article presents a review and analysis of modern approaches to community detection in social networks modeled as undirected graphs. Based on graph theory methods, we propose a new mathematical framework for identifying cliques and k-cliques in the network, aimed at determining indicators that provide useful information about the quality of connections in the social network, its vulnerabilities, and optimizing the information transfer process among community agents in the network. The results of the study are intended for the implementation of the developed methods into existing algorithms for social network analysis. Keywords social network, community, graph, social graph, clique, π‘˜-clique, graph labeling, decomposition of a graph, semi-rotated T-factorization 1. Introduction While performing analysis of large amount of data, there is a need for their identification and grouping according to certain characteristics. Social networks can be considered as one of the examples of such a set of data with connections between them. The term "social network" was first proposed by D. Barnes in 1954. A social network is understood as a system consisting of social objects or agents (people or different groups of people, such as organizations and families) between which certain relationships exist. Online social networks are very popular in modern society. Their analysis is necessary for solving various tasks related to marketing, bot detection, information security, and similar areas. here are various methods for studying the structure and characteristics of networks [1, 2, 3, 4, 5]. One of the structural features of a social network is its property of heterogeneity. In this regard, the task arises of identifying groups within it that are densely interconnected but have weak ties with other objects in the network. based on its segmentation into subnetworks, most often in the form of clique structures. Another important aspect is the study of the hierarchical organization of communities within the network. Hierarchical properties of structures can be represented using algebraic set theory, describing complex networks in terms of lattices [3, 4]. Mathematical formalization of the mentioned tasks often involves the use of graph theory methods aimed at developing software-algorithmic tools. This Information Technology and Implementation (IT&I-2024), November 20-21, 2024, Kyiv, Ukraine *Corresponding author. These authors contributed equally. leonhul.icyb@gmail.com (L. Hulianytskyi); marinafsemenyuta@gmail.com (M. Semeniuta); yasm@i.ua (S. Yakymenko) 0000-0002-1379-4132 (L. Hulianytskyi); 0000-0003-4639-0545 (M. Semeniuta); 0000-0002-5759-9603 (S. Yakymenko) Β© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 490 CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings facilitates the acceleration of data analysis in the social network and the interactions among its objects. This paper presents the results of applying graph theory methods to determine indicators that provide useful information about the quality of connections in a social network and its vulnerability. A social system that contains maximal communities is more resilient which is why we considered the problem of finding cliques, supergraphs, and subgraphs in the social graph. This problem belongs to the NP-complete problems of graph theory [7]. Research in this area has been ongoing for many years, and significant progress has been made. A review of algorithms for finding the maximal clique in graphs can be found in [8]. We applied graph labeling to identify local minimal networks that have a tree structure. The first publications on the graph labeling appeared in the mid-60s of the last century. A. Rosa is considered to be the founder of the theory of labelings, who in 1967 proposed four types of labelings as a tool for decomposing a complete graph into isomorphic trees. In particular, with the help of a graceful labeling, he proved H. Ringel's hypothesis about the existence of a cyclic decomposition of a complete graph 𝐾2𝑛+1 in 2𝑛 + 1 subgraphs, each of which is isomorphic to a size of the tree 𝑛. The necessary conditions for the decomposition of the complete graph 𝐾𝑛 into spanning trees isomorphic to tree 𝑇are: 1) the evenness of the number 𝑛; 2) the maximum degree of 𝑇 must not exceed 𝑛/2. In general, the problem of decomposing a complete graph into spanning trees is NP-complete, as it is related to their enumeration. Therefore, initially, trees of small orders were considered, and later methods for decomposing the graph 𝐾𝑛 into certain classes of trees, such as chains, caterpillars, and symmetric trees, emerged [9]. A comprehensive review of publications dedicated to graph labeling is presented by D. Gallian in the electronic journal "A Dynamic Survey of Graph Labeling," which is reissued annually and updated with information about new research results [10]. 2. Modern approaches to community detection in social networks In the modern world, social networks play a critical role in facilitating interactions between people. Analyzing them helps reveal hidden structures, interaction dynamics, and key characteristics of participants. To explore these aspects, this section provides a review and analysis of studies describing the main methods for detecting communities in social networks modeled as undirected graphs. There is a group of methods aimed at identifying communities in social networks. The Girvan- Newman method is one of the most popular methods among them. It is based on the concept of edge centrality. This method involves finding all simple paths between each pair of vertices in the graph and counting the frequency of each edge's occurrence on those paths, thus determining edge centrality. Edges with high centrality are critical to the structure of the graph and are removed until individual communities are discovered. A new algorithm, described in [11], combines the Girvan- Newman method with random walks, improving the process of partitioning a graph into communities. A modification of the Girvan-Newman method that optimizes edge removal to increase both speed and accuracy of community detection is presented in [12, 13]. Research [14] analyzes changes in the structure of social networks and their impact on well-known community detection algorithms, proposing an approach that takes into account the dynamic evolution of networks. Louvain's method consists in finding a partition that maximizes the modularity of the network. In the context of this method, modularity is a metric for evaluating community detection in graphs, measuring the extent to which a graph can be divided into subgraphs with dense connections. A community detection algorithm that combines Louvain's method with modified random walks is described in [15]. C. Xia and Y. Yang proposed an improved version of Louvain's method [16], while J. Zhou and X. Wang adapted Louvain's method for dynamic social networks, enabling better tracking of changes within communities [17]. A review discussing various approaches to applying Louvain's method for community detection in social networks and other types of graphs is presented in [18]. 491 Community detection in social graphs helps identify groups of users that actively interact with each other. One of the most well-known algorithms for finding all maximal cliques in undirected graphs is the Bron-Kerbosch algorithm, which operates recursively by selecting three sets: the current set of cliques, the candidate set, and the set of excluded vertices. In [19], M. Khoshraftar and M. Zarei introduced a hybrid genetic algorithm that integrates genetic methods with traditional approaches. H. Zhang, J.Wang and Y. Liu proposed a new clique detection algorithm based on vertex centrality, accounting for the significance of nodes [20]. In [21], the authors developed a fast and efficient method for detecting maximal cliques in large social networks, utilizing graph partitioning and parallelism to accelerate computations. An improved algorithm for community detection through clique expansion, which reveals robust structures with high accuracy, is described in [22]. S. Tawakoli and R. Farahani introduced a new method for finding k-cliques based on random walks [23]. A review of the latest advancements in community detection using deep learning techniques is provided in [24]. An important set of tools for social network analysis are graph decomposition methods into trees. These are used to represent and manage the structures of social networks [24, 25]. Although the study in [25] dates back to 1988, its contribution to the field of graph decompositions into trees remains significant for modern tasks, taking into account social network analysis. The literature review showed that there are many diverse approaches to community detection in social networks. Researchers seek to develop methods that can quickly process graphs with large order and size, and improve existing algorithms to reduce execution time, decrease memory consumption, or enhance accuracy. To do this, they adapt well-known algorithms by adding new techniques or modifying approaches to make them work better in real-world conditions. Thus, most research is focused on making community detection algorithms as fast and efficient as possible, which is crucial for working with large and complex graphs typical of social networks. However, such a focus can sometimes distract from a deeper analysis of the structure of communities and the connections between its objects. 3. Formulation of the problem Graph 𝐺 = (𝑉, 𝐸), which is often called social, will serve as a mathematical model of social network. Each person from the network will be matched with a vertex of the graph, and an edge between two vertices will represent the connection between corresponding people. We consider only symmetrical connections, thus, the direction of the connection between two objects of the structure is not important. Therefore, 𝐺 = (𝑉, 𝐸) is a finite undirected graph without loops and multiple edges with a set of vertices 𝑉 and a set of edges 𝐸. Under the order of the graph 𝐺 we understand the number of elements of a set 𝑉, and under its size is the number of elements of the set 𝐸. Groups of closely connected people are typically modeled by subgraphs of the given graph, such as a clique, π‘˜-clique (or π‘˜-distance clique), π‘˜-clan, π‘˜-club. A graph 𝐺′ is called a subgraph of the graph 𝐺, if 𝑉( 𝐺′)𝑉(𝐺) and 𝐸( 𝐺′)𝐸(𝐺). If 𝑉( 𝐺′) = 𝑉(𝐺), then 𝐺′ is a spanning subgraph or a factor of the graph 𝐺. For any subset 𝑆𝑉(𝐺) of the vertex set of the graph 𝐺 = (𝑉, 𝐸), the maximal subgraph of graph 𝐺 with vertex set 𝑆 is called the induced subgraph and is denoted 𝐺(𝑆). Every two vertices in 𝑆 are adjacent in 𝐺(𝑆) if and only if they are adjacent in 𝐺. A complete graph 𝐾𝑛 is a graph of order 𝑛 in which there is an edge between each pair of vertices. A subset π΅βŠ†π‘‰(𝐺) is called a clique if the subgraph 𝐺(𝐡) induced by it is complete. The graph 𝐺(𝐡) is also referred to as a clique. A clique of a graph that is not contained in a larger clique called a maximal clique. A walk in a graph is formed by a sequence of alternating vertices 𝑣1 , … , 𝑣𝑛 along with edges 𝑣𝑖 𝑣𝑖+1 ∈ 𝐸, where 𝑖 𝑛 1. It starts and ends at a vertex. In a connected graph, there exists a walk between any pair of vertices. The number of edges in a walk is called its length. This walk is called a path (or a (𝑣1 βˆ’ 𝑣𝑛 )-path), if all its edges are distinct. If all 𝑛 the vertices of a path are distinct, 492 it is commonly referred to as a simple path and denoted by 𝑃𝑛 , thus 𝑉(𝑃𝑛 ) = {π‘₯1 , π‘₯2 , … π‘₯𝑛 } and 𝐸(𝑃𝑛 ) = {(π‘₯𝑖 , π‘₯𝑖+1 ): 𝑖 = 1, 2, … , 𝑛 βˆ’ 1}. The distance between two vertices in a connected graph is defined as the length of the shortest simple path connecting them. The diameter of a graph is the largest distance between any two vertices. More detailed terminology from graph theory, used in this article, is presented in [26, 27]. Let 𝐺 be a connected graph with a diameter greater than π‘˜. A π‘˜-clique of the graph 𝐺 is its subgraph 𝐻 = (𝑉 β€² , 𝐸′), induced by the set of vertices 𝑉′𝑉, the distance between which in 𝐺 less than or equal to π‘˜. Thus, for a social network π‘˜-clique describes a group of people in which two individuals may be connected through acquaintances from this group whom they do not know. The following theorem makes it possible to calculate the number of routes of a certain length between each pair of vertices. Theorem 1 [27]. Let 𝐴 = 𝐴(𝐺) be the adjacency matrix of a simple graph 𝐺 = (𝑉, 𝐸) and (π‘˜) π΄π‘˜ = (π‘Žπ‘–π‘— ), where π‘˜ β‰₯ 1, π‘˜ ∈ 𝑁. Then the number of path π‘π‘˜ (𝑖, 𝑗) of length π‘˜, starting at the vertex (π‘˜) (π‘˜) π‘₯𝑖 ∈ 𝑉 and ending at the vertex π‘₯𝑗 ∈ 𝑉, is equal to π‘Žπ‘–π‘— , i.e π‘π‘˜ (𝑖, 𝑗) = π‘Žπ‘–π‘— . If a connected graph 𝐺 has 𝑛 vertices, then its 𝑛 eigenvalues 1 , 2 , … , 𝑛 are real and 1 β‰₯ 2 β‰₯ β‹― β‰₯ 𝑛 . According to the Frobenius-Perron theorem 1 > 0 and algebraic multiple 1 equals one. Recall that by the index 𝐺 of graph 𝐺 we mean its maximum eigenvalue. Thus, 𝐺 = 1 . Let us give some concepts from the theory of decomposition and graph labeling. The (𝐺, 𝑄)- decomposition of a graph 𝐺 into the graphs from the set 𝑄 = {𝑄1 , 𝑄2 , … , 𝑄𝑛 } we refers to the partitioning of the edge set 𝐺 into such subsets that the subgraphs generated by them (the components of decomposition) do not intersect in terms of edges and each of them is isomorphic to one of the elements of the set 𝑄. The total number of components in the decomposition is called the size (or rank) of the decomposition. If all components of the decomposition are isomorphic to a tree 𝑇 and 𝐺 is a complete graph 𝐾𝑛 , then we will get (𝐾𝑛 , 𝑇)-decomposition, which is called 𝑇- factorization 𝐾𝑛 where 𝑇 is spanning subgraph of 𝐾𝑛 . The first labelings were proposed by A. Rosa in his work "On Certain Valuations of the Vertices of Graphs" in 1967 as a tool for decomposing a complete graph into isomorphic subgraphs. Significant results have been achieved using these labelings in solving problems related to the existence, construction, and enumeration of graph decompositions. A labeling of the graph 𝐺 = (𝑉, 𝐸) of order 𝑝 and size π‘ž is injective mapping 𝑓 from the set 𝑉 into the set of numbers 𝑆 = {0, 1, 2, … , 2π‘ž}. The length 𝑑(π‘₯𝑖 , π‘₯𝑗 ) of the edge (π‘₯𝑖 , π‘₯𝑗 ), where 𝑖 β‰  𝑗, 𝑖, 𝑗 ∈ { 1, 2, … , 𝑝}, is defined as 𝑑(𝑖, 𝑗) = min(|𝑓(π‘₯𝑖 )βˆ’π‘“(π‘₯𝑗 )|, 2π‘ž + 1βˆ’οΌπ‘“(π‘₯𝑖 )βˆ’π‘“(π‘₯𝑗 )|). If the set of all lengths of the π‘ž of edges consists of numbers 1, 2, … , π‘ž and 𝑆{0, 1, 2, … , 2π‘ž}, then 𝑓 is 𝜌-labeling, if 𝑆{0, 1, 2, … , π‘ž}, then 𝑓 is called graceful labeling. Every graceful labeling is also a graph with 𝜌- labeling. In theorem 2 necessary and sufficient conditions for the existence of a cyclic decomposition of a graph into symmetric subgraphs are presented. 2 [9]. Let 𝐺 is a symmetric graph of order 2π‘ž βˆ’ 1. Then cyclic (𝐾2π‘ž , 𝐺)-decomposition exists if and only if the graph 𝐺 allows 𝜌-labeling. A tree is called symmetric if there is an automorphism πœ‘ and a edge π‘₯𝑦 so that πœ‘(π‘₯) = 𝑦 and πœ‘(𝑦) = π‘₯. If a tree 𝑇 of order π‘ž has a graceful labeling, then there is a cyclic (𝐾2π‘žβˆ’1 , 𝑇)-decomposition. Let's consider the following problem: based on data from a social network, perform a search for the maximum k-cliques and cliques in the graph, which serves as a mathematical model of this network, and construct optimal, stable, and redundancy-free connections between agents within the clique. The resulting mathematical framework can be integrated into existing clustering algorithms and adapted for tasks related to social network analysis. 493 4. Detection of cliques and trees in a social network Let 𝐺 = (𝑉, 𝐸) be the graph of order 𝑛 with the adjacency matrix 𝐴. Consider a graph 𝐺(π‘˜) = (𝑉, 𝐸(π‘˜)) in which any two vertices 𝑒 and 𝑣 are adjacent only if 𝑑𝐺 (𝑒, 𝑣) ≀ π‘˜, where 𝑉 = 𝑉(𝐺), 𝑑𝐺 (𝑒, 𝑣) is the distance between vertices 𝑒 and 𝑣 of the graph 𝐺. (π‘˜) According to the theorem 1, every matrix element π΄π‘˜ = (π‘Žπ‘–π‘— ) is equal to the number of length routes π‘˜ between the corresponding vertices of the graph. Let us set the matrix 𝐡 = (𝑏𝑖𝑗 ) as follows: β€’ find the matrix π΄βˆ— (𝐺(π‘˜)) = 𝐴 + 𝐴2 + 𝐴3 + β‹― + π΄π‘˜ , (1) βˆ— where π΄βˆ— = (π‘Žπ‘–π‘— ), 𝑖, 𝑗 = 1, 2, … , 𝑛; β€’ βˆ— π‘Žπ‘–π‘— β‰  0 and 𝑖 β‰  𝑗 then put 𝑏𝑖𝑗 = 1, otherwise 𝑏𝑖𝑗 = 0; β€’ b) if 𝑖 = 𝑗, then put π‘π‘–π‘–βˆ— = 0. Matrix 𝐡 = (𝑏𝑖𝑗 ), where 𝑖, 𝑗 = 1, 2, … , 𝑛 has the order 𝑛 Γ— 𝑛. As a result we get a matrix 𝐡 = (𝑏𝑖𝑗 ). Theorem 3. Let 𝐴 is adjacency matrix of the graph 𝐺 = (𝑉, 𝐸), matrix 𝐡 = (𝑏𝑖𝑗 ), where 𝑖, 𝑗 = 1, 2, … , 𝑛 is the adjacency matrix of the graph 𝐺(π‘˜) for any π‘˜ ∈ 𝑁. Proof. For π‘˜ = 1 the statement of Theorem 3 is true. If π‘˜ = 2, then the elements of the matrix 2 𝐴 are numbers equal to the number of routes of the length 2 in the graph 𝐺 that begin at the vertice π‘₯𝑖 ∈ 𝑉(𝐺) and end at the vertice π‘₯𝑗 ∈ 𝑉(𝐺). Elements of the matrix π΄βˆ— (𝐺(2)) = 𝐴 + 𝐴2 according βˆ— (2) βˆ— to theorem 1 and formula (1), will be in the form π‘Žπ‘–π‘— = π‘Žπ‘–π‘— + π‘Žπ‘–π‘— . Thus, π‘Žπ‘–π‘— β‰  0 with 𝑖 β‰  𝑗, if (π‘₯𝑖 , π‘₯𝑗 ) ∈ 𝐸(𝐺) or/and distance between the vertices π‘₯𝑖 and π‘₯𝑗 equal 2. Then 𝑏𝑖𝑗 = 1, if vertices π‘₯𝑖 and π‘₯𝑗 are adjacent to 𝐺(2). Thus, 𝐡 = 𝐡(𝐺(2)) is an adjacent matrix of the graph 𝐺(2). By continuing such steps, we can conclude, then 𝐡 = 𝐡(𝐺(π‘˜)) is an adjacency matrix of the graph 𝐺(π‘˜) for any π‘˜ ∈ 𝑁. ∎ According to the theorem 3, π‘˜-clique 𝐻 of the graph 𝐺 is the set of vertices that generate a clique in 𝐺(π‘˜). There can be several cliques, we will consider only the maximum. Under the maximum π‘˜- clique we understand π‘˜-clique, which has the highest order. The task of constructing a maximum π‘˜- clique of a graph 𝐺 is reduced to the task of constructing the maximum clique of a graph 𝐺(π‘˜). Remind you that a submatrix of any matrix is a rectangular array located in the selected rows and columns of the matrix [14]. Consequence 1. Let 𝐺 be a graph and there exists such a square matrix 𝑀 of order π‘˜ for which the following conditions are met: β€’ 𝑀 is a submatrix of the matrix 𝐴(𝐺); β€’ each element of the matrix π‘€π‘˜ equals to the number of routes of length π‘˜ between the corresponding vertices of a graph 𝐺; β€’ in the graph 𝐺 there are no vertices except those included in the matrix 𝑀, between which the walk has a length π‘˜. Then 𝑀 generates maximum π‘˜-clique in 𝐺. Consequence 2. If the graph 𝐻 of order 𝑛 is π‘˜-clique of the graph 𝐺, then 𝐡(𝐻(π‘˜)) is an adjacency clique matrix of order 𝑛 of the graph 𝐺(π‘˜). The proof of consequences 1 and 2 follow directly from theorem 3. 494 It follows from Consequence 2 that every is maximal π‘˜-clique of the graph 𝐺 generates the maximum clique of the graph 𝐺(π‘˜). When studying a social graph 𝐺 and its clusters, it is important to have an idea of how sparsed is this graph, as well as its subgraphs. The possibility of expanding it, introducing new agents and establishing their connections with other agents. This can be found out using some spectral characteristics of the graph. For example, the dynamic average 𝑑(𝐺) = lim π‘šβˆšπ‘π‘š , where π‘π‘š is a π‘šβ†’βˆž number of walk of length π‘š in 𝐺 gives an idea of the graph density [28]. According to the Tsvetkovich's theorem [27] we get 𝑑(𝐺) = 1 at same time βˆšβˆ†β‰€ 1 ≀ βˆ†, where 𝐺 is an index of 𝐺, βˆ† is a maximum degree of 𝐺. To illustrate the obtained results, consider a section of a social network, the mathematical model of which is a graph 𝐺 = (𝑉, 𝐸) of order 7 and diameter 3 (fig.1). Let 𝐴 is its adjacency matrix. In 𝐺 there are two maximum 2- cliques, one of them is generated by vertices from the set {1, 2, 3,4, 7}, and the second is from the set {3, 4, 5, 6, 7}. 1 3 4 5 2 7 6 Figure 1: Graph 𝐺 = (𝑉, 𝐸), that serves as a model of a social network Let's find the adjacency matrix 𝐡 of the graph 𝐺(2) = (𝑉, 𝐸(2)), according to the method described above: 2 2 2 1 0 0 1 0 1 1 1 0 0 1 2 2 2 1 0 0 1 1 0 1 1 0 0 1 2 2 4 1 1 2 1 1 1 0 1 1 1 1 π΄βˆ— (𝐺(2)) = 𝐴 + 𝐴2 = 1 1 1 3 2 2 2 οƒž 𝐡 = 1 1 1 0 1 1 1 . 0 0 1 2 2 2 1 0 0 1 1 0 1 1 0 0 2 2 2 3 1 0 0 1 1 1 0 1 ( 1 1 1 2 1 1 2) (1 1 1 1 1 1 0) Sets of vertices {1, 2, 3,4, 7} and {3, 4, 5, 6, 7} in the graph 𝐺(2) generate subgraphs, each of which is isomorphic to the complete graph 𝐾5 , that is, these subgraphs are maximal cliques in 𝐺(2). For each of the graphs, we will determine the dynamic average 𝑑(𝐺) β‰ˆ 2,7; 𝑑(𝐺(2)) = 5. This shows a substantial increase in density 𝐺(2) in comparison with 𝐺. Sufficient network means a network for which there is such an equilibrium in which all agents accept or are ready to participate in a collective action, regardless of their position [28, 29]. Sufficient networks are called minimal if there are no redundant communication links. Cliques form local sufficient networks in the global network. A mathematical model of a minimal network is a spanning tree of clique. It is important that communication between agents does not disappear, so it is better to have options for transition from one trunk tree to others, if they exist. Let's formulate the problem of finding a set of minimal structures of communication between agents, which provides the necessary properties of a sufficient social network in terms of graph theory: perform a spanning tree search in a click, in other words to construct a 𝑇-factorization of 𝐾𝑛 , that is, a (𝐾𝑛 , 𝑇)-decomposition. Among the methods of constructing such a decomposition, we can distinguish cyclic and semi-rotary ones. (𝐾𝑛 , 𝑇)-decomposition is cyclic, if all its components are obtained from the same base (or several . The specified 495 cyclic substitution is called the generator of the decomposition, and its degrees are automorphisms of (𝐾𝑛 , 𝑇)-decomposition. Each basic component of cyclic (𝐾𝑛 , 𝑇)-decomposition under the influence of powers of substitution 𝛼 generates an orbit, and two different orbits do not intersect. A semisymmetrical tree is a tree, which contains a central edge and after its removal, two isomorphic connectivity components are obtained, which are trees. An automorphism for such a tree with a central edge π‘₯𝑦 exists πœ‘, then πœ‘(π‘₯) = 𝑦 and πœ‘(𝑦) = π‘₯. Therefore, it belongs to the class of symmetric trees in terms [9, 29]. Semirotary (𝐾𝑛 , 𝑇)-decomposition is also obtained using the action of cyclic substitution 𝛼 on the tree 𝑇, but 𝑇 should be the right tree. Let's describe the scheme of building a semi-rotary (𝐾𝑛 , 𝑇)- decomposition, where 𝑇 is a tree of order 𝑛 βˆ’ 1, 𝑛 = 2π‘˜, π‘˜ is an integer number. 1. Consider a circle divided by 𝑛 = 2π‘˜ points on equal parts (elementary arcs), let us match the numbers to the points 0, 1, 2, … , 𝑛 βˆ’ 1. These points represent the vertices of the complete graph 𝐾𝑛 . 2. Determine the length of the edge (i, j) as a number 𝑑(𝑖, 𝑗) = min(|π‘–βˆ’π‘—|, π‘›βˆ’οΌπ‘–βˆ’π‘—|), where 𝑖 β‰  𝑗, 𝑖, 𝑗 ∈ {0, 1, 2, … , 𝑛 βˆ’ 1}. 3. We place the vertices of the semisymmetric tree at the dividing points so that the edges of the tree are represented by the chords of a circle and for each admissible chord length exactly two non-centered edges have this length. Such a tree is a right tree. 4. For each edge (𝑖, 𝑗), where 𝑖 β‰  𝑗, 𝑖, 𝑗 ∈ {0, 1, 2, … , 𝑛 βˆ’ 1} there is an edge symmetrical to it (𝑖 + π‘˜, 𝑗 + π‘˜) relative to the center of the circle, the addition is performed by mod𝑛. 5. Tree family 𝑇, 𝑇𝛼, … , 𝑇𝛼 π‘˜βˆ’1 represents (𝐾𝑛 , 𝑇)-decomposition, which is called semirotating 𝑇-factorization of 𝐾𝑛 . A semirotating (𝐾𝑛 , 𝑇)-decomposition has a nontrivial group of automorphisms, since this group, in addition to the cyclic substitution, includes the substitution that transforms every vertex 𝐾𝑛 into a symmetric one about the center of the circle. Problems of constructing cyclic and semirotating (𝐾𝑛 , 𝑇)-decomposition come to the tasks of constructing the appropriate tree labeling of 𝑇. For a cyclic schedule, the tree 𝑇 have to be graceful. According to the theorem 2, a cyclic disposition exists if 𝑇 allows 𝜌-labeling and 𝑛 is an even number. Consider a semisymmetric tree 𝑇 of order 2π‘˜ consisting of two symmetric parts 𝑇 (1) and 𝑇 (2), connected by an edge (π‘₯, 𝑦), where π‘₯ ∈ 𝑉(𝑇 (1) ), 𝑦 ∈ 𝑉(𝑇 (2) ). Let us say that for 𝑇 (1) there is a graceful labeling 𝑓, that 𝑓(π‘₯) = π‘˜ βˆ’ 1. We adapt the method of building graceful labeling proposed in [30], into tree 𝑇: 1. Consider a tree 𝑇 (1) as a bipartite graph, to do this, we partition the set of its vertices into two subsets A, B as the following: β€’ find the distance 𝑑(π‘₯, 𝑣𝑖 )from the vertex π‘₯ to all other vertices 𝑣𝑖 of the tree 𝑇 (1); β€’ if 𝑑(π‘₯, 𝑣𝑖 ) equals zero or an even number, then 𝑣𝑖 ∈ 𝐴, otherwise 𝑣𝑖 ∈ 𝐡; 2. For the labels of tree vertices T, we use the labeling οͺ, which is determined from the formulas: 𝑠 βˆ™ π‘˜ βˆ’ 1 βˆ’ 𝑓(𝑣𝑖 ), 𝑣𝑖 ∈ 𝐴, (2) πœ‘(𝑣𝑖𝑠 ) = { (3 βˆ’ 𝑠) βˆ™ π‘˜ βˆ’ 1 βˆ’ 𝑓(𝑣𝑖 ), 𝑣𝑖 ∈ 𝐡, πœ‘(π‘₯) = 0, πœ‘(𝑦) = π‘˜, π‘€β„Žπ‘’π‘Ÿπ‘’ 𝑠 = 1; 2. (3) 3. οͺ is the graceful labeling of the tree 𝑇 [16]. Problems of construction of cyclic and semi-rotary (𝐾𝑛 , 𝑇)-decomposition are reduced to the problems of the existence of the corresponding tree labeling 𝑇. For the cyclic schedule, the tree 𝑇 has 496 to be graceful. According to the theorem 2, semi-rotary 𝑇- factorization of 𝐾𝑛 exists if a symmetric tree 𝑇 allows 𝜌-labeling and 𝑛 is even. Theorem 4. Let the tree 𝑇of order 2π‘˜, consisting of two symmetrical parts 𝑇 (1)and 𝑇 (2), connected by an edge (π‘₯, 𝑦), where π‘₯ ∈ 𝑉(𝑇 (1) ), 𝑦 ∈ 𝑉(𝑇 (2) ). Then semi-rotary 𝑇-factorization of 𝐾𝑛 exists if and only if the symmetric part 𝑇 (1) (or 𝑇 (2)) has a graceful labeling. Proof. Semi-rotary construction method 𝑇-factorization of 𝐾𝑛 is based on the cyclic method of decomposition of the complete graph. Let's assume that the part is symmetrical, let's denote it 𝑇 (1), the tree 𝑇 of order 2π‘˜ has a graceful labeling, and therefore 𝜌-labeling. Let's go to 𝑇 (1) cyclic substitution 𝛼. We will get a family of trees 𝑇 (1) , 𝑇 (1) 𝛼, … , 𝑇 (1) 𝛼 2π‘˜ . The sets of their edges do not intersect in pairs and do not cover only on the circle π‘˜ chord of length π‘˜. We will cover these chords with ribs connecting symmetrical parts of the tree 𝑇. We will get a semi-rotary 𝑇-factorization of 𝐾𝑛 , in which each component is a tree 𝑇 and the isomorphic halves of the tree 𝑇 symmetrical about the corresponding chord length π‘˜. Let's assume that there is a semi-rotating 𝑇-factorization of 𝐾𝑛 . Since 𝑇 is a factor of 𝐾𝑛 , then the basic component of the expansion contains a symmetric part 𝑇 (1) is located on a circle so that the labels of its vertices are the numbers from 0 to (𝑛 βˆ’ 2)/2 while the lengths of the edges are the numbers from 1 to (𝑛 βˆ’ 2)/2. This shows that the specified markup is a graceful labeling of 𝑇 (1) . The theorem has been proved. Let us show by example how to implement communication support between 12 agents of the network in its graph model based on the method of constructing a semi-rotary (𝐾12 , 𝑇)- decomposition. As 𝑇 consider a semi-symmetric tree of order 12. Every component of it is a graceful tree (fig. 2 a). Graceful labeling of 𝑇 we will find in accordance with the formulas (2), (3) (fig 2 b). Since 𝑇 is graceful, it exists (𝐾12 , 𝑇)-decomposition. Let's make the correct entry of the tree 𝑇 in a circle (fig. 2 c). Under the influence of powers of cyclic substitution 𝛼, we will get a family of trees 𝑇, 𝑇𝛼, … , 𝑇𝛼 5 , which is (𝐾12 , 𝑇)-decomposition. Each of these trees implements non-redundant communication between agents, while all agents take part in information dissemination. Therefore, in case of obstacles, it is not difficult to establish a connection. 5. Discussion of results and conclusions We considered two approaches to social network research. The first consists in identifying structures with connections of a certain type in the network and further improving these structures depending on the task at hand. If the network contains π‘˜-cliques, it is important to select among them those with the maximum number of vertices. This makes it possible to expand the network by introducing additional connections without changing the number of agents. We proposed a method for finding such k-cliques, leading to the discovery of the maximum cliques in the network. 0 5 0 6 11 1 10 2 0 11 5 9 3 4 1 7 8 4 1 2 3 10 9 8 4 3 2 7 5 6 a) b) c) Figure 2: a) Graceful labeling of one of the components of a semisymmetrical tree 𝑇; 497 b) A semi-symmetrical tree 𝑇 and its graceful labeling; c) Correct fitting of the tree 𝑇 in a circle. The second approach is aimed at optimizing the process of information transfer between agents. It is based on methods of the theory of graph decomposition and labeling. The minimal social networks built by cyclic and semi- rotating methods, isomorphic to the same tree-like structure, form a set of network graphs with the same diameter and the same maximum degree. In addition, no two minimal networks have any edges in common, so damage to one network does not affect any other factor in the resulting population. The mathematical framework presented in this work can be integrated into existing algorithms for social network analysis. For instance, the research findings can be adapted to improve clustering algorithms, recommendation systems, and other applications requiring user interaction analysis. Declaration on Generative AI The authors have not employed any Generative AI tools. References [1] P. J. Carrington, J. Scott, S. Wasserman (Eds.), Models and Methods in Social Network Analysis, Cambridge University Press, 2005, 344 p. doi:10.1017/CBO9780511811395. [2] Jean Gallier, Spectral theory of unsigned and signed graphs applications to graph clustering: a survey. Department of Computer and Information Science University of Pennsylvania Philadelphia, PA, USA. (2016): 122 p. doi:10.48550/arXiv.1601.04692 [3] Ulrike von Luxburg, A Tutorial on Spectral Clustering. Statistics and Computing. Volume 17(4). (2007): pp. 395-416. doi:10.48550/arXiv.0711.0189. [4] Q. Zheng, Spectral Techniques for Heterogeneous Social Networks/ PhD Dissertation. University Kingston, Ontario, Canada, 2016. 235 p. https://qspace.library.queensu.ca/server/api/core/bitstreams/cfa9fac4-b8f1-4fad-becf- 96511fea9afe/content [5] Lucia Falzon, Determining groups from the clique structure in large social networks. Social Networks, Volume 22, Issue 2. (2000): pp. 159-172. doi.org/10.1016/S0378-8733(00)00021-6 [6] D. Schall, Social Network-Based Recommender Systems, 1st ed., Springer International Publishing Switzerland, 2015. doi: 10.1007/978-3-319-22735-1. [7] Dr. Cvetkovic, Slobodan Simic, Graph spectra in Computer Science. Linear Algebra and its Applications, volume 434, Issue 6. (2011): pp. 1545-1562. doi:10.1016/j.laa.2010.11.035. [8] M. Kadivar. N. Mohammadi, A maximum clique based approximation algorithm for wireless link scheduling under SINR model. Journal of Computer and System Sciences, volume 129(2), 2022, pp.72-89. doi.org/10.1016/j.jcss.2022.05.001. [9] Saad I. El-Zanati, Charles Vanden Eynden, On Rosa-type labelings and cyclic graph decompositions. Math. Slovaca, volume 59, No. 1, 2009, pp. 1 18. doi: 10.2478/s12175-008-0108- x. [10] J.A. Gallian, A dynamic survey of graph labeling. The Electronic Journal of Combinatorics. DS6: Dec 1, 2023. 644 p. [11] L. Despalatovic, T. Vojkovic, D. Vukicevic, Community structure in networks: Girvan-Newman algorithm improvement, 37th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2014, pp. 90 94. doi: 10.1109/MIPRO.2014.6859714. [12] P. Bedi, C. Sharma, Community detection in social networks. WIREs Data Mining and Knowledge Discovery, volume 6, Issue 3, 2016, pp. 115-135. doi: 10.1002/widm.1178. 498 [13] M Zahiri, J. Mohammadzadeh, S. Harifi, An improved Girvan Newman community detection algorithm using trust-based centrality. Journal of Ambient Intelligence and Humanized Computing, volume 14, 2021, pp. 1-5. doi: 10.1007/s12652-021-03508-y. [14] N. Alotaibi, D. Rhouma, A Review on community structures detection in time evolving social networks, Journal of King Saud University - Computer and Information Sciences, 34 (8), 2022, pp. 5646-5662. doi: 10.1016/j.jksuci.2021.08.016. [15] J. Zhang, J. Fei, X.Song, J.Feng, An improved Louvain algorithm for community detection, Mathematical Problems in Engineering, volume 2021, issue 1, 2021. doi: 10.1155/2021/1485592. [16] N. Aston, W. Hu, Community Detection in Dynamic Social Networks, Communications and Network, 6 (2), 2014, pp. 124-1366. doi: 10.4236/cn.2014.62015. [17] J M. Seifikar; S. Farzi; M. Barati, C-Blondel: An Efficient Louvain-Based Dynamic Community Detection Algorithm, IEEE Transactions on Computational Social Systems, volume 7(2), 2020, pp. 308-318. doi: 10.1109/TCSS.2020.2964197. [18] J. G. Baltsou, K. Christopoulos, K.Tsichlas, Local community detection: a survey, IEEE Access, volume 10(2), 2022, pp.110701-110726. doi: 10.1109/ACCESS.2022.3213980. [19] J. Chhatani, J. Chaudhary, Novel algorithm to find maximum clique. Fifth International Conference on Image Information Processing (ICIIP), 2019, pp. 286-291. doi: 10.1109/ICIIP47207.2019.8985699. [20] N. Med, A. Moussaoui, B. Saoud, Detecting communities in social networks based on cliques. Physica A: Statistical Mechanics and its Applications, volume 551, 2020. doi: 10.1016/j.physa.2019.124100. [21] T. Fan, W. Jiang, Y. Zhang, Linyuan LΓΌ, A fast maximum clique algorithm based on network decomposition for large sparse networks. Computer Science, Social and Information Networks, 2024. https://arxiv.org/pdf/2404.11862. [22] . Jiang, L. Chen, . Zhou, An improved community detection algorithm based on edge-graph of network under the spark environment. IEEE 18th International Conference on High Performance Computing and Communications; IEEE 14th International Conference on Smart City; IEEE 2nd International Conference on Data Science and Systems (HPCC/SmartCity/DSS), 2016. doi: 10.1109/HPCC-SmartCity-DSS.2016.0058. [23] S.Y. Chan, K. Morgan, J. Ugon, Finding Maximum Cliques in Large Networks. Social and Information Networks. 2022. https://arxiv.org/pdf/2207.13010. [24] F. Liu, S. Xue, J. Wu, Weiqiang Chen, Deep Learning for Community Detection: Progress, Challenges and Opportunities. Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence (IJCAI-PRICAI-20). 2020, pp. 4981-4987. [25] N. Alon, F. R. K. Chung. Explicit construction of linear sized tolerant networks. Discrete Mathematics, 1988, pp. 15-19. https://doi.org/10.1016/0012-365X(88)90189-6. [26] F. Harary, Graph Theory, Taylor & Francis Group, 2019. 284 p. [27] D. . Doob, H. Sachs, Spectra of Graphs: Theory and Application, 3rd rev. and enl. ed. - Heidelberg: Johann Ambrosius Barth, 1985. 447 p. [28] M. Suk-Young Chwe, Communication and Coordination in Social Networks. Review of Economic Studies. Volume 67(1). 01.11(2007): P. 1-16. doi.org/10.1111/1467-937X.00118 [29] R. Wei, Consensus seeking, formation keeping and trajectory tracking in multiple vehicle cooperative control. PhD Dissertation. Brigham Young University, 2004. 141 p. https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1152&context=etd [30] G. Rinaldi, Regular 1-factorizations of complete graphs and decompositions into pairwise isomorphic rainbow spanning trees. The Australasian Journal of Combinatorics, Volume 80(2) (2021), pp. 178 196. 499