CN108011784B - A Dynamic Optimization Method for the Worst Connectivity Performance of Networks - Google Patents

Abstract

The invention discloses a dynamic optimization method for the worst connection performance of the network. It includes the following steps: calculating the network diameter to obtain the corresponding set of node pairs; counting the number of shortest paths whose length is the diameter to obtain the set of shortest paths; reducing the set of node pairs, according to the number of elements in the reduced set Determine whether to optimize; according to the judgment result, choose to execute or end the optimization; randomly select several node pairs in the set, create a new direct connection edge to form a new network, and re-execute the above steps to achieve dynamic optimization. The method of the invention dynamically optimizes the overall connectivity performance of the network from the worst case by comparing the worst case of the connection between nodes, optimizing the pair of nodes and adding edges in a targeted manner. The invention can be widely used in a large number of actual complex systems, such as the Internet, traffic networks, etc., and provides an important reference for the optimal design of optical fiber routing layout, new routes, rail transit and the like.

Description

A Dynamic Optimization Method for the Worst Connectivity Performance of Networks

technical field

The invention relates to a dynamic optimization method for network connectivity performance.

Background technique

Human life and production activities depend on a large number of natural and man-made complex systems. For a given system, the connections and interaction patterns between its components can be represented by a network, and each component of the system can be abstracted into vertices and components in the network. The connections between them are abstracted into edges.

The overall connectivity of the network reflects the transmission and service capabilities of the carrier to a large extent, so it has received extensive attention in many application fields, such as the Internet, transportation networks, and trade networks. At present, the consideration of network connectivity usually focuses on deliberately attacking nodes with a high index (degree, betweenness, etc.) in the network and random attacks on all nodes. In these two cases, there are actually edges and all possible edges between nodes. (refer to the review published in Ecology letters by Banks et al. 2015).

Aiming at the dynamic change of network connectivity performance, the current research mostly focuses on the network evolution caused by random addition of edges or traction by external factors, and the influence of the evolution on the overall robustness of the network. For example, Foti et al. (J.Econ.Dyn.Control, 2013) considered changes in the network's robustness against random and deliberate attacks after adding edges, while the addition of edges in their trade network is influenced by economic policy affected. The improvement of network connectivity performance mainly considers the statistical characteristics of edges and the connectivity between most nodes, and the increase of edges is random. The current technology lacks active and targeted optimization, and also lacks an optimal way to add edges.

SUMMARY OF THE INVENTION

In order to solve the problem of targeted optimization of network connectivity performance, the present invention combines the robustness of the shortest path between nodes to evaluate the worst case of connectivity between nodes, provides an optimal way to add edges, and realizes dynamic optimization of network connectivity performance.

In order to achieve the above technical purpose, the technical solution of the present invention is a dynamic optimization method for the worst connectivity performance of a network, comprising the following steps:

Step 1: Calculate the network diameter and obtain the set of node pairs corresponding to the diameter;

Step 2: According to the set of node pairs obtained in step 1, count the number of shortest paths between each node pair, and obtain a set of shortest path numbers corresponding to the node pairs;

Step 3: According to the set of shortest paths obtained in Step 2, reduce the set of node pairs obtained in Step 1 to obtain the node pair in the worst case of connectivity; judge according to the number of elements in the reduced set whether to perform optimization;

Step 4: According to the execution optimization situation in the judgment result obtained in step 3, randomly select several node pairs in the set obtained in step 3, and add a directly connected edge respectively, thereby generating a new network; then return to step 1, In this cycle, dynamic optimization is implemented.

In the described method, in the described step 1, the steps of calculating the network diameter and obtaining the node pair set corresponding to the diameter are:

Step 1: Calculate the length of the shortest path between any two nodes in the network;

d _ij =min{P ¹ _i→j ,P ² _i→j ,...,P ⁿ _i→j }

where d _ij represents the length of the shortest path from node i to node j (i<j), n is the statistical value of the number of shortest paths from node i to node j, and P ^k _i→j represents the kth path from node i to node j The length value of each path, that is, the number of edges passed by the kth path; {P ¹ _i→j , P ² _i→j ,...,P ⁿ _i→j } is the length of all paths from node i to node j collection of values.

