CN111507506A - Consensus embedding-based complex network community discovery method - Google Patents

Abstract

A consensus embedding-based complex network community discovery method relates to a multi-objective optimization technology. The method comprises the following steps: 1) giving a maximum algebra maxgen and a particle swarm size pop; 2) given network G ═ V, E, the network size is n, carry on the network and represent and study; 3) representing a learning result by using a network, initializing a particle swarm to obtain 100 particles POP, wherein the iteration number t is 1; 4) carrying out updating and mutation based on consensus embedding on the POP; 5) stopping conditions are as follows: and if t is not more than maxgen, t ← t +1 and go to step 3), otherwise, stopping and returning pareto front edge solution, namely a plurality of community division results. The updating process is more efficient and accurate, and the obtained pareto frontier effect is more competitive; the accuracy rate of community discovery is improved, the convergence time of the method is effectively reduced, and the method has good practicability in practical application of function prediction, recommendation systems and the like.

Description

A Community Discovery Method for Complex Networks Based on Consensus Embedding

technical field

The invention relates to a multi-objective optimization technology, in particular to a complex network community discovery method based on consensus embedding, which can be applied to the fields of function prediction, recommendation system and the like.

Background technique

A network with some or all of the properties of self-organization, self-similarity, attractor, small world, and scale-free is called a complex network. In a complex network, there are many connections between the same type of nodes, forming a small community, and there are fewer connections between different types of nodes, but these connections will become an important channel for communication between different communities.

In order to explore the structural characteristics of complex networks and then understand the functions of complex networks, people have carried out extensive research on the community structure of complex networks, and proposed many community discovery methods, which are mainly divided into four methods: agglomeration method, splitting method, and optimization method. and simulation methods. Among the many methods, these four methods are not independent, and one method may reflect multiple ideas at the same time.

Complex network community discovery methods are widely used in many basic applications, such as recommender systems, disease prediction and prevention, etc. A particle can be defined as a solution in a multi-objective particle swarm, and each solution can represent a kind of community partition in a complex network. In recent years, the multi-objective optimization method has achieved good success, so it is of great significance to improve the multi-objective particle swarm optimization. Among the representative methods are Maoguo Gong et al. (M.Gong, Q.Cai, X.Chen, and L.Ma, "Complex network clustering by multiobjectivediscrete particle swarm optimization based on decomposition," IEEE Transactions on Evolutionary Computation, vol.18, no.1, pp.82–97, 2014) Application of Decomposition-Based Multi-objective Discrete Particle Swarm Optimization to Complex Network Clustering (MODPSO). However, when the algorithm is initialized, a large number of useless solutions are generated, which makes the search space too large and the redundancy is very high. The algorithm can only perform well in relatively small networks, and does not perform well in large-scale networks.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a complex network community discovery method based on consensus embedding, aiming at the problems of the prior art such as too slow convergence speed, a large number of redundant solutions, and no deep mining of the underlying structure information hidden in the network.

The present invention includes the following steps:

1) Given the maximum algebra maxgen, the particle swarm size pop;

2) Given a network G=(V, E), the network scale is n, and network representation learning is performed;

3) Using the network to represent the learning results, initialize the particle swarm to obtain 100 particle POPs, and the number of iterations is t=1;

4) Update and mutate POP based on consensus embedding;

5) Stop condition: if t≤maxgen is satisfied, then t←t+1 and turn to step 3), otherwise stop and return to the Pareto frontier solution, that is, the result of dividing multiple communities.

In step 2), the specific steps of performing network representation learning may be:

Using the network embedding method AROPE which preserves the similarity of any order based on singular value decomposition and eigenvalue decomposition framework, the high-dimensional adjacency matrix is mapped to the low-dimensional continuous feature space, and the underlying structural information hidden in the network is mined to obtain nodes. The feature vector E={e ₁ ,e ₂ ,e ₃ ,...,e _n }, where e _i ={e _i1 ,e _i2 ,e _i3 ,...,e _id }, d is the dimension reduction dimension.

In step 3), the specific steps of using the network to represent the learning result and initializing the particle swarm to obtain 100 particle POPs are:

利用k-means得到基于相似度的初始化的粒子群POP^t＝{x₁,x₂,x₃,...,x_pop}^t；粒子的局部最优解也初始化为Pbest＝POP^t。Calculate the similarity to get

The initialized particle swarm POP ^t ={x ₁ ,x ₂ ,x ₃ ,...,x _pop } ^t is obtained by using k-means; the local optimal solution of the particle is also initialized as Pbest=POP ^t .

In step 4), the specific steps for updating and mutating the POP based on consensus embedding are:

Consensus-based updates in each generation;

Consensus embedding every 10 generations;

Neighborhood-based single-point mutation of particles with mutation probability pm is performed in each generation.

Iterates the particle update mutation process for maxgen times.

