CN115049002A - Complex network influence node identification method based on reverse generation network - Google Patents

Abstract

The invention provides a complex network influence node identification method based on a reverse generation network, which comprises the following steps: s1, community division: carrying out community division on the network by using a Louvain algorithm; s2, generating a candidate node set: node information is collected by using graph traversal so as to assist in constructing an improved reverse generation network, and then a part of nodes are selected to be added into a candidate node set; s3, selecting a seed node: and finding out the final k influential nodes from the candidate node set as seed nodes. The method can select key nodes in the network or nodes for maintaining the stability of the network as candidate nodes, the seed nodes selected by the method have higher infection speed and larger infection scale, and the seed node sets are dispersed on most networks.

Description

Influence node identification method of complex network based on reverse generative network

technical field

The present invention relates to the technical field of influence node identification, in particular to a complex network influence node identification method based on reverse generation network.

Background technique

The prosperity of network science has led to a new wave of identifying a set of influential nodes in complex networks. Many real-life fields, including biology, physics, sociology, engineering, etc., can be represented by complex networks. The key nodes or influential nodes in the network can be used to maintain the stability of the network topology and determine the efficiency of information transmission such as rumors in the network. These nodes directly determine whether the network can operate normally. These nodes are usually referred to as influence nodes. Identifying a group of influential nodes in the network is a classical influence maximization problem. Strengthening the control of influential nodes provides new opportunities for accelerating information dissemination, which is of great significance for viral marketing, identification of drug targets and essential proteins, and rumor control. For example, in word-of-mouth marketing, selecting the most influential Users can promote it to ensure that the least budget is spent to achieve the maximum communication effect, or, for example, by detecting the source of public opinion transmission in the social network, it can control the transmission of public opinion. With the advent of the era of big data and 5G, the types and scales of networks have also grown rapidly, which poses new challenges to the old method of measuring the influence of nodes.

Influence node identification methods based on community discovery have attracted extensive attention of network science researchers in recent years. However, the existing methods simply take advantage of the feature of community structure, and some methods based on three-stage method have some shortcomings in selecting candidate node sets and seed nodes. First, existing methods such as random walk, genetic algorithm or some other heuristic algorithms need to traverse the entire network when selecting the candidate node set, and the selected candidate nodes may gather with each other. If seed nodes are selected from these candidate node sets, there may be a problem of overlapping influence ranges. Therefore, the generation of candidate node sets is particularly important in the entire seed node selection process. Secondly, in the stage of seed node identification, a large number of algorithms use greedy algorithms for accurate selection. Although the selection in the generated candidate node set has greatly improved the operation efficiency, it is also time-consuming.

SUMMARY OF THE INVENTION

The present invention aims to at least solve the technical problems existing in the prior art, and particularly innovatively proposes a complex network influence node identification method based on a reverse generation network.

In order to realize the above-mentioned purpose of the present invention, the present invention provides a kind of complex network influence node identification method based on reverse generation network, comprises the following steps:

S1, community division: use the Louvain algorithm to divide the community into the network to reduce the search space of seed nodes;

S2, candidate node set generation: use graph traversal to collect node information to assist in constructing an improved reverse generation network. In this method, high-importance nodes can be selected without restoring the original network when building the network; node set;

S3, select seed nodes: find the final k influential nodes from the candidate node set as seed nodes.

Further, the scale of the community at least meets the following conditions:

C_size=size(G)*η (9)

where C_size represents the community size;

size(G) represents the number of nodes in network G;

η is a tunable parameter that controls the size of the community that satisfies the condition.

Further, the S2 includes:

S2-1, calculate the joining cost of the remaining nodes, and select the node that minimizes the cost function to build the network. The cost function is:

where cost(u,n+1) represents the cost function of node u at the (n+1) ^th time step;

表示在(n+1)^th时间步，将节点u加入到网络G中的最大连通分量的大小，即

Represents the size of the largest connected component that adds node u to the network G at the (n+1) ^th time step, i.e.

AUC _u represents the AUC value of node u;

AUC _max represents the largest AUC value among all nodes;

AUC _min represents the smallest AUC value among all nodes;

ξ is a sufficiently small positive parameter;

S2-2, after adding a node, it is necessary to update the size of each connected component in the network, and record the size of the largest connected component in the network;

S2-3, repeat steps S2-1 to S2-2 until the number of remaining nodes meets the required number of candidate nodes, and at the same time stop constructing the network.

Using the improved reverse generative network to generate candidate node sets has the following advantages. First, the generated candidate node sets can be more dispersed, with a small number of nodes aggregated, and all of them are key nodes in the network. Second, the influence range of the selected candidate nodes has a low degree of overlap. In the third stage, the heuristic method and the greedy method can also be used to balance the selection of seed nodes. Third, these candidate nodes ensure the robustness of the network, and removing these nodes will easily cause the network to collapse. Fourth, it is not necessary to traverse the entire network when generating candidate nodes, and the network construction can be stopped when the number of unjoined nodes meets the number of candidate node sets.

Further, the S2 also includes:

In order to further narrow the search range and ensure that there are candidate nodes with suitable quality, the size of the candidate node set is set in the independent network formed by each community, and the formula is as follows:

where cand_num _i represents the size of the i-th community candidate node set;

(C_size _i -C_size _min )/(C_size _max -C_size _min ) represents the proportion of the i-th community in all selected communities;

β is an amplification parameter;

k is the final number of seed nodes to be selected.

Further, the graph traversal includes:

The degree centrality is selected as the initial center score in graph traversal, and the degree centrality is optimized by the graph traversal framework to generate a more fine-grained AUC score that measures the influence of nodes.

Further, the S3 includes:

S3-1, select k ₁ nodes in the candidate node set through the degree discount algorithm;

The calculation formula of the degree discount algorithm is:

where gdd _v represents the degree discount of node v;

d _v represents the degree of node v;

t _v represents the number of infected neighbors of node v;

t _w represents the number of infected neighbors of node w's susceptible neighbor node w;

p represents the infection probability;

S3-2, select k ₂ nodes through the improved submodularity algorithm;

k ₂ =kk ₁ (13)

Where k is the number of seed nodes that need to be selected in the end;

μ is a tunable parameter to balance greedy and heuristic algorithms;

c represents the total number of communities in the network that meet a certain size;

cand_num _i represents the size of the ith community candidate node set;

The specific steps for selecting k ₂ nodes by the improved submodularity algorithm are as follows: if the node u selected in each round of the improved submodularity algorithm selection process is similar to the node selected before or the node selected by the heuristic process, then The node is not selected and removed from the candidate node set.

Compared with the original submodularity algorithm, the improved submodularity algorithm further considers the position information of nodes and the structural similarity between nodes.

