CN103020267B - Based on the complex network community structure method for digging of triangular cluster multi-label - Google Patents

Abstract

Based on a complex network community mining method for triangular cluster multi-label, comprise the following steps: mutually disjoint triangular cluster in search network; For the initial state that the mutually different label of the Node configuration in different triangular cluster is propagated as label; According to many tag update rules, for all nodes in network, the propagation synchronously carrying out label upgrades; By the label array that obtains after upgrading with upgrade the label array obtained before and compare; If label is still in propagation, then proceed to upgrade; If label produces vibration, then proceed again after carrying out vibration Processing for removing to upgrade; If label no longer changes, then stop upgrading, obtain the community structure with overlap in network.Time complexity of the present invention is very low, is applicable to large-scale complex network.In addition, the present invention can detect the lap of community structure well, and has good robustness, and the accuracy of detection is very high.

Description

Community Structure Mining Method in Complex Networks Based on Multi-label Propagation of Triangular Clusters

technical field

The invention relates to a method in the field of complex networks, in particular to a method for mining complex network community structures based on triangular cluster multi-label propagation.

Background technique

A complex network is an abstract representation of complex systems in the real world. The nodes in a complex network represent the individuals in the complex system, and the connections between nodes represent the natural or man-made connections between individuals in the system according to certain rules. relationship. At present, complex networks have been widely used to represent various complex systems such as power networks, communication networks, the Internet, and social networks.

Community structure is an important topological characteristic of complex networks. The entire complex network is composed of several community structures. The nodes within each community structure are very tightly connected, while the connections between community structures are relatively sparse. The community structure of a complex network corresponds to functional units or organizational groups with common characteristics in reality. For example, the community structure in the Internet is some websites that discuss common topics, while the community structure in social networks is composed of people with common interests. a group. Therefore, it is of great practical significance to analyze the characteristics and functions of the network by mining the community structure in the complex network.

Community structure mining of complex networks needs to satisfy two key properties:

First, the complexity is low. The scale of complex networks is often very large, and can contain thousands or even tens of thousands of nodes. Under such a network, if the complexity of the method is high, the time spent on community structure mining will be very large;

Second, an effective mechanism for detecting overlapping structures. In actual complex networks, community structures commonly overlap, that is, some nodes in complex networks can belong to multiple community structures at the same time, which requires community structure mining methods to be able to detect the overlapping parts of community structures in complex networks.

After literature search, M.E.J.Newman and M.Girvan found in the article "Community structure in social and biological networks [J]" ("Community structure in social and biological networks") (Proc.Natl.Acad.Sci.USA99,7821-7826(2001)) (Proceedings of the National Academy of Sciences) proposed a shortest path-based community mining method. This method first obtains the shortest path table of the entire network by calculating the shortest path between any two points in the network; Then recalculate the weight of each edge in the entire network; repeat the above steps until the entire network is divided into a reasonable community structure. The detection accuracy of this scheme is not high, the method complexity is high, and the community structure with overlap cannot be detected.

After searching, it was found that Filippo Radicchi and Claudio Castellano et al. wrote in the article "Defining and identifying communities in networks [J]" ("Defining and identifying communities in networks") (Proc.Natl.Acad.Sci.USA101,2658-2663(2004)) (USA Proceedings of the Chinese Academy of Sciences) proposed a community mining scheme based on local network topology. The method is as follows: firstly analyze the local topological characteristics of the community structure in the complex network, take the triangular structure in the network as the most basic structure of the network community, and count the number of triangular structures to which each edge in the network belongs as the weight of the edge ; Then, remove the edge with the largest weight in the network, and recalculate the weight of each edge in the entire network; repeat the above steps until the entire network is divided into a reasonable community structure. This scheme takes into account the local characteristics of the network topology, and the detection accuracy has been improved to a certain extent, but it still cannot solve the two problems of high complexity and overlapping community structure detection.

After searching, it was found that GergelyPalla and ImreDerenyi et al. published the article "Uncovering the overlapping community structure of complex network sinnature and society [J]" ("Mining the overlapping community structure in natural and social networks") (Nature435(7043), 814-818(2005)) (Nature) A community structure mining method based on complete subgraph is proposed. For each node in the complex network, first calculate all the complete subgraphs containing the node, and construct the overlap matrix of these complete subgraphs; then filter the overlap matrix according to the connectivity, so as to obtain the community structure with overlap. Although this method can mine overlapping community structures, it has no practical application value due to its high complexity.