When consensus-based updates are performed in each generation, the community in gbest is used as consensus, and one of them is randomly selected to be embedded in the current particle; when consensus embedding is performed every 10 generations, the features in the current particle swarm are extracted every 10 generations. solution, extract all two-node communities from it, and vote in the current particle swarm. If the support is ≥ 70%, it is selected as a consensus community and all embedded in the current particle;

Among them, the characteristic solutions extracted from the solution set are three representative solutions, namely:

a. The solution with minimal KKM

b. The solution with minimal RC

c. Local knee solution with minimum Manhattan distance

When performing neighborhood-based single-point mutation of particles with mutation probability pm in each generation, for each particle that needs to be mutated, a position i is randomly selected, and its label is replaced with another label in its neighborhood. The generation of new possible solutions is guaranteed.

The objective function adopted in the present invention is a variant of KKM and RC:

所以

和

是集合V_h中节点的内部和外部相似度之和，“|·|”表示集合的大小。where V _h ∈ V,

so

and

is the sum of the internal and external similarity of nodes in the set V _h , and “|·|” represents the size of the set.

The non-dominated sorting selection strategy is adopted in the selection process of particles.

Compared with the prior art, the present invention has the following outstanding technical effects:

Compared with the evolution process of MODPSO, the update method of the algorithm particles of the complex network community discovery based on consensus embedding proposed by the present invention is different, and the update process is more efficient and accurate. The experimental data also show that the Pareto front effect obtained by the method of the present invention is more competitive; the convergence time required by the present invention is also less. The method of the invention improves the accuracy rate of community discovery, and at the same time can effectively reduce the convergence time of the method, and has good practicability in practical applications such as function prediction and recommendation system. For example, in the biological field, the analysis of the metabolic network, the analysis of the gene regulation network, and the identification of the master gene; in the field of disease transmission and evolution, prediction and prevention, find out the key communities and key nodes of infectious diseases to predict the transmission route and cut off the transmission route in time. ; Realize the precise placement of advertisements in the Internet, establish a more reliable recommendation system on the e-commerce system, and provide more personalized search results in the search engine.

Description of drawings

Figure 1 is a schematic diagram of how particles are updated in each generation.

Figure 2 is a schematic diagram of the update method based on consensus embedding of particles every 10 generations.

FIG. 3 is a comparison diagram of the running time of the method of the present invention (NE-PSO) and the MODPSO algorithm on a small-scale network dataset.

Figure 4. Line graph of the running time of the method of the present invention (NE-PSO) on a large-scale network dataset.

Detailed ways

The following embodiments will further illustrate the present invention in conjunction with the accompanying drawings.

The embodiment of the method for discovering complex network communities based on consensus embedding according to the present invention specifically includes the following steps:

1) Given network G=(V, E), maximum algebra maxgen, particle swarm size pop, network size n, mutation probability pm;

2) Using the network embedding method AROPE that retains any order similarity based on singular value decomposition and eigenvalue decomposition framework, network representation learning is performed on the network G, and the high-dimensional adjacency matrix is mapped into the low-dimensional continuous feature space, and the network is mined. The underlying structure information hidden in the node is obtained, and the feature vector E={e ₁ ,e ₂ ,e ₃ ,..., _{en } of the node is obtained, where e i =} {e _i1 ,e _i2 ,e _i3 ,..., e _id }, d is the dimension after dimension reduction;

利用k-means得到基于相似度的初始化的粒子群POP^t＝{x₁,x₂,x₃,...,x_pop}^t；粒子的局部最优解也初始化为Pbest＝POP^t；迭代次数t＝1；3) Using the network to represent the learning results and the feature vectors of nodes, calculate the cos similarity between nodes to get

Using k-means to obtain the initialized particle swarm POP ^t ={x ₁ ,x ₂ ,x ₃ ,...,x _pop } ^t based on similarity; the local optimal solution of the particle is also initialized as Pbest=POP ^t ; iterative times t=1;

4) Update and mutate POP based on consensus embedding, where:

Perform consensus-based updates in each generation (as shown in Figure 1), take the community in gbest as consensus, and randomly select one of them to embed into the current particle;

Consensus embedding is performed every 10 generations (as shown in Figure 2), the feature solution in the current particle swarm is extracted every 10 generations, all two-node communities are extracted from it, and voting is performed in the current particle swarm. Set as a consensus community, all embedded in the current particle;

In each generation, a neighborhood-based single-point mutation is performed on the particles with the mutation probability pm. For each particle that needs to be mutated, a position i is randomly selected, and its label is replaced by another label in its neighborhood, which ensures that generation of new possible solutions.

5) Stop condition: if t≤maxgen is satisfied, then t←t+1 and turn to step 3, otherwise stop the algorithm and return to the Pareto frontier solution, that is, the result of multiple community divisions.