Further, the similarity is to judge whether the nodes are similar by the following formula, if the following formula is satisfied, then the node u and the node v are similar;

where sim represents the similarity between node u and node v;

N(u) represents the set of neighbor nodes of node u;

N(v) represents the set of neighbor nodes of node v;

N(u)∩N(v) represents the number of neighbors shared by N(u) and N(v);

|·| indicates the number of sets;

ε is a parameter approaching 0;

abs( ) means to take the absolute value;

ks(u) is the normalized k-shell index of node u;

ks(v) is the normalized k-shell index of node v.

Further, it also includes evaluating the method by the following performance indicators: robustness value, cumulative distribution function, SIR model, and average shortest path length. The four performance indicators can comprehensively judge whether the method is reasonable.

To sum up, due to the adoption of the above technical solutions, the advantages of the present invention are as follows:

(1) Using the influence score to assist in constructing the reverse generation network, the generated network does not have to be restored to the original network, and the nodes not added to the network are directly added to the candidate node set, which greatly reduces the computing time.

(2) Considering that the common neighbors and positional relationship between nodes will overlap the influence range of the selected node set, an improved CELF algorithm is proposed.

(3) Considering the community structure of the network, using the community to accelerate the algorithm, and combining the network connectivity, graph traversal, and the advantages of heuristic algorithm and greedy algorithm.

Therefore, the present invention can better select key nodes in the network or nodes that maintain network stability as candidate nodes, and the seed node selected by the proposed method has a faster infection speed and a larger infection scale, and the seed node set is between the Most of the network is decentralized.

Additional aspects and advantages of the present invention will, in part, be set forth in the description that follows, and in part will become apparent from the description, or will be learned by practice of the invention.

Description of drawings

The above and/or additional aspects and advantages of the present invention will become apparent and readily understood from the following description of embodiments in conjunction with the accompanying drawings, wherein:

FIG. 1 is a graph of the robustness value R of the present invention.

Fig. 2 is a schematic diagram of graph traversal centrality of the present invention.

FIG. 3 is an overall schematic diagram of the CBGN framework of the present invention.

Figure 4 is a schematic diagram of a toy network of the present invention.

Fig. 5 is a degree distribution diagram of six experimental networks of the present invention.

Fig. 6 is the R curve diagram of 6 real networks of the present invention under different methods.

Fig. 7 is the R curve in two real network communities of the present invention.

FIG. 8 is a CDF distribution diagram of Degree and TARank_degree of the present invention on three networks.

FIG. 9 is a schematic diagram of the propagation influence of seed nodes selected by different algorithms of the present invention under the SIR model.

FIG. 10 is a schematic diagram of the transmission scale of the present invention under different infection rates.

Detailed ways

The following describes in detail the embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein the same or similar reference numerals refer to the same or similar elements or elements having the same or similar functions throughout. The embodiments described below with reference to the accompanying drawings are exemplary, only used to explain the present invention, and should not be construed as a limitation of the present invention.

The present invention provides a complex network influence node identification method based on reverse generation network, and its specific embodiments are as follows:

S1, divide the public opinion network into a community: use the Louvain algorithm to divide the public opinion network into a community to reduce the search space of the public opinion seed nodes;

S2, public opinion candidate node set generation: use graph traversal to collect public opinion node information to assist in constructing an improved reverse generation network. In this method, high-importance nodes can be selected without restoring the original network when constructing the network; then select some nodes Join the public opinion candidate node set;

S3, select the public opinion seed nodes: find the final k influential nodes from the public opinion candidate node set as the public opinion seed nodes.

It is only necessary to control the speech of the users corresponding to the selected public opinion seed nodes, and the spread of public opinion can be quickly controlled.

1. Introduction of related content

1.1 Background

The prosperity of network science has led to a new wave of identifying a set of influential nodes in complex networks. Many real-life fields, including biology, physics, sociology, engineering, etc., can be represented by complex networks. The key nodes or influential nodes in the network can be used to maintain the stability of the network topology and determine the efficiency of information transmission such as rumors in the network. These nodes directly determine whether the network can operate normally. These nodes are usually referred to as influence nodes. Identifying a group of influential nodes in the network is a classical influence maximization problem. Strengthening the control of influential nodes provides new opportunities for accelerating information dissemination, which is of great significance for viral marketing, identification of drug targets and essential proteins, and rumor control. For example, in word-of-mouth marketing, selecting the most influential Users can promote it to ensure that the least budget is spent to achieve the maximum communication effect, or, for example, by detecting the source of public opinion transmission in the social network, it can control the transmission of public opinion. With the advent of the era of big data and 5G, the types and scales of networks have also grown rapidly, which poses new challenges to the old method of measuring the influence of nodes.

The influence maximization problem was first studied by Domingos and Richardson, and in 2003 Kempe et al. formalized the problem as a discrete optimization problem, which was proved to be NP-hard. In order to efficiently obtain influential nodes and measure nodes from different perspectives, a large number of indicators have been proposed one after another, such asDegree, ClusterRank, K-shell, H-index, NeighborhoodCoreness, PageRank, DegreeDiscount, etc. Simply using height centrality to select a group of nodes often results in overlapping influence ranges, and direct selection of nodes such as K-shell and H-index also has the problem of low solution accuracy. The PageRank algorithm considers both the number and quality of nodes, but specification leakage occurs when dangling pages appear. ClusterRank also considers the direct neighbors of nodes and their clustering coefficients, and also lacks performance guarantees due to the consideration of local network information. Bae et al. envisaged that when a node has more neighbor nodes located at the core of the network, the propagation range is wider, and proposed the neighborhood kernel centrality, which balances the degree and position relationship of the node and effectively improves the K-shell Degeneracy of methods. There are also many combinations of network topology to heuristically select nodes, Beni et al. proposed an IMT algorithm to select seed nodes from dense parts of the graph in order to visit more nodes within the shortest distance. Considering local neighbor information and global community information, Zhang et al. designed a Constrained Evolutionary Algorithm (IICEA) based on the local-global influence index, which effectively solved the problem of budget influence constraints. Mao et al. proposed a topological latent scheme for predicting influential nodes in large-scale online social networks. Although based on the centrality of the network topology, it is possible to find influential nodes in a relatively short time, but such algorithms are often not stable enough and the solution quality is not high.