Finally, after searching, it was found that U.N.Raghavan and R.Albert et al. wrote in the article "Nearlineartimealgorithmtodetectcommunitystructuresinlarge-scalenetworks[J]" (a method close to linear time complexity applied to community structure mining in large-scale networks) (Phys.Rev.E76 , 036106(2007)) (Physical Review) proposed a label propagation method applied to community structure mining. When the scheme is initialized, first assign an independent label to each node in the complex network; then update the label of each node to the label with the largest proportion among its neighbor nodes at each iteration, until all nodes in the network Stop iterating when the labels of all nodes no longer change. At this time, nodes with the same label belong to the same community structure. From this, the community structure of the complex network can be divided. The complexity of this method is very low, and it has nearly linear time complexity, which can be applied to large-scale complex networks. But this method has poor robustness, low detection accuracy, and cannot detect community structures with overlaps.

Contents of the invention

The object of the present invention is to propose a complex network community structure mining method based on triangular cluster multi-label propagation to address the above-mentioned deficiencies in the prior art. The main idea is to first find the core part of the community structure as the initial state of label propagation, and then use multi-label update rules in the label update to ensure the detection effect of the overlapping part of the community structure.

The present invention is achieved through the following technical solutions:

A complex network community mining method based on triangular cluster multi-label propagation, which is characterized in that: the method includes the following steps: searching for mutually disjoint triangular clusters in the network; setting different labels for nodes in different triangular clusters as labels The initial state of propagation; according to the multi-label update rule, for all nodes in the network, the propagation update of the label is carried out synchronously; the label array obtained after the update is compared with the previously updated label array; if the label is still propagating, then Continue to update; if the label oscillates, perform oscillation elimination processing before continuing to update; if the label does not change anymore, stop updating to obtain an overlapping community structure in the network.

The concrete steps of this method are as follows:

① Assign an empty label to each node of the complex network G to be tested;

②Calculate the triangular cluster coefficient TC(e _ij ) of each edge e _ij according to the following formula:

TC(e _ij )＝|N(v _i )∩N(v _j )|

Among them: N(v _i ) is the set of neighbor nodes of node v _i , ∩ is an operator for seeking intersection, |·| is an operator for seeking set base, i is 1, 2, 3, ..., N;

③ Search out the side with the largest triangular cluster coefficient;

④ Give all nodes in the triangular cluster of the edge a label with a cardinality of 1 that is different from other labels in the network; then delete these nodes from the network to obtain a new network G',

⑤ Determine whether there is an edge with a triangular cluster coefficient greater than 0, if it exists, then return to step ②, otherwise save the labels of all nodes in the network as a label array L ⁽⁰⁾ at this time, as the initial state of label propagation, enter step ⑥;

⑥ Use the following formula to synchronize the propagation and update of tags:

