CN108833130A - A Method of Calculating Node Importance Degree in Power CPS System Based on Analytic Hierarchy Process - Google Patents

Abstract

The invention relates to a method for calculating the importance of nodes in a power CPS system based on the analytic hierarchy process, which analyzes the target and establishes a hierarchical structure through the analytic hierarchy process, and establishes a judgment matrix according to the evaluation index data of the importance of information network nodes; The judgment matrix calculates the weight between each adjacent two layers, and finally obtains the weight order between the bottom element and the target, and thus obtains the importance ranking of the nodes. The invention can solve the problem of how to use multiple indexes to evaluate the importance of nodes, and also reduces the subjectivity of weight selection to a certain extent, and obtains more objective and comprehensive results.

Description

A Method of Calculating Node Importance Degree in Power CPS System Based on Analytic Hierarchy Process

technical field

The invention relates to a method for calculating the importance of information network nodes in an electric power CPS system, in particular to a method for calculating the importance of information network nodes in an electric power CPS system based on analytic hierarchy process, which belongs to the field of nanotechnology.

Background technique

Cyber-Physical Systems (CPS, Cyber-Physical Systems) is a multi-dimensional complex system that integrates computing, network and physical environment. Through the organic integration and in-depth cooperation of 3C (Computer, Communication, Control) technology, it realizes real-time perception, Dynamic control and information services. Completing the integrated design of computing, communication and physical systems can make the system more reliable, efficient and collaborative in real time. Power CPS fully integrates the physical network and information network of the power system, and realizes the seamless integration of computing, communication, sensing, control and power systems through the mutual coordination of computing equipment, sensing equipment, communication equipment, and physical equipment.

The process of coupling and interaction between the information system and the power physical system in the power grid CPS is very complicated. With the continuous development of complex network theory research, the importance evaluation of nodes in the information side system has begun to receive widespread attention. There are many methods to measure the importance of nodes. Most of the commonly used methods are proposed for a specific problem. They describe the importance of nodes in a specific network from different angles and different purposes, and each has its own advantages and disadvantages. . For example, the evaluation method based on degree centrality emphasizes the number of connections between nodes and adjacent nodes, but in the power CPS information network, a node plays a more important role in information flow, so nodes with the same degree, in the network The degree of importance in is not necessarily the same; betweenness describes the importance of nodes in manipulating information flow in the network, and is closely related to the shortest path through nodes. However, in the actual network, most information flows randomly according to their own wishes, not along the shortest path. , so it is not accurate to evaluate the importance of nodes through betweenness. Proximity centrality takes into account the proximity of a node to other nodes, which plays a very important role in the transmission and acquisition of information. The shorter the distance from other nodes, the higher the proximity centrality. In a centralized network, it can more accurately discover the central node, but it is not suitable for some random networks. At the same time, complex networks are ever-changing in practical applications, and it is difficult to describe the importance of nodes in the network by a single indicator.

Contents of the invention

The purpose of the present invention is: aiming at the defects existing in the prior art, a method for calculating the importance of nodes in the electric power CPS system based on the analytic hierarchy process is proposed to solve the problem that a single index cannot be used to measure the importance of a certain node in the electric power CPS system.

In order to achieve the above purpose, the present invention provides a method for calculating the importance of nodes in the power CPS system based on the analytic hierarchy process, which analyzes the target and establishes a hierarchical structure through the analytic hierarchy process. According to the evaluation index of the importance of information network nodes Establish a judgment matrix based on the data; calculate the weight between each adjacent two layers according to the judgment matrix of each layer, and finally obtain the weight order between the bottom element and the target. The specific steps are as follows:

Step 1. Analyze the multi-objective decision-making problem of node importance in the information network, select three commonly used indicators for calculating the importance, including degree centrality, betweenness centrality and proximity centrality; and use the analytic hierarchy process to establish Hierarchical hierarchy;

Step 2. Calculate the DC, BC, CC value;

Step 3. After pairwise comparison of each index, the relative order of each evaluation index is arranged according to the nine-level proportional scale, and the judgment matrix of the evaluation index is sequentially constructed;

Step 4, carry out consistency check to the judgment matrix in step 3;

Step 5, using the eigenvector method to obtain the weight value of each layer to the dominant element of the previous layer;