In recent decades, some classic greedy algorithms have been proposed, such as the greedy algorithm that sequentially selects the node with the largest marginal gain, and the improved CELF and CELF++ algorithms. Although the influence diffusion of these algorithms approximates the optimal solution within the factor (1-1/e-ε), where ε is a small parameter approaching 0, and e is the natural base, these algorithms require tens of thousands of iterations. Monte Carlo simulations incur long computation times, making it difficult to scale to large networks. In order to solve this phenomenon, a large number of network science researchers have proposed heuristic algorithms for specific fields, sacrificing a certain accuracy rate to greatly reduce the computational complexity. In recent years, a new indicator, Robustnessvalue, has been widely used to measure the importance of nodes. Robustness originates from the well-known penetration theory, which states that when a part of the network is removed, the network collapses. The robustness value is used to measure the connectivity of the network, and a smaller robustness value means better performance of the algorithm. Compared with traditional methods, all nodes need to be sorted, and robustness only considers the importance of all nodes in the network. In addition, community is also an important structure in network science. Compared with different communities, nodes in the same community may be connected more frequently. A large number of community-based influence maximization algorithms have been proposed, proving the effectiveness of community division.

Based on the above discussion, in the patent of the present invention, a new community-based Backward Generating Networks (CBGN) method is proposed to identify a group of influential nodes in a complex network, which includes three steps: (1) community division; (2) candidate set generation; (3) selection of seed nodes. First, the Louvain algorithm is used to divide the network into a community to reduce the search space of seed nodes. In the second step, use graph traversal to collect the information of nodes, use the different information of these nodes to assist in constructing a reverse generation network, and select a part of the nodes to join the candidate node set; finally, use the heuristic algorithm and the improved classical greedy algorithm from the candidate nodes. to find the final top-k influential nodes.

1.2 Research motivation

Influence node identification methods based on community discovery have attracted extensive attention of network science researchers in recent years. However, the existing methods simply take advantage of the feature of community structure, and some methods based on three-stage method have some shortcomings in selecting candidate node sets and seed nodes. First, existing methods such as random walk, genetic algorithm or some other heuristic algorithms need to traverse the entire network when selecting the candidate node set, and the selected candidate nodes may gather with each other. If seed nodes are selected from these candidate node sets, there may be a problem of overlapping influence ranges. Therefore, the generation of candidate node sets is particularly important in the entire seed node selection process. Secondly, in the stage of seed node identification, a large number of algorithms use greedy algorithms for accurate selection. Although the selection in the generated candidate node set has greatly improved the operation efficiency, it is also time-consuming. Therefore, it is hoped that the candidate node set selected in the second stage can help the third stage, and not only narrow the search scope.

2. Related concepts

Let G=(V,E) denote a complex network graph, V=[v ₁ ,v ₂ ,...,v _n ] denote a set of nodes, E=[e ₁ ,e ₂ ,...,e _m ] represents a set of edge sets. Nodes represent individuals in a complex network, and edges represent relationships between individuals in the network. In the patent of the present invention, only the undirected and unauthorized simple network is concerned, and the existence of self-loop is not allowed.

Definition 1, Influential Nodes top-k: Top-k influential nodes are defined as nodes with significant influence in a specific occasion, and the number is designated as k.

Definition 2: Influence maximization problem: Influence maximization problem refers to finding a group of influential nodes, so that the k nodes are used as source nodes S to maximize the influence when spreading on the specified propagation model, This can be expressed as

Influ(S)=arg max _S∈V,|S|=k σ(S) (1)

Among them, Influ(S) represents the influence of the source node set S, σ(·) represents the information diffusion function, and σ(S) represents the expected number of nodes that can be affected by the seed set S as the node set after spreading on the specified model.

Definition 3, Robustness value: The robustness value can be used to evaluate the performance of the sorting algorithm. Given a network, remove a node at each time step and compute the size of the largest connected component in the remaining network until the network is empty. Its network robustness value R is defined as

where n is the number of nodes in G, σ _gcc (G) represents the size of the largest connected component of the network when no node is removed, σ _gcc (G\{v ₁ ,v ₂ ,...,v _n }) Represents the size of the huge connected components in the remaining network after sequentially removing nodes in the set K={v ₁ , v ₂ ,...,v _k } from the network. The robustness value R can be regarded as the area under the R curve, as shown in Figure 1, with k/n on the horizontal axis and σ _gcc on the vertical axis (G\{v ₁ ,v ₂ ,...,v _n }) /σ _gcc (G); The x-axis of Figure 1 represents the proportion of removed nodes, and the y-axis represents the size of the largest connected component of the remaining network after removing nodes.

在完全网络中，

因此，鲁棒性值的范围为

更小的鲁棒 性值意味着算法更小的性能。Among all n-node networks, the most vulnerable network is the star network, and the most robust is the fully connected network. In the star network,

In a complete network,

Therefore, the range of robustness values is

A smaller robustness value means a smaller performance of the algorithm.

In this section, the following three aspects will be introduced: community detection, reverse generative network, and graph traversal methods.

2.1. Community detection

A community is usually thought of as a group of closely interconnected nodes that focus on users with similar content or with the same interests. All nodes within a community are closely clustered, while different communities are only sparsely connected. Research on community structure detection in networks is of great significance for discovering group structure in social networks, understanding the impact of network group structure on information dissemination, and identifying key nodes in complex networks. Considering the real-world network characteristics, the algorithm complexity can be greatly reduced by rationally utilizing the community structure.

In the past decade, a large number of outstanding community detection algorithms such as FPMQA, BiLPA, CommunityGAN, SEAL, etc. have been proposed, but Newman algorithm and Louvain are undoubtedly still widely used community detection algorithms. In the patent of the present invention, the Louvain algorithm is selected to cluster the network. This algorithm is a community discovery algorithm based on modularity, and its optimization goal is to maximize the modularity of the entire community network. The network modularity is defined as

where Q is the network modularity;

k _i represents the sum of the weights of the edges connected to node i;

k _j represents the sum of the weights of the edges connected to node j;

A _ij represents the weight of the edge between nodes i and j;

m represents the sum of the weights of all edges;

表示所有边的权重之和。Louvain 算法主要包括Modularity Optimization和Community Aggregation两个阶段。前一阶段主要是将每个 节点划分到与其邻接的节点所在的社区中，以使模块度不断增大；后一阶段主要是将第一阶段划分 出来的社区聚合成一个点，再根据上一步的社区结构重新构造网络。阶段一需要计算模块度增益， 其计算公式为：where A represents the network adjacency matrix, which represents the weight of edges between nodes. When the network is not a weighted graph, the weight of all edges is 1; k _i =∑ _j A _ij represents the sum of the weights of all edges connected to node i ,

represents the sum of the weights of all edges. The Louvain algorithm mainly includes two stages: Modularity Optimization and Community Aggregation. The former stage is mainly to divide each node into the community where its adjacent nodes are located, so as to increase the modularity; community structure to reconstruct the network. The first stage needs to calculate the modularity gain, and its calculation formula is:

The above formula can be simplified to:

where ∑ _in represents the sum of the weights of all edges within the community C, and k _i,in represents the sum of the weights of the edges from node i to community C. ∑ _tot represents the sum of the weights of the edges pointing to the nodes in the community C. The Louvain algorithm can obtain a more natural community of the network, and it is also a fairly fast algorithm, so the algorithm is used to divide the community of the network to speed up the proposed algorithm.