${\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; arg</span>}\underset{\mathrm{<span\; class="notranslate">\; l</span>}}{\mathrm{<span\; class="notranslate">\; max</span>}}\underset{{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; N</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">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; )</span>$

$\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; \&NotElement;</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\end{array}\right.$

in: is the label of node v _i after the tth update, t is a positive integer greater than 1, N(v _i ) is the set of neighbor nodes of node v _i , is the label of node v _i 's neighbor node v _j after the t-1th update, It is an operator for finding the set of elements l, and the obtained l makes the function defined after max obtain the maximum value. In the t-time update, using the label array L ^(t-1) obtained from the t-1-th update, for all nodes in the complex network G, according to the multi-label update rule, the label propagation update is performed synchronously, and saved to new label array L ^(t) ;

⑦Comparing the label array: compare the label array L ^(t) obtained by the t-th update with the label array L ⁽¹⁾ , L ⁽²⁾ ,...,L ^(t-1) obtained by the previous t-1 update,

When the label arrays of t times are not the same, return to step ⑥;

When L ⁽¹⁾ , L ⁽²⁾ ,...,L ^(t-2) has the same label array as L ^(t) , it will enter to indicate that the update has oscillated, and then proceed to step ⑧;

When the label array L ^(t-1) and L ^(t) are the same, go to step ⑨

⑧ Oscillation Elimination Processing: Assume that L ^(k) and L ^(t) are the same in the label array L ⁽¹⁾ , L ⁽²⁾ , ..., L ^(t-2) , then in the label array L ^(k+1) , ...,L ^(t) searches out all the nodes whose labels have changed from the k+1th update to the tth update, and replaces the labels of these nodes in L ^(t) with different labels from other labels in the network The label whose cardinality is 1; then return to step ⑥;

⑨ Obtain the overlapping community structure of the network, the nodes with the same label elements in the network belong to the same network community structure, and the nodes with label cardinality greater than 1 are the overlapping parts of the network community structure.

The technical solution of the present invention is described as follows:

1. Calculate the initial state of label propagation:

For the complex network G=(V,E) to be tested, where V={v _i |i=1,2,...,N} is the node set of the complex network G, v _i represents the i-th node, N is the number of nodes in the complex network, is the edge set of complex network G, e _ij = (v _i , v _j ) represents the edge connecting nodes v _i and v _j in the network, and is each node v _i (i=1,2,.. .,N) assigns an empty label. First, calculate the triangular cluster coefficient of each edge e _ij (i,j=1,2,...,N); then, search for the edge with the largest triangular cluster coefficient, and re- Set a label with a cardinality of 1 that is different from other labels in the network; then delete these nodes from the network to obtain a new network G'=(V',E');

Repeat the above process until there is no edge with a triangular cluster coefficient greater than 0 in the network, and save the labels of all nodes in the network at this time as a label array As the initial state propagated by labels, where Indicates the label of node vi when the label propagates the initial state;

2. Tag propagation update:

In the t-time update, using the label array L ^(t-1) obtained from the t-1-th update, for all nodes in the complex network G=(V,E), the label is updated synchronously according to the rule of multi-label update Propagate updates and save to new labels array $L^{\left(t\right)}=[L_1^t,L_2^t,...,L_i^t,...,L_N^t],$ in Indicates the label of node v _i after the tth update;

3. Tag array comparison:

Compare the label array L ^(t) obtained by the t-th update with the label array L ⁽¹⁾ , L ⁽²⁾ ,...,L ^(t-1) obtained by the previous t-1 update,

When the label arrays of t times are not the same, continue to update the labels according to step 2;

When L ⁽¹⁾ , L ⁽²⁾ ,...,L ^(t-2) has the same label array as L ^(t) , it indicates that there is oscillation in the update, and the oscillation elimination process must be performed, and then continue to follow step 2 Propagate and update labels;

When the label array L ^(t-1) and L ^(t) are the same, it means that the labels of all nodes in the network G=(V,E) will no longer change. At this time, the propagation update of the label is terminated, and the network has the same label The nodes of the elements belong to the same network community structure, and the nodes whose label cardinality is greater than 1 are the overlapping parts of the network community structure.

The initial state of the computed label propagation. For the complex network G=(V,E) to be tested, where V={v _i |i=1,2,..., N is the node set of the complex network G, vi represents the i-th node, and N is the complex The number of nodes in the network, E={e _ij =(v _i ,v _j )|i,j=1,2,...,N} is the edge set of complex network G, e _ij =(v _i ,v _j ) represents the edge connecting nodes v _i and v _j in the network, and assigns an empty label to each node v _i (i=1,2,...N) in the network G. First, calculate each edge e _ij (i,j=1,2,...,N) triangular cluster coefficient; then, search for the edge with the largest triangular cluster coefficient, and reset all nodes in the triangular cluster of the edge to a label different from other labels in the network Labels whose cardinality is 1; these nodes are then deleted from the network to obtain a new network G'=(V', E'). Repeat the above process until there is no edge with a triangular cluster coefficient greater than 0 in the network. This The labels of all nodes in the network are saved as a label array As the initial state propagated by labels, where Indicates the label of node v _i at the initial state of label propagation. Specifically:

The triangle cluster of edge e _ij refers to the topology structure composed of all triangles including edge e _ij in the network.

The triangular cluster coefficient of the edge e _ij refers to the number of all triangles including the edge e _ij in the network, and its calculation formula is as follows:

TC(e _ij )＝|N(v _i )∩N(v _j )|

Among them, TC(e _ij ) is the triangular cluster coefficient of edge e _ij , N(v _i ) is the set of neighbor nodes of node v _i , ∩ is an operator for intersection, and |·| is an operator for set base.

The neighbor nodes of the node v _i refer to the nodes in the network that have connection edges with the node v _i .

The cardinality of the set refers to the number of elements in the set.

The label of the node v _i is a set L _i ={ _{li ik} |k=1,2,...,K}, whose element _{li ik} is used to represent the number of the community structure to which the node v _i belongs, K is the base of the set. If the cardinality of the label is 1, it indicates that the node v _i only belongs to one community structure; if the cardinality of the label is greater than 1, the node v _i belongs to multiple community structures at the same time.

The empty label refers to a label whose set is an empty set, that is, a label whose cardinality is 0. If the label owned by the node is an empty label, it means that the node does not belong to any community structure.

The label array is a 1×N array for storing labels of all nodes in the network. Among them, N is the number of nodes in the network, Represents the labels owned by all nodes when labels propagate the initial state, The label owned by node v _i when propagating the initial state for the label; Indicates the labels owned by all nodes after the tth update, is the label owned by node v _i after the tth update.

The propagating update of the label. In the t-time update, using the label array L ^(t-1) obtained from the t-1-th update, for all nodes in the complex network G=(V,E), the label is updated synchronously according to the rule of multi-label update Propagate updates and save to new labels array in Indicates the label of node v _i after the tth update. Specifically:

The described multi-label update rule is:

${\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; arg</span>}\underset{\mathrm{<span\; class="notranslate">\; l</span>}}{\mathrm{<span\; class="notranslate">\; max</span>}}\underset{{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; N</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">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; )</span>$

$\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; \&NotElement;</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\end{array}\right.$

in, is the label of node v _i after the tth update, t is a positive integer greater than 1, N(v _i ) is the set of neighbor nodes of node v _i , is the label of node v _i 's neighbor node v _j after the t-1th update, It is an operator for finding the set of elements l, and the obtained l makes the function defined after max obtain the maximum value.

The synchronous label propagation update refers to updating the label of any node v _i for the tth time It can only be calculated from the label array L ⁽¹⁾ , L ⁽²⁾ ,…,L ^(t-1) obtained by the previous t-1 update, and any other node v _j (j ≠ i) label irrelevant.

The labeled arrays to compare. Compare the label array L ^(t) obtained by the t-th update with the label arrays L ⁽¹⁾ , L ⁽²⁾ , ..., L ^(t-1) obtained by the previous t-1 update. If the label arrays of t times are not the same, continue to follow step 2 to propagate and update the label; if L ⁽¹⁾ , L ⁽²⁾ , ..., L ^(t-2) have the same label as L ^(t) array, it indicates that the update has oscillated, and the oscillation elimination process must be performed, and then continue to follow step 2 to carry out the label propagation update; if the label array L ^(t-1) and L ^(t) are the same, it indicates that the network G=(V ,E) The labels of all nodes in E) are no longer changed. At this time, the propagation update of labels is terminated. The nodes with the same label elements in the network belong to the same network community structure, and the nodes with a label base greater than 1 are the network community structure. Overlap. Specifically:

The steps of the vibration elimination are as follows: assuming that L ^(k) and L ^(t) are the same in the label array L ⁽¹⁾ , L ⁽²⁾ , ..., L ^(t-2) , then in the label array L ^{( k+1)} ,...,L ^(t) , search out all the nodes whose labels have changed from the k+1th update to the tth update, and replace the labels of these nodes in L ^(t) with different The cardinality-1 label of other labels in the network.

The present invention improves the performance and effect of label propagation from three aspects. First, the core structure of the complex network community structure is a triangular cluster. The invention divides disjoint triangular clusters from the network, and assigns different labels as the initial state of label propagation, fully utilizes the topological characteristics of the complex network, and preliminarily constructs the basic shape of the community structure. The method of assigning different labels to nodes as starting states has been greatly optimized. Secondly, the present invention introduces a multi-label update rule, so that the label propagation update of each node makes full use of the label information of neighboring nodes, so that the local information of the node will not be lost. Compared with the update rule of randomly selecting the optimal label, more The label update rule greatly improves the robustness and accuracy of label propagation. Finally, the oscillation elimination process is used to reassign the label of the oscillation node, which better solves the oscillation problem in the synchronous update mode, and completely eliminates the randomness defect introduced by the update sequence of the nodes in the asynchronous update mode, and can pass parallel Computing, improving computing efficiency.

Description of drawings

Fig. 1 is a flow chart of the method of the present invention.

Figure 2 is a schematic diagram of the initial state of label propagation under the karate club network of this method.

Figure 3 is a schematic diagram of the overlapping community structure obtained by this method under the karate club network.

detailed description

The embodiments of the present invention are described in detail below. This embodiment is implemented on the premise of the technical solution of the present invention, and detailed implementation methods and specific operating procedures are provided, but the protection scope of the present invention is not limited to the following implementation example.

This embodiment adopts the Zachary karate club network, a classic data set in social networks, which contains 34 nodes and 78 edges. The specific steps are as follows:

① Assign an empty label to each node of the karate club network to be tested;

②Calculate the triangular cluster coefficient TC(e _ij ) of each edge ej according to the following formula:

TC(e _ij )＝|N(v _i )∩N(v _j )|

Among them: N(v _i ) is the set of neighbor nodes of node v _i , ∩ is an operator for seeking intersection, |·| is an operator for seeking set base, i is 1, 2, 3, ..., N;

③ Search out the side with the largest triangular cluster coefficient;

④ Give all nodes in the triangular cluster of the edge a label with a cardinality of 1 that is different from other labels in the network; then delete these nodes from the network to obtain a new network G',

⑤ Determine whether there is an edge with a triangular cluster coefficient greater than 0, if it exists, then return to step ②, otherwise save the labels of all nodes in the network as a label array L ⁽⁰⁾ at this time, as the initial state of label propagation, enter step ⑥;

The label array L ⁽⁰⁾ of the initial state of label propagation obtained from step ⑤ contains three different non-empty labels l ₁ , l ₂ and l ₃ , corresponding to the three disjoint triangular clusters in the karate club network , as shown in Figure 2, where each label is represented by a circle, nodes in different circles have different non-empty labels, and blank nodes represent nodes with empty labels.

⑥ Use the following formula to synchronize the propagation and update of labels:

${\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; arg</span>}\underset{\mathrm{<span\; class="notranslate">\; l</span>}}{\mathrm{<span\; class="notranslate">\; max</span>}}\underset{{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; N</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">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; )</span>$

$\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; \&NotElement;</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\end{array}\right.$

in: is the label of node v _i after the tth update, t is a positive integer greater than 1, N(v _i ) is the set of neighbor nodes of node v _i , is the label of node v _i 's neighbor node v _j after the t-1th update, It is an operator for finding the set of elements l. The obtained l makes the function defined after max obtain the maximum value. When the t-th update is performed, the label array L ^(t-1) obtained by the t-1th update is used. , for all nodes in the complex network G, according to the rule of multi-label update, the label is propagated and updated synchronously, and saved to a new label array L ^(t) ;

⑦Comparing the label array: compare the label array L ^(t) obtained by the t-th update with the label array L ⁽¹⁾ , L ⁽²⁾ ,...,L ^(t-1) obtained by the previous t-1 update,

When the label arrays of t times are not the same, return to step ⑥;

When L ⁽¹⁾ , L ⁽²⁾ ,...,L ^(t-2) has the same label array as L ^(t) , it will enter to indicate that the update has oscillated, and then proceed to step ⑧;

When the label array L ^(t-1) and L ^(t) are the same, go to step ⑨

⑧ Oscillation Elimination Processing: Assume that L ^(k) and L ^(t) are the same in the label array L ⁽¹⁾ , L ⁽²⁾ , ..., L ^(t-2) , then in the label array L ^(k+1) , ...,L ^(t) searches out all the nodes whose labels have changed from the k+1th update to the tth update, and replaces the labels of these nodes in L ^(t) with different labels from other labels in the network The label whose cardinality is 1; then return to step ⑥;

⑨ Obtain the overlapping community structure of the network, the nodes with the same label elements in the network belong to the same network community structure, and the nodes with the label cardinality greater than 1 are the overlapping parts of the network community structure.

Using this method, the label array L ⁽²⁾ obtained after the second update is the same as the label array L ⁽¹⁾ obtained after the first update, so the propagation update of the label is terminated, and the overlapping communities of the karate club network are obtained structure, as shown in Figure 3. It can be seen that there are three community structures C ₁ , C ₂ and C ₃ in the karate club network, each represented by a circle, and the nodes in the circle are the member nodes of the community structure; nodes 5, 10 and 11 are community The overlapping parts of the structures are represented by black nodes; community structures C ₁ and C ₂ share nodes 5 and 11, and communities C ₂ and C ₃ share node 10.

The above experiments use typical network data sets to describe the flow of the method of the present invention in detail. The experimental results are basically consistent with the background knowledge of the dataset, and the proportion of nodes classified into the correct community structure reaches 95.59%. In addition, modularity is a very important index parameter used to measure the quality of the community structure. After calculation, the modularity of the community structure obtained by this method under the karate club network is 0.3912, which is very close to the theoretical maximum value of 0.4020, which is The accuracy and effectiveness of this method are also verified.

Claims (1)

1. A complex network community mining method based on triangular cluster multi-label propagation, comprising the following steps: searching for disjoint triangular clusters in the network; setting different labels for nodes in different triangular clusters as the starting point of label propagation Status; according to the multi-label update rule, for all nodes in the network, the label propagation update is performed synchronously; the updated label array is compared with the previously updated label array; if the label is still propagating, continue to update; If the label oscillates, continue to update after performing oscillation elimination processing; if the label no longer changes, then stop updating to obtain an overlapping community structure in the network, characterized in that: the specific steps of the method are as follows: ① Assign an empty label to each node of the complex network G to be tested; ②Calculate the triangular cluster coefficient TC(e _ij ) of each edge e _ij according to the following formula: TC(e _ij )＝|N(v _i )∩N(v _j )| Among them: N(v _i ) is the set of neighbor nodes of node v _i , ∩ is an operator for seeking intersection, |·| is an operator for seeking set base, i is 1, 2, 3, ..., N; ③ Search out the side with the largest triangular cluster coefficient; ④ Give all nodes in the triangular cluster of the edge a label with a cardinality of 1 that is different from other labels in the network; then delete these nodes from the network to obtain a new network G', ⑤ Determine whether there is an edge with a triangular cluster coefficient greater than 0, if it exists, then return to step ②, otherwise save the labels of all nodes in the network as a label array L ⁽⁰⁾ at this time, as the initial state of label propagation, enter step ⑥; ⑥ Use the following formula to synchronize the propagation and update of labels: ${\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; arg</span>}\underset{\mathrm{<span\; class="notranslate">\; l</span>}}{\mathrm{<span\; class="notranslate">\; max</span>}}\underset{{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; N</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">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; )</span>$ $\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; \&NotElement;</span>{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\end{array}\right.$ in: is the label of node v _i after the tth update, t is a positive integer greater than 1, N(v _i ) is the set of neighbor nodes of node v _i , is the label of the neighbor node v _j of node v _i after the t-1th update, |·| is an operator for calculating the cardinality of the set, It is an operator for finding the set of elements l. The obtained l makes the function defined after max obtain the maximum value. When the t-th update is performed, the label array L ^(t-1) obtained by the t-1th update is used. , for all nodes in the complex network G, according to the rule of multi-label update, the label is propagated and updated synchronously, and saved to a new label array L ^(t) ; ⑦Comparing the label array: compare the label array L ^(t) obtained by the t-th update with the label array L ⁽¹⁾ , L ⁽²⁾ ,...,L ^(t-1) obtained by the previous t-1 update, When the label arrays of t times are not the same, return to step ⑥; When L ⁽¹⁾ , L ⁽²⁾ ,...,L ^(t-2) has the same label array as L ^(t) , it will enter to indicate that the update has oscillated, and then proceed to step ⑧; When the label array L ^(t-1) and L ^(t) are the same, enter step ⑨; ⑧ Oscillation Elimination Processing: Assume that L ^(k) and L ^(t) are the same in the label array L ⁽¹⁾ , L ⁽²⁾ ,...,L ^(t-2) , then in the label array L ^(k+1) , ...,L ^(t) searches out all the nodes whose labels have changed from the k+1th update to the tth update, and replaces the labels of these nodes in L ^(t) with different labels from other labels in the network The label whose cardinality is 1; then return to step ⑥; ⑨ Obtain the overlapping community structure of the network, the nodes with the same label elements in the network belong to the same network community structure, and the nodes with label cardinality greater than 1 are the overlapping parts of the network community structure.