Step 6. Synthesize the obtained weight values to obtain the comprehensive weight value of the bottom element to the target, that is, to obtain the importance ranking of nodes

Furthermore, the multi-objective decision-making problem is divided according to the hierarchical structure, including at least three levels of objectives, the first level of target level is node importance, the second level of criterion level is the evaluation index for node importance, respectively, degree centrality , betweenness centrality and proximity centrality, the third layer scheme layer is based on 25 basic nodes in the connected graph.

Further, in the step 2, the definitions of the three indicators for calculating the importance of nodes are:

(1) The degree of a node in a complex network refers to the total number of edges connected to this node, and the degree centrality of a node refers to the sum of the number of neighbor nodes of a node, which reflects that if a node The more neighbor nodes there are, the greater the influence of this node, that is, the greater the degree of the node, the greater its importance; the degree centrality of node i in the network is defined as:

Among them, i represents the requested node, j represents all other nodes, N represents the total number of nodes in the entire network, X _ij represents the connection relationship between node i and node j, if two nodes are connected, it is 1, otherwise , then it is 0;

(2) In the shortest path of all node pairs in a complex network, if the number of shortest paths passing through a node is more, then this node is more important, so the betweenness centrality of a network node is defined as:

Among them, g _st is the number of all shortest paths from node s to node t, and g _st (i) is the number of shortest paths passing through node i among the shortest paths from node s to node t; is the formula used to normalize the betweenness, and N is the total number of network nodes;

(3) The proximity centrality of a node represents the reciprocal of the sum of the shortest distances between the node and all other nodes in the complex network. The smaller the average distance between a node and other nodes, the greater the proximity centrality of the node. defined as:

Among them, d _ij represents the shortest distance between node i and node j.

The nine-level proportional scale is defined as: when two elements are compared with each other, take one element u _i as 1, if compared with the previous layer, u _i and u _j are the same, then u _j is recorded as 1; if u _j is better than u _i , u _j is recorded as 3; u _j is better than ui, u _j is recorded as 5; u _j is obviously better than u _i , u _j is recorded as 7; if u _j is much better than u _i , Then u _j is recorded as 9; 2, 4, 6, and 8 are cases between 1, 3, 5, 7, and 9. Comparing all the lower elements that are related to a certain element in the upper layer one by one, and arranging the comparison results of each element with each element in a row, a square matrix A=(a _ij ) _n×n can be obtained, which is called a pairwise comparison matrix ; Suppose the ratio of u _i to u _j is a _ij , then the ratio of u _j to u _i should be a _ji =1/a _ij , so the pairwise comparison matrix A is also called a positive and reciprocal matrix.

Further, in the step 4, the step of consistency check is:

Step 4.1, calculate the consistency index CI of the judgment matrix:

Among them, λ _max is the maximum eigenvalue of the judgment matrix, and n is the number of rows and columns of the judgment matrix.

Step 4.2, look up the corresponding index value in the value table of the consistency index RI;

Step 4.3, calculate the consistency ratio CR:

When CR<0.1, it is considered that the consistency of the judgment matrix is acceptable, otherwise the judgment matrix should be corrected.

Further, in the step 5, the step of using the eigenvector method to obtain the weight value of each layer to the previous layer is,

Step 5.1, calculating the maximum eigenvalue λ _max of the judgment matrix;

Step 5.2. Determine whether the judgment matrix belongs to the positive eigenvector of the eigenvalue λ _max , that is, the eigenvector whose components are all greater than 0, and normalize it, and the obtained vector is the weight vector.

Compared with the prior art, the present invention adopts the above technical scheme and has the following technical effects: the present invention utilizes multiple importance evaluation indexes of nodes: degree centrality, betweenness centrality and proximity centrality to comprehensively evaluate the importance of network nodes , compared with using a single evaluation index, the sorting results can be obtained more accurately.

Description of drawings

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

Fig. 1 is a topological diagram of the electric power CPS information network in the present invention.

Fig. 2 is a hierarchical structure diagram established in the present invention.

Detailed ways

Specific embodiments of the present invention are described in detail below, but it should be understood that the protection scope of the present invention is not limited by the specific embodiments.

This embodiment provides a method for calculating the importance of nodes in a power CPS system based on the analytic hierarchy process. Based on the power CPS information network used to calculate the importance of nodes in Figure 1, the secondary equipment layer and the corresponding secondary equipment layer of a power CPS system are The communication layer is simplified, and the object of the present invention is to calculate the importance of these 25 communication nodes in the network.