2.2. Reverse generative network

Lin et al. proposed Backward Generating Networks (BGN) to identify influential nodes in complex networks, and the method obtains the ranking of node importance by minimizing the robustness value R. The purpose of BGN is to find a sequence of nodes, so that the network collapses as soon as possible, that is, the maximum connected component in the network decreases rapidly. The core of BGN is the reverse process. It does not choose to delete nodes from the network, but according to the requirement that the size of the huge connected components in the network grow as slowly as possible, add nodes to the empty network one by one to construct the original network. In this way, the nodes are ordered in the opposite order than they were added, that is, nodes added later are more important in maintaining network connectivity.

并且

在(n+1)^th时间步即第n+1个节点 的时间步，将剩余节点中的一个节点添加到当前的网络G_n(V_n,E_n)中形成一个有n+1个节点的新网 络，即G_n+1(V_n+1,E_n+1)，V_n表示网络G_n的节点集，E_n表示网络G_n的边集。重复此过程，直到网络恢 复为原始网络。注意，在这一过程中所有进行中的网络G_n(n＝0,1,2,...,N)都是网络G的诱导子图，G_n表示n个节点的网络。根据BGN的策略，在每一个时间步中选择的节点应该尽可能最小化网络G_n+1中的最大连通分量的大小。The reverse process starts with an empty network G ₀ (V ₀ , E ₀ ), where,

and

At the (n+1) ^th time step, that is, the time step of the n+1 th node, one of the remaining nodes is added to the current network G _n (V _n , E _n ) to form a network with n+1 nodes The new network of , namely G _n+1 (V _n+1 , E _{n +1} ), V _n represents the node set of the network G _n , and En represents the edge set of the network G _n . Repeat this process until the network returns to the original network. Note that all in-progress networks Gn ( _n =0,1,2,...,N) in this process are induced subgraphs of network G, Gn representing a network of _n nodes. According to the BGN strategy, the nodes selected in each time step should minimize the size of the largest connected component in the network G _n+1 as much as possible.

2.3. Graph Traversal Centrality

Graph traversal frameworks can incorporate different types of centrality to improve existing performance. This method solves the problem of identifying influential nodes from the perspective of graph traversal, which is completely different from existing methods. Any existing centrality such as degree centrality, H-index, etc. can generate importance scores through this framework. The graph traversal centrality is shown in Figure 2. First, for each node in the network, a breadth-first search tree (BFS) is constructed by traversing the graph layer by layer, where the target node is the root node, as shown in Figure 2(A) Show. Each node has an initial centrality score, which can be obtained from any centrality metric. For a tree of influential nodes, there are generally more nodes at the top level of the BFS tree, because the top level nodes belong to the local neighbors of the root node. Second, construct a cumulative score vector vec=[l ₁ ,l ₂ ,...,l _h ] of length h from each BFS tree, where h represents the maximum number of levels (the number of levels of the root node is 1 ). l _i represents the sum of the scores of all nodes with layers not greater than i, as shown in Figure 2(B). Third, the first m values of the score vector vec are used to draw the curve, the area under the curve is used to quantify the influence of the node, and the area under the curve is recorded as the AUC value to measure the influence of each node; such as As shown in Figure 2(C), where m (1≤m≤h) is a user-specific parameter, m=2 in this figure; the x-axis represents the number of layers of the BFS tree, and the y-axis represents the cumulative score of each layer.

In a given network graph G, suppose the initial centrality score is CS={c ₁ ,c ₂ ,...,cn }, where c _i represents a certain centrality of node _i (such as degree, H-index etc.), n represents the number of nodes, and c _n represents the nth node centrality score. Then the cumulative score of the BFS tree generated by each node at the mth layer can be calculated as follows:

where cum_score(m) represents the cumulative score of the BFS tree generated by each node in the mth layer; v _j represents node j, T(q) represents all nodes in the qth layer in the BFS tree generated by a node, and c _j represents Some centrality of node j. The AUC value is obtained by plotting the first m terms of the generated score vector and calculating the area, which can be expressed as follows:

The AUC(m) value represents the first m items of the generated score vector to draw the curve and calculate the area, which represents the AUC value of a node to measure the importance of the node.

The AUC value obtained by graph traversal can better improve the performance such as degree centrality, and make the existing centrality sorting methods more fine-grained.

3. The proposed framework

In this chapter, a new CBGN framework will be proposed to maximize influence in the network. The pseudocode of its algorithm is shown in Algorithm 1. The framework is composed of three parts as shown in Figure 3: (1) Community division; at this stage, a community detection algorithm (algorithm 1line3) suitable for the application dataset and considering the running time is adopted. (2) Candidate set generation; the concept of graph traversal is introduced in reverse network generation. Nodes are added to the empty network one by one using a centrality metric further optimized by graph traversal. Finally, the nodes that have not joined the network are regarded as candidate nodes (algorithm 1lines 4-10). (3) Select the seed node. Balance the heuristic algorithm with the greedy algorithm for fast and accurate node selection (Algorithm 1line12). A detailed description of each step will be given below.

3.1 Community Division

The Louvain algorithm is used to divide the real network data set of the patent of the present invention. Compared with some other graph segmentation methods, hierarchical clustering methods, label propagation methods, etc., the Louvain algorithm does not require prior knowledge about the number of communities and can find more natural communities. Therefore, the community obtained by Louvain's algorithm is closer to the intrinsic community of the real network. And the community discovery algorithm can also be applied to large-scale networks. In addition, for the network after the community is divided, not all the communities are meaningful enough to accommodate the final seed nodes, and for those smaller communities, they are not sent to the candidate node selection stage. Considering that larger communities have more influence, each community size has at least the following conditions

C_size=size(G)*η (9)

where size(G) represents the number of nodes in the network G, and η is an adjustable parameter to control the size of the community that satisfies the condition. The invention patent sets η=0.01.

3.2 Candidate Node Selection

At this stage, candidate nodes will be generated in mutually independent communities. Efficiency is improved by reducing the number of candidate nodes that need to be evaluated to find the most influential nodes. In this step, each community will be treated as an induced subgraph, an independent network. In each network, the process of back-generating the network is performed by minimizing the robustness value. When adding node u to the network, record the maximum connected component of the network as G[u]. According to the reverse generation network strategy, the added node u should minimize the size of the maximum connected component in the network, but there may be two or more nodes that satisfy this condition at the same time, such as the green nodes in Figure 4, which is a toy network ., Figure 4(A) is the second time step in the reverse generation process. It is found that when a node is added while ensuring that the maximum connected component of the network is minimized, there are multiple nodes (node 1, 2, 3, 4, 6) are optional, Fig. 4(B) is in the 4th time step of the reverse generative network, here there are 3 nodes (nodes 1, 3, 4) optional. The centrality optimized by graph traversal is used to assist in constructing a reverse generative network. Transform the objective of minimizing the size of connected components into minimizing the cost function. Define its cost function as:

