CN106841012A - Flow cytometry data automatically-controlled door prosecutor method based on distributed graph model - Google Patents

Abstract

The invention discloses an automatic gating method for flow cytometer data based on a distributed graph model, which applies distributed technology to the gating calculation of flow cytometer data; and executes parallel calculations for all element-based operations of the graph model , to improve program execution performance; the kNN search strategy based on random projection trees reduces the time to linear complexity of constructing graphs; Spark's distributed storage method can handle larger-scale data sets. The random projection tree is used to speed up the search efficiency of kNN; the operation of edge weights is parallelized; the cut graph algorithm adopts a parallelized community partition algorithm. The present invention realizes the clustering analysis based on the graphical model for the gating process of the flow cytometer data through the distributed computing framework, and automatically divides the original data, thereby improving the efficiency and accuracy of data analysis, and reducing the duplication of labor and labor involved in the division process. Human subjective factors.

Description

Automatic Gating Method of Flow Cytometry Data Based on Distributed Graph Model

technical field

The invention relates to flow cytometer technology, in particular to an automatic gating method for flow cytometer data based on a distributed graph model.

Background technique

Flow cytometry is a relatively advanced single-cell measurement technology at present. It is a technology for high-speed, one-by-one quantitative analysis and sorting of single cells or other biological particles in suspension by detecting the labeled fluorescent signal. Mass cytometry technology is a new generation of single cell measurement technology developed on the basis of flow cytometry. Use rare earth element isotopes to label specific antigens, control the specific binding of antigens and antibodies on the surface of single cells, then gasify the cells, control their plasma into the mass spectrometer, and the technical results of mass spectrometry for the isotope represent the expression level of the labeled antigen on the cell . The degree of antigen expression is closely related to the function and type of cells. The measurement results of this scale provide great help for the research of the immune system, including cell screening and typing.

The basis of most studies is to rely on these markers to gradually screen out interested cell subpopulations for further research. This process is called gating. The traditional gating method is to use the existing domain knowledge, rely on the two-dimensional map of the markers with key information, and gradually manually separate the cell subpopulations of interest from the raw data according to a certain level. Several commercial software also provide users with faster and more interactive operations on this basis: FCS Express, FlowJo, CytoBank, etc. Gating becomes less feasible as the dimensionality of single-cell data increases.

The academic community introduces computational methods, focusing on using unsupervised learning-clustering to replace artificial gating work on data sets, and the general directions include density-based, geometry-based, etc. Among the clustering algorithms provided by Cytobank, there are only relatively basic k-means and hierarchical clustering. Compared with these methods, the graph-based method does not need to have a prior morphological assumption on the data, and the input parameters can output stable results in a large range. It has the ability to identify and retain rare subgroups, and can also be connected. Further semi-supervised learning and migration data mining models become better choices.

Traditional manual gating is to sample a two-dimensional scatter diagram division strategy, which is time-consuming and labor-intensive, with large human subjective factors and no repeatability. It is powerless for high dimensions, and the complexity is O(m^2), where m is the number of data points. dimension. And this method has no gold standard for poorly defined tissues (such as liver and spleen).

Traditional clustering algorithms have no way to deal with the consistency between model assumptions and data distribution. For example, k-means is a polygonal division of a geometric space. It is easy to merge two data areas that are clearly divided into one category in a polygonal space; clustering algorithms that rely on density such as DBSCAN need to estimate the density kernel width in advance, so for sizes smaller than this In the area of nuclear width, there is incompatibility and so on. Compared with these methods, graph-based methods largely preserve both global and local data characteristics.

The calculation process of conventional graph algorithms often requires global traversal of nodes and edges, which will consume a lot of time and memory when faced with large-scale experimental data. For example, the first step usually needs to construct a kNN graph, and it is necessary to traverse and calculate the pairwise distance between all data points, the complexity is O(n^2), n is the number of data points, and the weight of the edge is pre-stored at the same time. In other operations, such as weight update, addition and deletion of edges, there are also many element-by-element operation methods, which are inefficient in a single-threaded manner. When the data points reach the order of millions, the conventional stand-alone configuration has made the memory consumption and computing time unbearable, which will limit the experimental data processing with higher and higher throughput.