Specific steps are as follows:

Step 1: Analyze the multi-objective decision-making problem of node importance in the information network, and select three commonly used indicators for calculating the importance—degree centrality, betweenness centrality, and proximity centrality; and use the analytic hierarchy process to establish a hierarchical level structure, the established hierarchical structure is shown in Figure 2;

Step 2: Calculate the DC, BC, CC value, through data search, we can know that the definitions of the three indicators are as follows:

(1) The degree of a node in a complex network refers to the total number of edges connected to this node, and the degree centrality of a node refers to the sum of the number of neighbor nodes of a node, which reflects that if a node The more neighbor nodes there are, the greater the influence of this node, that is, the greater the degree of the node, the greater its importance. The degree centrality of nodes is the simplest, most intuitive, and least computationally complex index to describe the importance of nodes in the network. The degree centrality of node i in the network can be defined as:

Among them, i represents the requested node, j represents all other nodes, N represents the total number of nodes in the entire network, X _ij represents the connection relationship between node i and node j, if two nodes are connected, it is 1; otherwise , then it is 0.

(2) Among the shortest paths of all node pairs in a complex network, if the number of shortest paths passing through a node is more, then this node is more important. According to this idea, Freeman proposed the betweenness centrality of network nodes, which is defined as:

Among them, g _st is the number of all shortest paths from node s to node t, and g _st (i) is the number of shortest paths passing through node i among the shortest paths from node s to node t. is the formula used to normalize the betweenness, and N is the total number of network nodes.

(3) The proximity centrality of a node means the reciprocal of the sum of the shortest distances between the node and all other nodes in the complex network. The smaller the average distance between a node and other nodes, the greater the proximity centrality of the node. It is defined as:

Among them, d _ij represents the shortest distance between node i and node j.

The index data of 25 nodes can be calculated by Matlab software, as shown in Table 1.

Table 1 Index data of each node

Step 3: After pairwise comparisons between each index, arrange the relative order of each evaluation index according to the nine-level proportional scale, and construct the judgment matrix of the evaluation index in turn;

Firstly, the data of degree centrality, betweenness centrality and proximity centrality of 25 nodes are subtracted in pairs, and then a nine-level proportional scale is introduced to analyze the results. The nine-level proportional scale is defined as: when two elements are compared with each other, take one element as 1 (such as u _i ), if compared with the previous layer, u _i and u _j are the same, then uj is recorded as 1 ; u _j is better than u _i , u _j is recorded as 3; u _j is better than ui, u _j is recorded as 5; u _j is obviously better than u _i , u _j is recorded as 7; if u _j is much better than u _i , then u _j is recorded as 9; 2, 4, 6, and 8 are cases between 1, 3, 5, 7, and 9. Comparing all the elements of the lower layer that are related to an element of the upper layer one by one, and arranging the comparison results of each element with each element in a row, a square matrix A=(a _ij ) _n×n can be obtained, which is called a pairwise comparison matrix . Assuming that the ratio of u _i to u _j is a _ij , then the ratio of u _j to u _i should be a _ji =1/a _ij , so the pairwise comparison matrix A is also called a positive and reciprocal matrix.

For example, when processing the data of the degree centrality index, the minimum difference obtained is 0.04, and the maximum difference is 0.20. Then set the difference series between 0 to 0.05 as 1; the difference series between 0.06 and 0.1 as 5; the difference series between 0.11 and 0.15 as 7; the difference between 0.16 and 0.2 The number of series is 9. 2, 4, 6, and 8 are cases between 1, 3, 5, 7, and 9. Then the final comparison matrix of the bottom element (25 nodes) compared with the degree centrality element of the upper layer is:

In the same way, the third layer elements (25 nodes) can be compared with the betweenness centrality elements of the previous layer and the comparison matrix B and C of the close centrality elements. A, B, and C are the third layer and Comparison matrix between the second layer.

Then according to the definition of the three indicators, the importance ranking of the three indicators is given: betweenness centrality > degree centrality > closeness centrality, then the comparison matrix D of the second layer with respect to the first layer is:

Step 4: Carry out a consistency check on the judgment matrix;

First calculate the consistency index CI of the judgment matrix:

Among them, λ _max is the maximum eigenvalue of the judgment matrix, and n is the number of rows and columns of the judgment matrix. Because the degree centrality comparison matrix A has a maximum eigenvalue of 26. Secondly, look up in the value table of the consistency index RI and find that when n=25, the corresponding index value RI is 1.6556, then it can be seen that the consistency index CR=0.02<0.1, indicating that the matrix A is acceptable. Similarly, it can be known that the three comparison matrices B, C, and D are also acceptable.

Step 5: Use the eigenvector method to obtain the weight value of each layer to the previous layer; through Matlab calculation:

After normalization, the eigenvector of the largest eigenvalue of matrix A is W ₁ =[0.0248, 0.0248, 0.0248, 0.0962, 0.0248, 0.0248, 0.0248, 0.0554, 0.0102, 0.0102, 0.0102, 0.0102, 0.0102, 0.0102, 0.0902 0.0554, 0.0102, 0.0102, 0.0248, 0.2097, 0.1470, 0.0248, 0.0248, 0.0248];

The eigenvector of the largest eigenvalue of matrix B after normalization is W ₂ =[0.0144, 0.0134, 0.0565, 0.1030, 0.0158, 0.0174, 0.0917, 0.1146, 0.0096, 0.0096, 0.0096, 0.0096, 0.0096, 0.0096, 0.00796, , 0.0316, 0.0096, 0.0096, 0.0377, 0.1148, 0.0513, 0.0225, 0.0377, 0.0144];

The eigenvector of the largest eigenvalue of matrix C after normalization is W ₃ =[0.0180, 0.0107, 0.0454, 0.0978, 0.0301, 0.0454, 0.1181, 0.1033, 0.0066, 0.0123, 0.0123, 0.0123, 0.0086, 0.0086, 0.00876, , 0.0153, 0.0066, 0.0362, 0.0635, 0.0362, 0.0230, 0.0301, 0.0635, 0.0404];

The eigenvector of the largest eigenvalue of the matrix D is W ₄ =[0.1884, 0.7306, 0.0810] after normalization.

Step 6: Synthesize the obtained weight values to obtain the comprehensive weight value of the bottom element to the target. Because the weight value vectors of the third layer to the second layer are W ₁ , W ₂ , W ₃ respectively, and the weight value vector of the second layer to the first layer is W ₄ , so the 25 nodes of the third layer are relative to the first layer Importance weight value vector W ₅ =0.1884*W ₁ +0.7306*W ₂ +0.0810*W ₃ =[0.0166, 0.0153, 0.0496, 0.1012, 0.01860.0210, 0.0812, 0.1025, 0.0094, 0.0099, 0.0099, 0.009 , 0.0096, 0.0096, 0.1589, 0.0347, 0.0094, 0.0118, 0.0373, 0.1263, 0.0670, 0.0235, 0.0373, 0.0184].

The weight between the bottom layer and the target layer represents the importance of the nodes. It can be seen from the data that the most important nodes are 16 nodes.

In addition to the above-mentioned embodiments, the present invention can also have other implementations. All technical solutions formed by equivalent replacement or equivalent transformation fall within the scope of protection required by the present invention.

Claims (6)

1. the method for calculating electric power CPS system interior joint different degree based on analytic hierarchy process (AHP), it is characterised in that：It is carried out for target It analyzes and passes through analytic hierarchy process (AHP) and establish recursive hierarchy structure, established according to the evaluation index data of information network pitch point importance Judgment matrix；The weight between every adjacent two layers is calculated according to every layer of judgment matrix, finally obtains bottom element and target Between weight order, specific step is as follows：

Step 1, for information network interior joint different degree, this decision-making problem of multi-objective is analyzed, and is selected and is calculated different degree Three common counters, including degree centrality, betweenness center and close to centrality；And Recurison order hierarchy is established using analytic hierarchy process (AHP) Structure；

Step 2, according to degree centrality (DC), betweenness center (BC), close to these three calculate node different degrees of centrality (CC) Index definition, calculate DC, BC, CC value of each node in network-in-dialing figure；

Step 3, to being compared two-by-two between each index after, be ranked the relative superior or inferior of each evaluation index by nine grades of proportion quotieties Sequentially, the judgment matrix of evaluation index is successively constructed；

Step 4 carries out consistency check to the judgment matrix in step 3；