表示在(n+1)^th时间步， 将节点u加入到网络G中的最大连通分量的大小，即

ξ是一个足够小的正参数，保 证

这里选择度中心性作为图遍历中的初始化中心分 数，度中心性经过图遍历框架优化，可以产生更加细粒度的衡量节点影响力的AUC分数。在每个 时间步将使得代价函数最小的节点加入到网络中，当剩余未加入节点数量满足候选节点数量需求时， 停止构造网络。其改进的在每个社区中用于生成候选节点的反向生成网络算法imp_BGN如算法2 所示。由于反向生成网络过程中先加入是较为不重要的节点，因此将剩余未用于构造原始网络的节 点则传入候选节点集。为了进一步缩小搜索范围，并保证有质量合适的候选节点，在每个社区形成 的独立网络中设置候选节点集的大小，其公式表示如下：Among them, cost(u,n+1) represents the cost function of node u at (n+1) ^th time step, AUC _u represents the AUC value of node u, AUC _max represents the largest AUC value of all nodes, and AUC _min represents all nodes with the smallest AUC value,

represents the size of the largest connected component that adds node u to the network G at the (n+1) ^th time step, namely

ξ is a positive parameter small enough to guarantee

Here, degree centrality is selected as the initial center score in graph traversal. The degree centrality is optimized by the graph traversal framework, which can generate a more fine-grained AUC score that measures the influence of nodes. At each time step, the node with the smallest cost function is added to the network, and the network is stopped when the number of remaining unjoined nodes meets the requirement of the number of candidate nodes. Its improved reverse generative network algorithm imp_BGN for generating candidate nodes in each community is shown in Algorithm 2. Since the less important nodes are added first in the process of reverse network generation, the remaining nodes that are not used to construct the original network are passed into the candidate node set. In order to further narrow the search range and ensure that there are candidate nodes with suitable quality, the size of the candidate node set is set in the independent network formed by each community. The formula is as follows:

Among them, cand_num _i represents the size of the candidate node set of the ith community, and the item (C_size _i -C_size _min )/(C_size _max -C_size _min ) represents the proportion of the ith community in all selected communities, and its value is defined in [0 ,1]. β is a scaling parameter that controls the size of the candidate node set. k is the final number of seed nodes to be selected. Using the improved reverse generative network to generate candidate node sets has the following advantages. First, the generated candidate node sets can be more dispersed, with a small number of nodes clustered, and all of them are key nodes in the network. Second, the influence range of the selected candidate nodes has a low degree of overlap. In the third stage, the heuristic method and the greedy method can also be used to balance the selection of seed nodes. Third, these candidate nodes ensure the robustness of the network, and removing these nodes will easily cause the network to collapse. Fourth, it is not necessary to traverse the entire network when generating candidate nodes, and the network construction can be stopped when the number of unjoined nodes meets the number of candidate node sets.

In summary, it is very meaningful to use imp_BGN to generate candidate nodes.

In Algorithm 2, first lines1-2 initialize the algorithm, and then lines3-11 construct a reverse generative network to generate candidate node sets. Each time a node is added to the network, the joining cost of the remaining nodes (lines4-5) needs to be calculated, and the node (line7) that minimizes the cost function is selected to construct the network. After adding a node, it is necessary to update the size of each faction in the network, that is, the size of the connected component, and record the size of the largest connected component in the network (line8). This process is repeated until the number of remaining nodes meets the required number of candidate nodes.

3.3 Select the seed node

Through the first two stages, the search space has been greatly reduced. Since the nodes of the candidate node set in the second stage are relatively scattered with each other, the heuristic algorithm can be used to partially select nodes to balance the efficiency of the algorithm. At this stage, the selection heuristic method is combined with the greedy method to select the seed influence nodes. Either heuristic algorithm combined with improved classical greedy algorithm or heuristic algorithm combined with classical greedy algorithm can be used. It is preferable to use a heuristic algorithm combined with an improved classical greedy algorithm to select seed influence nodes. The steps are as follows:

The overall seed node selection is divided into two steps: Step 1): select some k ₁ nodes in the candidate node set by the degree discount algorithm, and step 2): select some k ₂ nodes by the improved submodular CELF algorithm. Let k ₁ and k ₂ satisfy the following conditions:

k ₂ =kk ₁ (13)

Among them, k is the final number of seed nodes to be selected, and c is the total number of communities in the network that meet a certain scale. μ is a tunable parameter to balance greedy and heuristic algorithms. For convenience, the patent of the present invention sets μ=0.5. In the heuristic selection process, the contagion probability p in the degree discount is made larger than the network's propagation threshold. The generalized discount degree of each node is obtained by formula (14), the calculation results are sorted from high to low, and the first k ₁ nodes are selected.

where d _v represents the degree of the node, t _v represents the number of infected neighbors of node v, and t _w represents the number of infected neighbors of node w of node v's susceptible neighbors. In the greedy CELF selection stage, the location information of nodes and the structural similarity between nodes are further considered. , the CELF algorithm needs to iteratively select nodes) or the nodes selected by the heuristic process are similar, that is, as long as there is a node that satisfies, then the node is not selected, and it is eliminated from the candidate node set. Design node u and node v similarity as follows:

sim_loc=1-abs(ks(u)-ks(v)) (16)

where sim represents the similarity between node u and node v, N(u) represents the neighbor node set of node u, N(v) represents the neighbor node set of node v, and abs( ) represents the absolute value. ks(u) is the normalized k-shell metric for node u, and ks(v) is the normalized k-shell metric for node v. The former term represents the structural similarity between nodes, and the latter term represents the positional similarity between nodes. Since the k-shell indices between two nodes are equal or similar, they should be located at similar locations in the network, and such nodes are considered to be similar in location. The location similarity sim_loc is calculated by equation (16). Obviously, the larger the sim_loc, the more similar the node positions. where ε is a positive parameter that balances structural similarity and positional similarity, and ε = 0.1 is set here. The pseudo-code of the algorithm for selecting seed nodes is shown in Algorithm 3.

Among them, lines1-3 initialize the algorithm, then use the degree discount algorithm to select some k ₁ nodes (line5), and finally use the improved CELF algorithm to select some k ₂ nodes (lines12-19), sim_value represents the similarity threshold, the difference between the two nodes If the similarity between them is greater than the similarity threshold, they are considered to be similar.

4 Experimental results