Figure 1 is a schematic diagram of how particles are updated in each generation. In each generation update, all particles will be sorted according to the non-dominant relationship to maintain a global optimal solution gbest. The communities divided in gbest can be regarded as a consensus community, and the particles of the current generation are randomly embedded by a consensus community , and make a non-dominated sorting selection with the original particle, and what is left is the new particle generated.

Figure 2 is a schematic diagram of the update method based on consensus embedding of particles every 10 generations. In the update every 10 generations, in the Pareto frontier composed of all particles, select the local knee points (ie extreme points), KKM minimum points, RC minimum points, and extract consensus among these h points community (the support degree set in the present invention is 70%), and the obtained consensus community is embedded into all particles of the current generation, and all particles are updated.

Table 1 presents the comparison of the modularity Q (maximum and average) of the method of the present invention (NE-PSO) with other benchmark algorithms on 11 real-world network datasets.

Table 1

Note: "——" indicates that the corresponding method cannot get the result within the given time. "?" indicates that the corresponding method is not disclosed, resulting in unknown experimental results.

It can be seen from Table 1 that the method of the present invention has better effects than other benchmark algorithms in 9 of the 11 data sets used, especially in the data set with many network nodes. And according to the line graphs of running time on small-scale network datasets and large-scale network datasets in Figures 3 and 4, it can be seen that NE-PSO also significantly reduces the convergence time of multi-objective particle swarm optimization. Therefore, the present invention improves the accuracy of community discovery, and at the same time can effectively reduce the algorithm convergence time, and has good practicability in practical applications.

The above-mentioned embodiments are only preferred embodiments of the present invention, and should not be construed as limiting the scope of implementation of the present invention. All equivalent changes and improvements made according to the scope of the application of the present invention should still belong to the scope of the patent of the present invention.

Claims (5)

1. A consensus embedding-based complex network community discovery method is characterized by comprising the following steps:

1) giving a maximum algebra maxgen and a particle swarm size pop;

2) given network G ═ V, E, the network size is n, carry on the network and represent and study;

3) representing a learning result by using a network, initializing a particle swarm to obtain 100 particles POP, wherein the iteration number t is 1;

4) carrying out updating and mutation based on consensus embedding on the POP;

5) stopping conditions are as follows: and if t is not more than maxgen, t ← t +1 and go to step 3), otherwise, stopping and returning pareto front edge solution, namely a plurality of community division results.

2. The method for discovering complex web communities based on consensus embedding as claimed in claim 1, wherein in step 2), the specific steps of performing web representation learning are:

the method comprises the steps of adopting a network embedding method AROPE based on singular value decomposition and eigenvalue decomposition frames and keeping any order of similarity, mapping a high-dimensional adjacent matrix into a low-dimensional continuous eigenspace, mining underlying structure information hidden in a network, and obtaining an eigenvector E ═ { E } of a node₁,e₂,e₃,...,e_nIn which e_i＝{e_i1,e_i2,e_i3,...,e_idD is the dimensionality after dimensionality reduction.

3. The method as claimed in claim 1, wherein in step 3), the specific steps of using the network to represent the learning result and performing initialization of the particle swarm to obtain 100 particle POPs are as follows:

calculating similarity to obtain S ═ S_ij)_n*n(ii) a Particle swarm POP capable of obtaining initialization based on similarity by using k-means^t＝{x₁,x₂,x₃,...,x_pop}^t(ii) a The local optimal solution for the particle is also initialized to Pbest ═ POP^t。

4. The method as claimed in claim 1, wherein in step 4), the step of updating and mutating the POP based on consensus embedding comprises:

performing consensus-based updates in each generation;

performing consensus embedding every 10 generations;

and performing neighborhood-based single-point mutation on the particles with mutation probability of pm in each generation.

5. The method for discovering complex network communities based on consensus embedding as claimed in claim 1, wherein in step 4), the updating and mutation iterates the updating and mutation process of the particles for maxgen times;

when updating based on consensus is carried out in each generation, taking the communities in the gbest as consensus, and randomly selecting one of the communities to be embedded into the current particle; when the consensus embedding is carried out every 10 generations, extracting the characteristic solution in the current particle swarm every 10 generations, extracting all two-node communities from the characteristic solution, voting in the current particle swarm, and if the support degree is more than or equal to 70%, selecting the characteristic solution as the consensus community and completely embedding the characteristic solution into the current particle;

wherein, the characteristic solutions extracted from the solution set are three representative solutions, which are respectively:

(1) solutions with minimum KKM

(2) Solutions with minimum RC

(3) Local knee solution with minimum manhattan distance

When single-point variation based on neighborhood is carried out on the particles with variation probability pm in each generation, a position i is randomly selected for each particle needing variation, and the label of the position i is replaced by another label in the neighborhood, so that the generation of a new possible solution is ensured.

Images