Step 2: Calculate the network diameter;

According to the length of the shortest directional path between two nodes obtained in step 1 in step 1, calculate the maximum length of the shortest path between any two nodes in the network, that is, the diameter:

D= _maxdij

D represents the diameter of the network; maxd _ij represents the maximum value of the shortest path length between any two nodes.

Step 3: Obtain the node pair set corresponding to the diameter;

According to the diameter obtained in step 2 in step 1, find the set of node pairs corresponding to the diameter, and the steps are:

U={(i,j)|d _ij =D}

Wherein U represents the node pair set corresponding to the diameter, and (i, j) represents the node pair satisfying the condition d _ij =D.

In the described method, the steps of obtaining the shortest path number set corresponding to the node pair in the second step are:

According to the set of node pairs obtained in step 3 in step 1, count the number of shortest paths between each node pair, and obtain the set of shortest paths corresponding to the node pairs. The steps are:

V={M _ij |(i,j)∈U}

Wherein M _ij represents the set of shortest path numbers corresponding to the node pair (i, j); V represents the set of M _ij .

In the described method, the steps of reducing the set of nodes and judging whether to optimize in the third step are:

Step 1: Obtain the node pair in the worst case of connectivity;

According to the set of node pairs obtained in step 3 in step 1, extract the node pair with only one shortest path, and the steps are:

U′={(i,j)|M _ij =1}

Among them, U' represents the node pair set after U is reduced, and _Mij = 1 means that there is only one shortest path between the node pair (i, j); in this case, the minimum cut set of the edge between the node pair is 1. Destruction of any node and edge on the path will lead to an increase in the diameter of the network, which will worsen the worst connectivity performance of the network.

Step 2: Determine whether to optimize;

According to the set of node pairs obtained in step 1 in step 3, it is judged whether to optimize according to the number of elements in the set. The steps are:

表示对“U′中的元素个数大于等于1个”这个命题进行真假判断；T表示命题判断结果为真，即进入下一步的优化阶段；F表示命题判断结果为假，即终止优化。where (card(U′)≥1)

Indicates that the proposition of "the number of elements in U' is greater than or equal to 1" is true or false; T indicates that the proposition judgment result is true, that is, the next optimization stage is entered; F indicates that the proposition judgment result is false, that is, the optimization is terminated.

In the described method, the steps of performing optimization in the described step 4 are:

According to the situation that the optimization needs to be performed in step 2 in step 3, the optimization is performed, and the steps are:

Randomly select t node pairs (i, j) in U' and connect them directly with an edge; among them, t<card(U'); here, the optimization implementer is given a certain degree of freedom to select each node according to the actual situation. The number of new edges added for the suboptimization.

The present invention implements active optimization of network connectivity performance by comparing the worst case of connectivity between nodes. Compared with the existing technology, the addition of edges is more targeted, and the worst case of network connectivity performance is improved from the perspective of improving the robustness of the connection between pairs of nodes, avoiding deliberate attacks or random attacks on some nodes in the worst case. impact before the worst-case scenario gets worse. The optimization process may lead to the reduction of the network diameter, which may also achieve the goal of optimizing the worst connectivity.

The dynamic optimization method of the present invention is not only applicable to simple networks whose edges do not contain directions and weights, but also applicable to directed networks and weighted networks. The condition of step 1 in the directed network can be changed to i≠j. For the weighted network, the weight of the edge can be converted into the path length to calculate. Therefore, the present invention can be widely used in a large number of actual complex systems, such as the Internet, traffic networks and other networks, and provides an important reference for the implementation of optical fiber routing layout, new routes, tracks and the like.

The present invention will be further described below in conjunction with the accompanying drawings.

Description of drawings

FIG. 1 is a flow chart of the present invention.

FIG. 2 is a schematic diagram of a complex network in the present invention.

FIG. 3 is a schematic diagram of the execution optimization of the present invention.

Detailed ways

Referring to FIG. 1, FIG. 1 is a flow chart of the present invention. The following examples illustrate the specific implementation process of the present invention.

Example 1: Dynamic Optimization of the Worst Connectivity Performance of a Stochastic Network