In order to compare the proposed CBGN method with existing algorithms (Degree, K-shell, NC+, PageRank, ClusterRank and BGN), six real networks including Inf-USAir, CEnew, Power, Ca-GrQc, Hamster and Router Simulation experiments including robustness and propagation scale of the SIR model were carried out on .

4.1 Dataset

The patent of the present invention uses 6 real network data sets of different types and scales, and their statistical characteristics are shown in Table 1.

The degree distribution and network community division of each experimental network are shown in Fig. 5, which are (a) Inf-USAir, (b) CEnew, (c) Power, (d) Hamster, (e) Ca-GrQc, (f) )Router. The abscissa represents the degree of nodes in the network, and the ordinate represents the frequency of node degrees. The small image shows the results of the community visualization of the network.

Among them, 1) Inf-USAir is an American aviation network, the node represents an airport, and the edge represents a direct flight between two airports. 2) CEnew is a biological network that describes an edge list of the metabolic network of C. elegans. 3) Power is an undirected, weightless network, representing the topology of the power grids in the states of the United States, each node represents a power company, and each edge represents the relationship between power companies. 4) Hamster is a description of the friendship between users of the website "www.hamsterster.com". 5) The Ca-GrQc network is a scientific collaboration network covering scientific collaborations between authors of papers submitted to the general relativity and quantum cosmology categories. 6) A Router is a symmetric snapshot of the Internet structure at the autonomous system level.

Table 1 Statistical characteristics of the network

Network |V| |E| <k> k_max <d> C_num β_min Inf-USAir 332 2126 12.807 139 2.738 7 0.0231 CEnew 453 2025 8.94 237 2.664 9 0.0256 Power 685 1282 5.743 12 12.422 17 0.2778 Hamster 2426 16631 13.711 273 3.67 168 0.0241 Ca-GrQc 4158 13422 6.456 81 6.049 40 0.0589 Router 5022 6258 2.492 106 6.449 55 0.0786

In Table 1, |V| represents the total number of nodes in the network, and |E| represents the number of edges in the network. <k>=2|E|/|V| represents the average degree of the network. k _max represents the maximum degree of the network. <d> represents the average shortest path length of the network. C_num represents the number of communities in the network. β _min is the propagation threshold of the network, which is calculated by the formula <k>/(<k ² >-<k>).

4.2 Performance indicators

(1) Robustness value

Robustness can be used to evaluate the performance of the algorithm, given a network, delete a node at each time step, and calculate the size of the largest connected component in the remaining network. The robustness value can be obtained by summing the maximum connected components of these nodes each time they are added and normalized by the network size N. The robustness value is calculated by formula (2), and the smaller the value is, the better the sorting algorithm can give the correct sorting.

(2) Cumulative Distribution Function (CDF)

The cumulative distribution function can completely describe the probability distribution of a random variable X. For all real numbers x, the cumulative distribution function is defined as follows:

F _X (x)=P(X≤x)for-∞<x<+∞ (17)

The CDF can be used to determine the probability that a random observation from a population is less than or equal to a particular value. The invention patent uses CDF curve to measure the ability of sorting algorithm to distinguish the importance of nodes.

(3) SIR model

The SIR model is a common diffusion model for describing infectious diseases. Its basic assumption is to divide the nodes in the network into three categories: a) susceptible nodes, which refer to uninfected but lacking immunity nodes, b) infected nodes , such nodes are already infected nodes, which can infect neighboring susceptible nodes with probability β at each time step, c) restore nodes, also at each time step, each infected node will change with probability γ In order to restore the state, and will not participate in the infection and infection process afterward. The SIR model is often used to measure the influence scale of a node. The invention patent uses the SIR model to measure the final infection scale of the selected seed nodes. A good spreader can quickly reach a high infection level, and its infection scale F(t) at time t and the final infection scale F(t _c ) that reaches a steady state during the infection process can be expressed as

where n _I (t) represents the number of infected nodes at time t, n _R (t) represents the number of recovered nodes at time t, and n is the number of nodes in G.

(4) Average shortest path length

To ensure wider coverage, consider the chosen seed nodes to be spread across parts of the network. Generally speaking, the more dispersed the selected nodes are, that is, evenly distributed in the network, the smaller the overlapping degree of the influence range between nodes, and the larger the expected infection range. Generally, the average shortest path length can be used to judge the degree of dispersion of nodes, and the average shortest path length L _s between seed nodes can be calculated by formula (19).

where S represents the selected set of seed nodes, and d _{u, v} represents the average shortest path length from node u to node v.

4.3 Baseline Algorithm

Taking 6 advanced algorithms as benchmark algorithms, the robustness experiments and propagation scale experiments are compared with the proposed CBGN method. The 6 algorithms are briefly introduced as follows.

Degree: This algorithm selects the maximum degree as the seed node, which is a simple, intuitive and commonly used standard algorithm.

K-shell: The k-shell value of each node can be obtained by K-shell decomposition, and the K-shell method considers the positional relationship of nodes in the network.

Neighborhood coreness(NC): This method is a further improvement on the K-shell method. The number of neighborhood cores C _nc (v) and the number of extended neighborhood cores C _nc+ (v) for each node are calculated as follows, where ks( w) represents the k-shell value of node w.

where N(v) represents the number of neighbors of node v.

PageRank: The PageRank algorithm is proposed as an algorithm for the importance of computer Internet pages. The higher the PageRank value, the more important a web page is and may be ranked higher in Internet search rankings. If a web page is linked to by many other web pages, it means that this web page is more important. If a page with a high PageRank links to another page, the PageRank of the linked page will increase accordingly.

ClusterRank: The ClusterRank algorithm not only considers the influence of the node itself, but also considers the clustering coefficient of the node. It considers the local information of the network and lacks performance guarantee.

BGN: This algorithm considers the importance of nodes from the perspective of network robustness, and considers the global information of the network.

4.4 Robustness Analysis

In order to verify the effectiveness of the improved reverse generative network algorithm, imp_BGN is compared with six baseline algorithms to analyze its robustness. A good sorting algorithm should have a smaller robustness value, that is, the smaller the area under the R curve. Figure 6 visualizes the R-curves generated during the reverse generation of the network in 6 networks, (a) Inf-USAir, (b) CEnew, (c) Power, (d) Hamster, (e) Ca -GrQc, (f)Router. The robustness values R of different methods on 6 real networks are given in Table 2. It can be seen from Figure 6 and Table 2 that, except in the Inf-USAir network, Imp_BGN has a smaller robustness value R than the other six baseline methods. It can be shown that candidate nodes can be well selected by this method, and these candidate nodes are helpful to maintain network stability and connectivity. Considering that the reverse generation network is applied in the candidate node selection stage, and the candidate nodes are carried out in the sub-network formed by the community, in order to further verify the effectiveness of the algorithm, in the first two communities with a larger scale of each network The robustness of the algorithm is analyzed, and the statistics of the results are shown in Table 3. C ₁ and C ₂ represent the top two communities in terms of community size. In Figure 7, the R curves of the first two communities in the two networks, CEnew and Power, are visualized. Figure 7 shows the R curves in the two real network communities. The horizontal axis represents the proportion of seed nodes, and the vertical axis represents the largest network in the network. The size of the connected components. Figure 7(a) is the largest community in CEnew, Figure 7(b) is the second largest community in CEnew, Figure 7(c) is the largest community in Power, and Figure 7(d) is the second largest community in Power.