Step 5 seeks the weighted value that each layer dominates element to upper one layer using feature vector method；

Step 6 synthesizes obtained weighted value, obtains bottommost element to the synthetic weights weight values of target to get to section The importance sorting of point.

2. the method according to claim 1 for calculating electric power CPS system interior joint different degree based on analytic hierarchy process (AHP), special Sign is：In the step 1, decision-making problem of multi-objective is divided according to recursive hierarchy structure, including at least three layers of target, the One layer of destination layer is pitch point importance, and second layer rule layer is the evaluation index for pitch point importance, respectively degree centrality, Betweenness center and close to centrality, third layer solution layer be based on 25 base nodes in connected graph.

3. the method according to claim 1 for calculating electric power CPS system interior joint different degree based on analytic hierarchy process (AHP), special Sign is：In the step 2, the definition of the index of three calculate node different degrees is：

(1) degree of a node refers to the total number on the side being connected with this node in complex network, then the degree center of node Property refer to the sum of the number of neighbor node an of node, reflection be if the neighbor node of a node is more, The influence power of this node is bigger, i.e. the degree of node is bigger, and importance is bigger；The degree centrality of nodes i is fixed Justice is：

Wherein, i indicates that required node, j indicate that other all nodes, N indicate the sum of whole network interior joint, X_ijIt indicates Connection relationship between node i and node j is 1 if two nodes are connected, conversely, being then 0；

(2) in complex network in the shortest path of all nodes pair, if more by the shortest path number of a node, that This node is more important, therefore the betweenness center of network node is defined as：

Wherein, g_stFor the number of all shortest paths from node s to node t, g_st(i) shortest path for being node s to node t The number of the middle shortest path by node i；It is the formula for betweenness is normalized, N is network node Sum；

(3) what node was indicated close to centrality is that the sum of shortest distance of other all nodes is fallen in the node and complex network Number, as soon as the average distance of node and other nodes is smaller, then the node is bigger close to centrality, is defined as：

Wherein, d_ijIndicate the shortest distance of node i and node j.

4. the method according to claim 1 for calculating electric power CPS system interior joint different degree based on analytic hierarchy process (AHP), special Sign is：In the step 3, nine grades of proportion quotieties are defined as：Assuming that two element u_iWith u_jWhen mutually comparing, with one of them Element u_iAs 1, if relative to upper one layer, u_iWith u_jCompare, quality is identical, then u_jIt is denoted as 1；If u_jCompare u_iPreferably, u_jIt is denoted as 3；u_j Good, the u than ui_jIt is denoted as 5；u_jCompare u_iObvious good, u_jIt is denoted as 7；If u_jCompare u_iIt is much better, then u_jIt is denoted as 9；2,4,6,8 be between 1, between 3,5,7,9 the case where.With the related all lower layer's elements of upper layer element one by one compared with, and each element with Each element comparison result, which is arranged in a row, then can be obtained a square matrix A=(a_ij)_n×n, referred to as comparator matrix two-by-two；If u_iWith u_jThan For a_ij, then u_jWith u_iThan should be a_ji=1/a_ij, therefore comparator matrix A is also referred to as positive reciprocal matrix two-by-two.

5. the method according to claim 1 for calculating electric power CPS system interior joint different degree based on analytic hierarchy process (AHP), special Sign is：In the step 4, the step of consistency check, is：

Step 4.1, the coincident indicator CI for calculating judgment matrix：

Wherein, λ_maxFor the maximum eigenvalue of judgment matrix, n is the ranks numerical value of judgment matrix.

Step 4.2 searches corresponding index value in the numerical tabular of coincident indicator RI；

Step 4.3 calculates consistency ration CR：

Work as CR<When 0.1, it is believed that the consistency of judgment matrix is acceptable, otherwise copes with judgment matrix and is modified.

6. the method according to claim 1 for calculating electric power CPS system interior joint different degree based on analytic hierarchy process (AHP), special Sign is：In the step 5, seek each layer using feature vector method is to the step of upper one layer of weighted value,

Step 5.1, the maximum eigenvalue λ for calculating the judgment matrix_max；

Step 5.2 is asked and judges that judgment matrix belongs to eigenvalue λ_maxPositive feature vector, i.e., feature of the component all greater than 0 to Amount, and normalized, gained vector is weight vectors.