1) Get a complex network

In this embodiment, a random complex network with 50 nodes is denoted as DN. The network is represented as DN=(V, E), where V is the set of nodes and E is the set of edges between nodes. The nodes contained in V are {v1, v2, ..., v50}. In the network, nodes v1-v9, v1-v18, v1-v20, v1-v34, v3-v6, v5-v12, v5-v16, v5-v37, v5-v47, v6-v45, v7-v6, v8 -v37, v9-v29, v11-v21, v11-v24, v12-v13, v12-v15, v13-v41, v14-v18, v14-v23, v16-v21, v16-v23, v18-v30, v18-v31 , v21-v9, v21-v24, v21-v35, v22-v10, v22-v21, v23-v30, v23-v32, v25-v6, v26-v11, v26-v24, v26-v47, v27-v36, v27 -v45, v28-v5, v28-v20, v29-v18, v30-v37, v31-v9, v31-v34, v32-v3, v32-v6, v32-v36, v32-v41, v33-v47, v34-v7 , v34-v27, v34-v32, v34-v42, v35-v13, v35-v31, v35-v47, v36-v11, v36-v28, v36-v39, v36-v48, v37-v7, v37-v12, v37 -v21, v37-v24, v37-v27, v37-v33, v37-v42, v37-v43, v38-v1, v38-v2, v38-v43, v39-v31, v40-v4, v40-v5, v40-v27 , v40-v30, v40-v33, v40-v49, v41-v4, v41-v46, v42-v8, v42-v32, v42-v44, v42-v45, v43-v8, v43-v9, v43-v47, v43 -v48, v44-v39, v45-v38, v46-v28, v46-v33, v47-v14, v47-v34, v47-v45, v48-v42, v49-v44, v50-v3, v50-v30, v50-v43 There is an undirected and weightless edge between them, and there is no connection between other nodes.

FIG. 2 is a schematic diagram of a complex network obtained according to connections between nodes in Embodiment 1 of the present invention.

2) Calculate the diameter of the network and the set of corresponding node pairs

The network diameter is defined as the maximum value of the shortest path length between any two reachable nodes in the network. First calculate the length of the shortest path between any two nodes in the network. Taking the calculation of the length of the shortest path between the node pair (v1, v2) as an example, the shortest path between them is v1~v38~v2, and the shortest path contains 2 edges, so the length is 2. Calculate the length of the shortest path between any other two nodes in turn, and then find the maximum value among all the length values. The maximum value obtained here is 6, which is the diameter of the network. The corresponding set of node pairs is {(v2,v10),(v3,v10),(v4,v10),(v10,v25),(v10,v49),(v25,v29)}.

2) Count the number of shortest paths whose length is diameter, and obtain the set of shortest paths

First find the number of shortest paths between the node pair (v2, v10), walk along the edge from the node v2, limit the number of walking edges to 6, and go to the node v10, you can get 3 shortest paths. Obtain the number of shortest paths between node pairs (v3, v10), (v4, v10), (v10, v25), (v10, v49), (v25, v29) in turn, which are 6, 6, 1 Article, 6, 20. The set of shortest path numbers obtained is {6,6,1,6,20}.

3) Reduce the node pair set and judge the elements in the set

Extract the node pairs whose shortest path number is only 1, the set {(v2,v10),(v3,v10),(v4,v10),(v10,v25),(v10,v49),(v25,v29)} are Reduced to {(v10,v25)}. Judging the number of elements in the set, there is more than 1 at this time, so the next optimization is performed.

4) Randomly select several node pairs in the set, and create new direct edges

Here, there is only one element left in the reduced set, so one node pair is extracted, namely (v10, v25), and an undirected and weightless edge v10-v25 is added to the network to form a new network.

FIG. 3 is a schematic diagram of performing optimization in Embodiment 1 of the present invention.

5) A new round of optimization

Calculate the diameter of the new network and the corresponding node pair, and find that the diameter is 6, and the corresponding node pair set is {(v10,v49)}. The obtained shortest path number set is {9}. Extract the node pairs whose shortest path number is only 1 to get an empty set. Determine the number of elements in the set, which is less than 1, so the optimization ends.