As can be seen from Table 3 and Figure 7, the imp_BGN algorithm also performs the best in the community of most networks, and also outperforms the BGN algorithm by a small margin in the community of the Inf-USAir network.

Table 2 Robustness value R of different methods

Network Inf-USAir CEnew Power Hamster Ca-GrQc Router K-shell 0.1614 0.1873 0.4223 0.1815 0.2317 0.0285 ClusterRank 0.1181 0.1301 0.2115 0.1371 0.1051 0.0158 PageRank 0.1227 0.1229 0.2019 0.1421 0.1027 0.0135 NC+ 0.1643 0.1623 0.3329 0.1692 0.2143 0.0202 BGN 0.0899 0.1171 0.0633 0.1045 0.0606 0.0076 Degree 0.1260 0.1200 0.2286 0.1384 0.1313 0.0121 Imp_BGN 0.0961 0.0790 0.0431 0.0872 0.0538 0.0063

Table 3 Robustness values R of different algorithms in the community

In addition, the reason for choosing the degree centrality optimized by graph traversal to assist the construction of the reverse generation network is more effective than directly using the degree centrality to assist the construction. This is because the degree centrality becomes more fine-grained after being optimized by the graph traversal framework. The ability to distinguish the importance of nodes can be measured by the resolution, which can be measured by the cumulative distribution function CDF. Figure 8 presents the CDF curves of Degree and graph traversal optimized degree centrality TRank_degree in three networks. The three networks are (a) Inf-USAir, (b) CEnew, (c) Power. The x-axis in the figure represents the level of nodes, and the y-axis represents the proportion of each level. The smaller the angle between the CDF curve and the x-axis, the better the algorithm effect. It can be seen that TRank_degree can better distinguish the importance of nodes. This further verifies the effectiveness of the algorithm imp_BGN.

4.5 Analysis of Spread Scale

In order to verify the ability of the proposed CBGN method to select influential nodes, the SIR model is selected to measure the final infection scale F(t _c ) of the seed nodes selected by different algorithms. The selection β should be higher than the network propagation threshold β _min , and the infection rate is set as λ=β/γ. Due to the randomness of the model, the experimental results were obtained by averaging 1000 independent experiments. The number of seed nodes chosen is set to 3% of the network size. The experimental results are shown in Figure 9, where the abscissa represents the time t of infection, and the ordinate F(t) represents the cumulative number of infected nodes at time t, and F(t) will reach a stable value F(t) over time _c ). Reaching a larger F(t _c ) in less time indicates better performance of the algorithm.

Observing the time step experiment of the SIR model in Figure 9, the proposed CBGN has the best propagation scale in the 6 network datasets compared with the other 6 algorithms. These 6 networks are (a) Inf-USAir , (b) CEnew, (c) Power, (d) Hamster, (e) Ca-GrQc, (f) Router. In the Inf-USAir network, the infection scale of the proposed CBGN method is significantly higher than that of the other 6 baseline algorithms, which are comparable in infection scale. In the Power network, the infection scale of the CBGN algorithm outperforms the best ClusterRank algorithm by 0.84%. In the networks CEnew, Hamster, Ca-GrQC and Router, the infection scale of the CBGN method is 0.59%, 1.05%, 0.71% and 0.14% higher than the best BGN algorithm, respectively. In these 4 networks, the BGN algorithm shows excellent ability, but it is still inferior to CBGN. In addition, in the SIR model, different infection probabilities will also have a certain impact on the transmission scale. Therefore, experiments are carried out on different infection rates of the SIR model, and the λ range is set to [1.0, 2.0], and the experimental results are shown in Figure 10. . Again, the experimental results were obtained from the average of 1000 independent experiments. where the x-axis represents the infection rate λ, and the y-axis represents the stable final infection scale F(t _c ) at a certain infection rate.

The infection scale of the proposed CBGN method outperforms the six baseline algorithms under different infection probabilities. Except in the CEnew network, the CBGN method is similar to the BGN algorithm, and outperforms the BGN algorithm by a large advantage in other networks. In addition, when selecting candidate nodes, the improved reverse generation network algorithm imp_BGN does not always obtain the smallest robustness value on Inf-USAir and Router, but the seed nodes selected by the final CBGN method can successfully infect the most node. It can be seen that the constructed CBGN framework is step-by-step and effective.

4.6 Average Shortest Path Length Analysis

Generally speaking, the more dispersed among the nodes of the selected seed node set, that is, the larger the average shortest path, the wider the diffusion effect can reach. Therefore, the average shortest path length L _s between the seed node sets is usually used as a measure Good and bad indicators. L _s is not an absolute indicator, because the spreading ability of nodes is considered when selecting nodes and not just the degree of dispersion of nodes.

Table 4 Average shortest path length

Network Inf-USAir CEnew Power Hamster Ca-GrQc Router Degree 1.0 1.3077 12.3809 1.6929 3.936 3.6381 K-shell 1.0 1.3077 9.7762 1.9958 4.0117 3.1819 NC+ 1.0 1.2527 8.6714 1.5871 3.9745 3.0253 PageRank 1.1333 1.3187 11.2143 1.7393 3.3853 3.6440 ClusterRank 1.0 1.3187 10.6524 1.6541 2.9274 3.0640 BGN 1.0 1.4615 8.5381 2.1008 3.7463 4.1390 CBGN 1.2 1.5275 12.2857 2.2618 3.9821 4.0840

Table 4 presents the average shortest path lengths between the seed nodes selected by the proposed CBGN method and the 6 baseline algorithms. It can be seen that in half of the networks, the set of seed nodes selected by the CBGN method is the most dispersed. While Degree, K-shell and BGN methods select the most dispersed nodes in Power, Ca-GrQc and Router networks, respectively.

5 Conclusion