Contents of the invention

The object of the present invention is to provide an automatic gating method for flow cytometry data based on a distributed graph model to address the deficiencies in the prior art.

The object of the present invention is achieved by the following technical solutions: a method for automatic gating of flow cytometry data based on a distributed graph model, comprising the following steps:

(1) Transform the input cytometer data file into an RDD type according to the GraphLab framework, and obtain the flow cytometer data X={x ₁ ,x ₂ ,...,x _N };

(2) Input the flow cytometry data X={x ₁ ,x ₂ ,...,x _N }, the size of the neighborhood k, and the number of random repetitions r; N is the number of data points. Output C={c ₁ ,c ₂ ,...,c _N }, which represents the label assigned to each data point, that is, the result after gating;

(3) Distributed construction of kNN graph based on random projection tree and GraphLab framework:

In the Gather stage, several hyperplanes v are randomly generated on each thread, and each data point is regarded as a node. The node x on this thread is selected to meet the distance requirement of the farthest point x·v≤median({z·v:z∈ S}+δ) nodes automatically become neighbors. In the Scatter stage, the weight of the edge between node x and the neighbor node is 1, and the weight of the edge between the non-neighbor node is 0. When each node is found to have neighbors When the number reaches k, it will automatically jump out to construct a kNN graph; S is the set of nodes, δ is an arbitrary constant, and median() means to take the median value. In order to achieve the required accuracy, it is repeated 2-3 times, and the intersection of the graphs is taken to ensure the accuracy, and the final kNN graph is obtained;

(4) Through the Gather stage of the GraphLab framework, traverse all the edges of each node x; through the Scatter stage of the GraphLab framework, calculate the Jaccard coefficient J _k ( _xi , x _j ) according to all nodes V _k (x) connected to the node ), turn the kNN graph into a graph with weights;

(5) Execute the graph cut algorithm on the obtained weighted graph to obtain a division C={c ₁ ,c ₂ ,...,c _N } and the objective function Q value. The calculation of the Q value is as in (2):

Among them, J represents the weight of the entire weighted graph, and δ( _{ci,c j )} represents the delta function. When the input is equal, it takes 1, otherwise it takes 0. deg(v _i ) represents the degree of node i, there is no negative weight in this model, and m represents 1/2 of the sum of the weights of the edges in the weighted graph.

(6) Repeat step 4 r times, and select C corresponding to the largest Q value in r times as the result after gating.

Further, said step 5 includes the following sub-steps:

a) Initialize each node to form a community;

b) Traversing nodes in parallel, for each node j∈V _k (x) in the neighborhood V _k (x) of node i, calculate the increment value ΔQ of Q value if i is classified into the community c _j to which j belongs, Find the way in which ΔQ is the largest. In the process of calculating ΔQ, through the Gather stage, read the edge weight and the node corresponding to the edge, and add the weight of each edge to the attribute of the corresponding node in the Apply stage, calculate the degree of each node, and give A temporary label of a node represents the community it belongs to. ΔQ is calculated according to the degree and temporary label of each node.

Where ∑in is the sum of the weights of the edges between the internal nodes of community C, ∑tot is the sum of the weights of all the edges connected to C after the implementation of the subsuming method, k _i is the weight of all the connected edges of node i The sum of k _i,in is the sum of the weights of all edges brought in after node i connects to community C, and m is the sum of the weights of all edges in the entire network.

c) After selecting the largest ΔQ incorporation method, all points within the community are aggregated into a new point, and a self-connected edge is added to the community, and the weight of the self-connected edge is the sum of the weights of the edges between the internal nodes of community C , the weight of the edge between the community and the community is the sum of the weight of the edge between the connected members of the two communities before aggregation. Bring the aggregated graph back into step b) to do the same.

d) Repeat b) and c) until ΔQ converges.