The above is an example analysis of dynamic optimization of the worst performance of the network.

Claims (5)

1. a kind of dynamic optimization method of the worst connectivity performance of network, is characterized in that, comprises the following steps, Step 1: Calculate the network diameter and obtain the set of node pairs corresponding to the diameter; Step 2: According to the set of node pairs obtained in step 1, count the number of shortest paths between each node pair, and obtain a set of shortest path numbers corresponding to the node pairs; Step 3: According to the shortest path number set obtained in Step 2, reduce the node pair set obtained in Step 1 to obtain the node pair in the worst case of connectivity; judge whether it is not according to the number of elements in the set after reduction perform optimization; Step 4: According to the situation of performing optimization in the judgment result obtained in Step 3, randomly select several node pairs in the set obtained in Step 3, and add a directly connected edge respectively, thereby generating a new network; then return to Step 1, According to this cycle, dynamic optimization is achieved. 2. method according to claim 1 is characterized in that, in described step 1, the step of calculating network diameter and obtaining the node pair set corresponding to diameter is: Step 1: Calculate the length of the shortest path between any two nodes in the network; d _ij =min{P ¹ _i→j ,P ² _i→j ,...,P ⁿ _i→j } where d _ij represents the length of the shortest path from node i to node j (i<j), n is the statistical value of the number of shortest paths from node i to node j, and P ^k _i→j represents the kth path from node i to node j The length value of each path, that is, the number of edges passed by the kth path; {P ¹ _i→j , P ² _i→j ,...,P ⁿ _i→j } is the length of all paths from node i to node j a collection of values; Step 2: Calculate the network diameter; According to the length of the shortest directional path between two nodes obtained in step 1 in step 1, calculate the maximum length of the shortest path between any two nodes in the network, that is, the diameter: D= _maxdij where D represents the diameter of the network; maxd _ij represents the maximum value of the shortest path length between any two nodes; Step 3: Obtain the node pair set corresponding to the diameter; According to the diameter obtained in step 2 in step 1, find the set of node pairs corresponding to the diameter, and the steps are: U={(i, j)|d _ij =D} Wherein U represents a set of node pairs corresponding to diameters, and (i, j) represents a node pair that satisfies the condition d _ij =D. 3. method according to claim 2, is characterized in that, the step that obtains the shortest path number set corresponding to node pair in described step 2 is: According to the set of node pairs obtained in step 3 in step 1, count the number of shortest paths between each node pair, and obtain the set of shortest paths corresponding to the node pairs. The steps are: V={ M _ij |(i, j)∈U} Wherein M _ij represents the set of shortest path numbers corresponding to the node pair (i, j); V represents the set of M _ij . 4. The method according to claim 3, characterized in that, in the described step 3, the steps of reducing the set of nodes and judging whether to perform optimization are: Step 1: Obtain the node pair in the worst case of connectivity; According to the set of node pairs obtained in step 3 in step 1, extract the node pair with only one shortest path, and the steps are: U'={(i, j)|M _ij =1} where U' represents the node pair set after U is reduced, and _Mij = 1 means that there is only one shortest path between the node pair (i, j); in this case, the minimum cut set of the edge between the node pair is 1. Destruction of any node and edge on the path will lead to an increase in the diameter of the network, which will worsen the worst connectivity performance of the network; Step 2: Determine whether to optimize; According to the set of node pairs obtained in step 1 in step 3, it is judged whether to optimize according to the number of elements in the set. The steps are:

in

Indicates that the proposition "the number of elements in U' is greater than or equal to 1" is true or false; T indicates that the proposition judgment result is true, that is, the next optimization stage is entered; F indicates that the proposition judgment result is false, that is, the optimization is terminated. 5. The method according to claim 4, wherein the step of performing optimization in the described step 4 is: According to the situation that the optimization needs to be performed in step 2 in step 3, the optimization is performed, and the steps are: Randomly select t node pairs (i, j) in U' and connect them directly with an edge; among them, t<card(U'); here, the optimization implementer is given a certain degree of freedom to select each node according to the actual situation. The number of new edges added for the suboptimization.

Images