The patent of this invention proposes a community-based reverse generation network framework CBGN to solve the problem of maximizing influence. First, use the Louvain algorithm suitable for the application dataset and consider the running time to divide the network into natural communities, and narrow the search scope of influential nodes through this step. Then, each community is regarded as an induced subgraph of the original graph, and the degree centrality of graph traversal optimization is used in each subgraph to assist the reverse construction of the network, and each time a node that minimizes the cost function is added to the network, when the remaining When the nodes that do not join the network meet the number of candidate nodes, the network construction is stopped, and all these candidate nodes are sent to the candidate node set. By analyzing the robustness experiments, the improved reverse generative network algorithm can obtain smaller robustness values in the whole network or independent communities. This verifies that the improved imp_BGN algorithm can better select key nodes in the network or nodes that maintain network stability as candidate nodes. Finally, the utilization discount and the greedy algorithm considering the network structure and node position relationship select the final seed node from the candidate node set. The propagation scale and average shortest path length experiments of the algorithm prove that the seed nodes selected by the proposed CBGN method have a faster infection speed and larger infection scale, and the seed node sets are scattered on most of the network.

To sum up, the main contributions of the patent of the present invention are summarized as follows:

(1) A new reverse generative network method, Imp_BGN, is proposed to minimize the cost function. Using the new perspective of graph traversal, each node is evaluated by constructing a breadth-first search tree (BFS) with the target node as the root node. , the influence score of each node can be obtained from the BFS tree, and the influence score can be used to assist in constructing the reverse generation network, and since the least important node is added first, the generated network can be saved from the original network without being added. The nodes in the network are directly added to the candidate node set, which greatly reduces the computation time.

(2) The CELF algorithm is improved. Considering that the common neighbors and positional relationships between nodes will overlap the influence of the selected node set, a similarity evaluation index is designed, which is applied to the CELF selection of seed nodes. process.

(3) Conceived a community-based reverse generative network framework CBGN to select a group of influential nodes in a complex network, considering the community structure of the network, using the community to accelerate the algorithm, and combining the connectivity of the network , graph traversal, and the advantages of heuristics and greedy algorithms.

(4) The proposed CBGN method is experimentally evaluated on the robustness, influence propagation scale and average shortest path length between nodes. advanced methods are more competitive.

In addition, for the problem of influential node identification, there are still many challenges from different perspectives, such as how to efficiently mine large-scale network influential nodes, on a time-varying network, the influential nodes may change with the change of topology and How to better combine information between different layers in a multi-layer network, etc. Future work will further extend to weighted networks, time-varying networks, multilayer networks, and heterogeneous networks.

Although embodiments of the present invention have been shown and described, it will be understood by those of ordinary skill in the art that various changes, modifications, substitutions and alterations can be made in these embodiments without departing from the principles and spirit of the invention, The scope of the invention is defined by the claims and their equivalents.

Claims (8)

1. A complex network influence node identification method based on a reverse generation network is characterized by comprising the following steps:

s1, community division: carrying out community division on the network by using a Louvain algorithm;

s2, generating a candidate node set: node information is collected by using graph traversal so as to assist in constructing an improved reverse generation network, and then a part of nodes are selected to be added into a candidate node set;

s3, selecting a seed node: and finding out the final k influential nodes from the candidate node set as seed nodes.

2. The method for identifying the complex network influence node based on the backward generation network according to claim 1, wherein the size of the community at least has the following condition:

C_size＝size(G)*η (9)

wherein C _ size represents the community size;

size (G) represents the number of nodes of network G;

eta is an adjustable parameter for controlling the size of the community that satisfies the condition.

3. The complex network impact node identification method based on the backward generation network of claim 1, wherein the S2 comprises:

s2-1, calculating the adding cost of the remaining nodes, selecting the nodes with the minimized cost function to construct the network, wherein the cost function is as follows:

where cost (u, n +1) indicates that node u is at (n +1) ^th A cost function of the time step;

is shown in (n +1) ^th Time step, the size of the maximum connected component for adding node u to network G, i.e.

AUC _u AUC value representing node u;

AUC _max represents the maximum AUC value among all nodes;

AUC _min represents the smallest AUC value among all nodes;

ξ is a sufficiently small positive parameter;

s2-2, after the node is added, the size of each connected component in the network needs to be updated, and the size of the maximum connected component in the network is recorded;

s2-3, repeating the steps S2-1-S2-2 until the number of the remaining nodes meets the required candidate node number, and at the same time stopping constructing the network.

4. The complex network impact node identification method based on the backward generation network of claim 1, wherein the S2 further comprises:

in order to further narrow the search range and ensure that there are candidate nodes with proper quality, the size of a candidate node set is set in an independent network formed by each community, and the formula is as follows:

where cand _ num _i Representing the size of the ith community candidate node set;

(C_size _i -C_size _min )/(C_size _max -C_size _min ) Representing the proportion of the ith community among all the selected communities;

β is an amplification parameter;

k is the number of seed nodes that ultimately need to be selected.

5. The complex network influence node identification method based on the backward generation network according to claim 1, wherein the graph traversal comprises:

the degree centrality is selected as an initial center score in graph traversal, and the degree centrality is optimized through a graph traversal framework, so that an AUC score which is finer in granularity and can measure the influence of the nodes can be generated.

6. The complex network impact node identification method based on the backward generation network of claim 1, wherein the S3 comprises:

s3-1, selecting k in the candidate node set through a degree discount algorithm ₁ A node;

the calculation formula of the degree discount algorithm is as follows:

gdd therein _v Represents a degree discount for node v;

d _v degree representing node v;

t _v represents the number of infected neighbors of node v;

t _w representing the number of infected neighbors of a susceptible neighbor node w of the node v;

p represents the probability of infection;

s3-2, selecting k through improved sub-model algorithm ₂ A node;

k ₂ ＝k-k ₁ (13)

k is the number of the seed nodes which need to be selected finally;

mu is an adjustable parameter to balance greedy algorithm and heuristic algorithm;

c represents the total number of communities in the network that meet a certain scale;

cand_num _i representing the size of the ith community candidate node set;

the improved sub-modular algorithm selection k ₂ The specific steps of each node are as follows: and if the node u selected in the process of each round of improved sub-model algorithm selection is similar to the node selected before or the node selected in the heuristic process, not selecting the node and removing the node from the candidate node set.

7. The complex network influence node identification method based on the backward generation network of claim 6, wherein the similarity is determined by the following formula to determine whether the nodes are similar, and if the following formula is satisfied, the node u is similar to the node v;

where sim represents the similarity of node u and node v;

n (u) represents a set of neighbor nodes for node u;

n (v) a set of neighbor nodes representing node v;

n (u) andn (v) represents the number of neighbors shared by N (u) and N (v);

| represents the number of sets;

ε is a parameter approaching 0;

abs (·) represents the absolute value;

ks (u) is the normalized k-shell index for node u;

ks (v) is a normalized k-shell index for node v.

8. The method for identifying the complex network influence node based on the backward generation network according to claim 1, further comprising evaluating the method by using the following performance indexes: robustness value, cumulative distribution function, SIR model, and average shortest path length.

Images