The beneficial effects of the invention are: the distributed technology is applied to the gating calculation of the flow cytometry data; all the parallel calculations of the graphic model are operated by elements, and the program execution performance is improved. A kNN search strategy based on random projection trees reduces the time-to-linear complexity of constructing graphs. Spark's distributed storage method can handle larger-scale data sets (more than one million data points). The search efficiency of kNN is accelerated by using random projection tree. The operation of edge weights is parallelized. The cut graph algorithm uses a parallelized community partition algorithm. The present invention realizes the clustering analysis based on the graphical model for the gating process of the flow cytometer data through the distributed computing framework, and automatically divides the original data, thereby improving the efficiency and accuracy of data analysis, and reducing the duplication of labor and effort in the division process. Human subjective factors.

Description of drawings

Figure 1 shows how GraphLab constructs a storage graph;

Figure 2 shows the Gather‐Apply‐scatter architecture;

Figure 3 is a flow chart of the clustering algorithm;

In Figure 4 (a) is the principle of k-d tree, (b) is the principle of random projection tree.

detailed description

The present invention will be described in further detail below in conjunction with the accompanying drawings and specific embodiments.

The present invention uses a graph-based clustering algorithm to realize automatic gating of flow cytometry data, that is, realizes data clustering by constructing, modifying and dividing graphs on the data set. By assuming the overall distribution pattern of the data and selecting a similarity measure, the output of stable clustering results is achieved through the optimization of internal indicators (or called objective functions), and the accuracy of the clustering results is achieved by relying on external indicators (compared with artificial labels) . The unsupervised learning process is straightforward and easy to implement efficiently. Compared with the traditional gating strategy, it can greatly liberate manpower, and the results are repeatable.

In order to improve computing performance so that the method can adapt to larger data sets in the future and give researchers feedback information faster, the present invention adopts the Spark-based GraphLab distributed computing framework, which provides a mature graph-based The data mining model function excuse can help us realize this algorithm on a distributed framework. The GraphLab distributed computing framework is as follows:

The parallelization of GraphLab mainly relies on vertices, which are the minimum parallel granularity and communication granularity, while edges are the representation of data dependence in machine learning algorithms. GraphLab's storage mode is to store a single vertex on multiple machines, divided into master-mirror, and for a certain edge, GraphLab will deploy it to a certain machine, so that each machine has a local map, such as Figure 1 shows. There is a mapping table from the local id to the global id. The nodes in the graph are shared by all threads in a process. In the process of parallel computing, each thread shares the gather→apply→scatter operation of all vertices, as shown in Figure 2.

Each iteration of each vertex goes through three stages of gather->apple->scatter.

1) Gather stage

The edge of the working vertex (it may be all edges, or it may be the incoming edge or the outgoing edge) collects data from the leading vertex and itself, which is recorded as gather_data_i, and graphlab will sum the data of each edge, which is recorded as sum_data. This phase is read-only for working vertices and edges.

2) Apply stage

Mirror sends the result sum_data calculated by gather to the master vertex, and the master summarizes it as total. The master uses the total and the vertex data in the previous step to perform further calculations according to business requirements, then updates the vertex data of the master and synchronizes the mirror. In the Apply phase, the working vertices can be modified, but the edges cannot be modified.

3) Scatter stage

After the update of the working vertex is completed, the data on the edge is updated, and the adjacent node vertices that depend on it are notified to update the status. During the scatter process, the working vertices are read-only, and the data on the edges can be written.

In the execution model, GraphLab achieves mutual exclusion by controlling the read and write permissions of the three stages. Read-only in the gather phase, apply only writes to vertices, and scatter writes only to edges. The synchronization of parallel computing is realized through the master and mirror. The mirror is equivalent to an interface for each vertex, abstracting complex data communication into the behavior of the vertex.

For conventional graph operations, Graphlab also provides APIs that can be called directly, such as element access graphlab.Edge, element fusion graphlab.aggregate(), etc.

A method for automatic gating of flow cytometer data based on a distributed graph model provided by the present invention, as shown in Figure 3, comprises the following steps:

(1) Transform the input cytometer data file into an RDD type according to the GraphLab framework, and obtain the flow cytometer data X={x ₁ ,x ₂ ,...,x _N };

(2) Input the flow cytometry data X={x ₁ ,x ₂ ,...,x _N }, the size of the neighborhood k, and the number of random repetitions r; N is the number of data points. Output C={c ₁ ,c ₂ ,...,c _N }, which represents the label assigned to each data point, that is, the result after gating;

(3) Distributed construction of kNN graph based on random projection tree and GraphLab framework:

In the Gather stage, several hyperplanes v are randomly generated on each thread, and each data point is regarded as a node. The node x on this thread is selected to meet the distance requirement of the farthest point x·v≤median({z·v:z∈ S}+δ) nodes automatically become neighbors. In the Scatter stage, the weight of the edge between node x and the neighbor node is 1, and the weight of the edge between the non-neighbor node is 0. When each node is found to have neighbors When the number reaches k, it will automatically jump out to construct a kNN graph; S is the set of nodes, δ is an arbitrary constant, and median() means to take the median value. In order to achieve the required accuracy, it is repeated 2-3 times, and the intersection of the graphs is taken to ensure the accuracy, and the final kNN graph is obtained;

(4) Through the Gather stage of the GraphLab framework, traverse all the edges of each node x; through the Scatter stage of the GraphLab framework, calculate the Jaccard coefficient J _k ( _xi , x _j ) according to all nodes V _k (x) connected to the node ), turn the kNN graph into a graph with weights;

(5) Execute the graph cut algorithm on the obtained weighted graph to obtain a division C={c ₁ ,c ₂ ,...,c _N } and the objective function Q value. The calculation of the Q value is as in (2):

Among them, J represents the weight of the entire weighted graph, and δ( _{ci,c j )} represents the delta function. When the input is equal, it takes 1, otherwise it takes 0. deg(v _i ) represents the degree of node i, there is no negative weight in this model, and m represents 1/2 of the sum of the weights of the edges in the weighted graph. The specific implementation steps of this step are as follows:

a) Initialize each node to form a community;

b) Traversing nodes in parallel, for each node j∈V _k (x) in the neighborhood V _k (x) of node i, calculate the increment value ΔQ of Q value if i is classified into the community c _j to which j belongs, Find the way in which ΔQ is the largest. In the process of calculating ΔQ, through the Gather stage, read the edge weight and the node corresponding to the edge, and add the weight of each edge to the attribute of the corresponding node in the Apply stage, calculate the degree of each node, and give A temporary label of a node represents the community it belongs to. ΔQ is calculated according to the degree and temporary label of each node.

Where ∑in is the sum of the weights of the edges between the internal nodes of community C, ∑tot is the sum of the weights of all the edges connected to C after the implementation of the subsuming method, k _i is the weight of all the connected edges of node i The sum of k _i,in is the sum of the weights of all edges brought in after node i connects to community C, and m is the sum of the weights of all edges in the entire network.

c) After selecting the largest ΔQ incorporation method, all points within the community are aggregated into a new point, and a self-connected edge is added to the community, and the weight of the self-connected edge is the sum of the weights of the edges between the internal nodes of community C , the weight of the edge between the community and the community is the sum of the weight of the edge between the connected members of the two communities before aggregation. Bring the aggregated graph back into step b) to do the same.

d) Repeat b) and c) until ΔQ converges.

(6) Repeat step 4 r times, and select C corresponding to the largest Q value in r times as the result after gating.

Claims (2)

1. A flow cytometer data automatic gating method based on distributed graph model, it is characterized in that, the method comprises the following steps: (1) Transform the input cytometry data file into RDD type according to the GraphLab framework, and obtain the flow cytometry data X={x ₁ ,x ₂ ,...,x _N }; (2) Input the flow cytometry data X={x ₁ ,x ₂ ,...,x _N }, the neighborhood size k, and the number of random repetitions r; N is the number of data points. Output C={c ₁ ,c ₂ ,...,c _N }, which represents the label assigned to each data point, that is, the result after gating; (3) Distributed construction of kNN graph based on random projection tree and GraphLab framework: In the Gather stage, several hyperplanes v are randomly generated on each thread, and each data point is regarded as a node. The node x on this thread is selected to meet the distance requirement of the farthest point x·v≤median({z·v:z∈ S}+δ) nodes automatically become neighbors. In the Scatter stage, the weight of the edge between node x and the neighbor node is 1, and the weight of the edge between the non-neighbor node is 0. When each node is found to have neighbors When the number reaches k, it will automatically jump out to construct a kNN graph; S is the set of nodes, δ is an arbitrary constant, and median() means to take the median value. In order to achieve the required accuracy, it is repeated 2-3 times, and the intersection of the graphs is taken to ensure the accuracy, and the final kNN graph is obtained; (4) Through the Gather stage of the GraphLab framework, traverse all the edges of each node x; through the Scatter stage of the GraphLab framework, calculate the Jaccard coefficient J _k ( _xi , x _j ) according to all nodes V _k (x) connected to the node ), turn the kNN graph into a graph with weights; ${\mathrm{<span\; class="notranslate">\; J</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&cap;</span>{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; |</span>}{{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&cup;</span>{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$ (5) Execute the graph cut algorithm on the obtained weighted graph to obtain a division C={c ₁ ,c ₂ ,...,c _N } and the objective function Q value. The calculation of the Q value is as in (2): $\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; J</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; C</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; m</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}<span\; class="notranslate">\; \&lsqb;</span>{\mathrm{<span\; class="notranslate">\; J</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\frac{\mathrm{<span\; class="notranslate">\; deg</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; deg</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; \&rsqb;</span>\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$ Among them, J represents the weight of the entire weighted graph, and δ( _{ci,c j )} represents the delta function. When the input is equal, it takes 1, otherwise it takes 0. deg(v _i ) represents the degree of node i, there is no negative weight in this model, and m represents 1/2 of the sum of the weights of the edges in the weighted graph. (6) Repeat step 4 r times, and select C corresponding to the largest Q value in r times as the result after gating. 2. A kind of flow cytometer data automatic gating method based on distributed graph model according to claim 1, is characterized in that, described step 5 comprises the following substeps: a) Initialize each node to form a community; b) Traversing nodes in parallel, for each node j∈V _k (x) in the neighborhood V _k (x) of node i, calculate the increment value ΔQ of Q value if i is classified into the community c _j to which j belongs, Find the way in which ΔQ is the largest. In the process of calculating ΔQ, through the Gather stage, read the edge weight and the node corresponding to the edge, and add the weight of each edge to the attribute of the corresponding node in the Apply stage, calculate the degree of each node, and give A temporary label of a node represents the community it belongs to. ΔQ is calculated according to the degree and temporary label of each node. $\mathrm{<span\; class="notranslate">\; \&Delta;</span>}\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; \&lsqb;</span>\frac{<span\; class="notranslate">\; \&Sigma;</span>\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; k</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; no</span>}}}{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; -</span>{<span\; class="notranslate">\; (</span>\frac{<span\; class="notranslate">\; \&Sigma;</span>\mathrm{<span\; class="notranslate">\; t</span>}\mathrm{<span\; class="notranslate">\; o</span>}\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; k</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; \&lsqb;</span>\frac{<span\; class="notranslate">\; \&Sigma;</span>\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; -</span>{<span\; class="notranslate">\; (</span>\frac{<span\; class="notranslate">\; \&Sigma;</span>\mathrm{<span\; class="notranslate">\; t</span>}\mathrm{<span\; class="notranslate">\; o</span>}\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span>{<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; k</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$ Where ∑in is the sum of the weights of the edges between the internal nodes of community C, ∑tot is the sum of the weights of all the edges connected to C after the implementation of the subsuming method, k _i is the weight of all the connected edges of node i The sum of k _i,in is the sum of the weights of all edges brought in after node i connects to community C, and m is the sum of the weights of all edges in the entire network. c) After selecting the largest ΔQ incorporation method, in the Apply stage, the points in all communities in the compressed data set are aggregated into a new point, and a self-connected edge is added to the community, and the weight of the self-connected edge is between the internal nodes of community C The sum of the weights of the edges between the communities and the edges between the communities is the sum of the weights of the edges between the connected members of the two communities before aggregation. Bring the aggregated graph back into step b) to do the same. d) Repeat b) and c) until ΔQ converges.