Sage Journals: Discover world-class research

Abstract

There are shortcomings in the node contraction method used in the evaluation of the importance of weighted network nodes. To avoid those defects, an improved importance evaluation method is proposed. The differences of edge weight have impacts on importance of nodes and edges; therefore, two improvements are made in defining the network cohesion and the importance of edges of network G* using weighted shortest distances. In this paper, this improved method is analyzed and validated through a comparative analysis. The influence of the coefficients on the importance and relative importance of the nodes is analyzed by adjusting the proportional coefficient and the weight coefficient. The results show that the improved method can provide more comprehensive and accurate assessment of the importance of weighted network nodes without increasing the computational complexity.

Keywords

Weighted network node importance edge weight node shrinkage method network cohesion degree

Introduction

In recent years, with the rise of complex network research, the complex network survivability has become a key branch of research,^1–3 in which node importance assessment is a basic content of the study of survivability. Complex network is essentially different. The key topology of each node in the network is different.⁴ A few key nodes play a vital role in the overall performance of the network. Research shows that when the 5% core node is attack, the network will be paralyzed,⁵ so the importance of complex nodes in the network assessment, accurate excavation of the network of important nodes, to improve the network survivability has a very important theoretical help.

The existing network node importance evaluation research is divided into two categories: (a) Based on the social network analysis method, in order not to undermine the overall structure of the network to explore the importance of nodes, the central network to measure the central indicators, such as degree and (b) based on the system of scientific analysis method, by deleting the node after the damage to the network to determine its importance, such as node deletion, node shrink method, etc.⁶ The system node shrinkage method in the scientific analysis method⁷ overcomes the drawbacks of the node deletion method, taking into account the connection degree of the node and the location of the node, and the evaluation method is intuitively effective for the weighted network with the actual network characteristics, the weighted network. The nodal shrinkage method⁸ has also been proposed. In Choe et al.,⁹ the importance of node joint is considered, and the importance of node is introduced.

The definition of network cohesion in Zhang et al. and Choe et al.^8,9 is based on the average shortest distance after the weighted network is reduced to an unallocated network on the basis of maintaining the weighted network route, and there is no in-depth consideration of the importance of the difference which can cause the same evaluation index of nodes in different positions and cannot distinguish the importance. For the above problems and the impact of edge weights on the nodes and the edges, the weighted shortest distance of the weighted network is applied to define the network cohesion, the network G* is weighted with edge weight function, and improved weighted network node importance evaluation of the node shrinkage method is proposed in this paper. Finally, the effectiveness and feasibility of the improved method are analyzed through examples.

Weighted network model

In real life, there is a difference in the intensity of the interaction between many individuals in the real system. It cannot be simply described by the use of the right less network, and the weight of the interaction is introduced to form the weighted network. The weighted network model is represented by G = (V, E, W), where V = {v₁, v₂, …,v_n} is the set of nodes, E = {e₁, e₂, …, e_m}, W = {w_e1, w_e2, …, w_em} is the edge weight set, the number of nodes in the network is N = | V |, the number of edges is M = |E|.

When the real system is abstracted as a weighted network, it is necessary to consider the way of giving the weight. In dealing with the weight relation, we usually use the different weights of the different rights or similarities. In the case of the exclusive right, the nodes with larger weight and greater distance show their relationship is looser; otherwise the nodes with smaller weight and closer distance provide closer relationship.⁸ For different empowerment methods, the definition of the characteristics of the network parameters is not the same. Similarly, when the weight is the same, the node strength is defined as the sum of the reciprocal of the edge weight $s u m i = \sum_{i \in N j} \frac{1}{w_{i j}}$ (N_j represents all adjacent nodes of node j); when the edge weight is similarity, the node strength is defined as edge. The sum of the weights is $s u m i = \sum_{i \in N j} w_{i j}$ , where the larger the value of the node's intensity, the closer the node is to the surrounding node. It is assumed that the nodes i and j are connected by the two weights for the w_ik and w_kj edges. The distance between nodes can be directly taken and k_ij = w_ik + w_kj; for similarity, the distance between nodes is defined as k_ij = 1/w_ik + 1/w_kj. On this basis, we can get weighted complex network average distance $A = \frac{1}{N (N - 1)} \sum_{i \neq j} k_{i j}$ . The undirected weighting network is discussed below, the network is applied to the different rights to give way.¹⁰

Node importance evaluation based on cohesion

The node contraction method based on network cohesion is first applied in assessing the importance of nodes in the absence less network. The convergence degree of the network is defined as the reciprocal of the number of nodes and the average shortest distance. In the weighted network, the weight of the weighted network is defined by⁸

\partial (G) = \frac{1}{Sum(G) \times A(G)} = \frac{1}{\sum_{i = 1}^{N} \frac{S u m i}{l_{i}} \times \frac{\sum_{i \neq j \in V} k_{i j}}{N (N - 1)}}

(1)

where Sum (G) is the sum of the average nodes' strength of the weighted network, A(G) is the average shortest distance after the weighted network is reduced to the unweighted network on the basis of maintaining the weighted network route, N is the number of nodes of the network; the strength of node i, l_i is the number of adjacent nodes of node i and k_ij is the least significant distance between node i and node j in weighted routing path.¹¹

On the basis of weighted network cohesion, the importance of defining node i IMP (i) is⁸

I M P (k) = 1 - \frac{\partial (G)}{\partial (G^{'} (i))}

(2)

where G'(i) represents the weighted network obtained by contracting node I. Shrinking node I means that the k_i nodes connected to node i are fused with i, that is, using a new node instead of k_i +1 nodes, the original with their associated edges are now associated with the new node,¹² edge weight for the contraction point and the peripheral node edge of the weight, if more than one side to reach the shortest path in the form of contraction. This article takes the least weight edge instead.¹³

On the basis of the above definition, the importance of node edge is further considered.¹⁴ First, the edge of the weighted network G is the node, the connection relation between each side is the edge, the network G is converted into the network G*. The degree of cohesion of the node shrinks the method of calculating the importance of each node in network G*.

The importance of the node itself and the importance of the edge are superimposed, and the importance of the improved node is defined^9,15

I M P (i) = a \times {I M P}_{n} (i) + β \times \sum_{j \in V_{θ}^{i}} I M P θ (j)

(3)

where IMP_n (i) represents the importance of node i in network G; IMP_e (j) represents the importance of node j in network G;¹⁶ M (i) e represents the node set in node G in G corresponding to node set in network G (

α + β = 1

), and ρ = α/β is the proportion coefficient of the importance of the node and the importance of the edge. The α and β are the weighting coefficients (α + β = 1).¹⁷

Node importance assessment method

Defects of existing node shrinkage method

The above-mentioned method of estimating the node shrinkage is to define the convergence degree of the weighted network based on the average shortest distance after the weighted network is reduced to the unweighted network on the basis of maintaining the weighted network route, and only the connection relation between the sides of the weighted network G. As the edge of network G, G is an unallocated network, which does not take into account the influence of the connection relation strength on G-edge, which reduces the influence of edge weight on the importance of the node itself and the importance of edge. The importance of the nodes cannot be accurately evaluated.¹²

Figure 1 shows the undirected weighted graphs with 1 node and 10 edges. Figures 2 and 3 are the weighted networks obtained by the contraction nodes v3 and v8, respectively. After calculation, $\partial (G' (3)) = \partial (G' (8))$ , the average shortest distance of the weighted network is reduced to the unweighted network on the basis of maintaining the weighted network route as shown in Figure 4, IMPe(1)=IMPe(9), IMPe(2)=IMPe(10), IMPe(3)=IMPe(8), using the formula (3) to be IMP (3) = IMP (8), that is, node v3 and node v8 have the same importance. From Figure 1 on the global understanding of network G can be seen, node v3 and node v8 have symmetrical positions but their corresponding edges have different weights, that is, the global role of node v3 and node v8 in the network is different, the importance of the two nodes can be distinguished, so the algorithm needs to be improved. The impact of edge weight should be further considered on the importance of nodes in order to carry out a more comprehensive and accurate assessment of the importance of the node.

Figure 1.

Topology structure of network G.

Figure 2.

Topology structure of network G’(3).

Figure 3.

Topology structure of network G’(8).

Figure 4.

The topological structure of the unweighted network G*.

Improved method of node importance assessment

Through the above analysis, this paper proposes two improved aspects of the algorithm based on the algorithm^9,18

(a) Redefine the cohesion degree $\partial^{ω} (G)$ of the weighted network

\partial^{ω} (G) = \frac{1}{s u m (G) \times A^{ω} (G)} = \frac{1}{\sum_{i = 1}^{N} \frac{S u m i}{l i} \times \frac{\sum_{i \neq j \in V} k_{i j}^{ω}}{N (N - 1)}}

(4)

In this case, $A^{ω} (G$ ）is the average shortest distance of the weighted network, $k_{i j}^{ω}$ is the weighted minimum distance between node i and node j, and the other definition parameters are the same as equation (1).

(b) When the network G is converted to network G*, the edge weights of network G* are calculated with the importance values of each side in G. If there are two edges e1 and e2 connected in the weighted network G, the weights are w_e1 and w_e2. In the conversion of network G to network G*, the corresponding network G with edges e1 and e2 between two nodes has an edge, define the edge of the weight of (w_e1 • w_e2)^θ, that is, G* connected. The smaller the edge weight of the two edges e1 and e2, the smaller the edge weight between the nodes corresponding to the two edges when converting to the network G indicating that the connection between the two edges e1 and e2 is closer, ( $θ > 0$ ) determines the non-homogeneity of each side in the weighted network G*. When θ = 0, the corresponding edge weight is 1, and the weighting network G* degenerates into no right network; when θ > 0, the weights in the weighted network G* are different, and the larger the θ is, the greater the difference between the sides.¹⁹

Through the improvement of the above two aspects, the influence of the weight value on the importance of the node itself and the importance assessment of the edge is highlighted, so that the importance evaluation of the node takes into account the connection tightness of the node and the path position of the node. And finally according to the actual needs of the network by adjusting the scale factor β, the importance of nodes are accurately assessed.

The algorithm steps for improving the importance assessment method of the weighted network nodes are given below:

Calculate the sum (Sum(G)) of the average node intensities of the weighted network G;

Call the Floyd shortest path algorithm to calculate the weighted average shortest distance $A^{ω} (G)$ of the weighted network G;

Compute the initial weighted network cohesion $\partial^{ω} (G)$ of the network G;

For each node i (i = 1, 2, …, N) in the network G, the sum of the average node intensities Sum(G'(i)) and the weighted average of the nodes G'(i). The shortest distance $A^{ω} (G^{'} (i))$ ;

Calculating the weighted network concurrency degree $\partial^{ω} (G^{'} (i))$ of the network G'(i);

Calculate the importance of each node in the weighted network G IMPn (i);

Converting the weighted network G to the weighted network G*, repeating steps (a) to (f) calculating the importance of each node in the network G IMPe (j);

Set the weighting coefficients α and β to calculate the importance IMP (i) of each node in the weighted network G.

The core of the above-mentioned node importance evaluation algorithm is the calculation of network cohesion, and the time complexity is O (n³). For the importance of node edge, it is equivalent to calculating the importance of nodes in network G*, and the time complexity is O (n³), so the time complexity of the whole algorithm is O (n³). The time complexity of the improved method is much less than the time complexity of the weighted point method and the ideal computing power can be obtained for large weighted complex networks.⁸

Example analysis

For the weighted importance of the weighted network G shown in Figure 1, the network G is converted into the weighted network G* using the edge weighting method (θ = 1) proposed in this paper. The topology structure is shown in Figure 5. The scaling factor β = 6, respectively, using the weighted point of the method, the literature^8,9 and the improvement of the method of network G on the importance of the assessment of the results are shown in Figure 6.

Figure 5.

The topology of the weighted network G*.

Figure 6.

Comparison of the results of each node in Figure 1 under different evaluation methods.

From the overall ranking of the nodes in Figure 6, we can see that the method is not the same as the overall ranking of the nodes under the first three methods, and it is further compared with the literature⁹ considering the more comprehensive factors. The results show that the v3 and v8, v5 and v6 of the G symmetric topological position of the network are analyzed. The importance of the weight of the two methods is similar to that of the two methods should be differentiated, and the results of Table 1 show that the number of vx is the same as v8, v5 is the same as v6, and it is clear that the results of the three evaluation methods are not enough, which is v3 > v8 > v6 > v5, which is because the method of this method further considers the difference of the weight of the node to the importance of the node. In this paper, we can improve the importance of the nodes. Influence and the importance of the node make a more comprehensive and detailed distinction, which verifies the advantages of this method.

Table 1.

Comparison of the importance results of each node in Figure 1 under different evaluation methods.

Node number	Weighted point betweenness method		Weighted node contraction method		Improved nodal contraction method		Improved method in this paper
Node number	Importance	Ranking	Importance	Ranking	Importance	Ranking	Importance	Ranking
v1	0.2000	7	0.1086	8	0.1383	8	0.18418
v2	0.2000	7	0.518	7	0.1753	7	0.1912	7
v3	0.3667	5	0.4128	5	0.5228	3	0.5883	3
v4	0.4222	3	0.6161	2	0.7481	2	0.6533	1
v5	0.5333	1	0.4430	3	0.4737	5	0.3819	6
v6	0.5333	1	0.4430	3	0.4737	5	0.3923	5
v7	0.4222	3	0.6552	1	0.7816	1	0.5889	2
v8	0.3667	5	0.4128	5	0.5228	3	0.4531	4
v9	0.2000	7	0.0782	9	0.1122	9	0.1191	9
v10	0.2000	7	0.0782	9	0.1122	9	0.1191	9

The importance of node v6 is higher than that of node v5 because the edge weights of network G* are calculated with the importance values of each side. The connected edge importance of node v6 is higher than that of node v5, and the importance of node v6 itself is equal to that of node v5 itself. As a result, the importance of node v6 is greater than that of node v5. Node v3 is more important than v8 because the connection between nodes v8 and v9 and v10 is alienated, and node v3 is connected with its neighboring nodes that are relatively close; v3 shrinks the average shortest distance after the network to reduce the larger, with a higher degree of network cohesion, coupled with the v3 edge of the v8 even more important, making the node v3 more important node v4 than v7. The increase in importance is due to the fact that the global role of node v4 in the network is highlighted by taking into account the impact of edge weights on the importance assessment of nodes, and its own importance and edge importance are increased compared to node v7. The node v4 is more important than v7 for the entire network.

In order to further analyze the influence of the proportional coefficient β and the weight coefficient θ on the importance evaluation of the nodes, the importance degree of each node is normalized as the final evaluation index, and the network of Figure 1 is taken as the research object. Figure 7 shows the importance of each node under different weight parameters θ. It can be seen from Figure 6 that the importance and the relative importance of each node are different when the value of β changes. The importance of nodes V3, V4, V6 and V7 decrease with the increase of β, while the importance of nodes V8, V9 and V10 increase with the increase of β. In addition to this, the importance of node V8 is greater than that of V5 and V6 gradually when the value of β increases. As a result, different assessment results of the importance of nodes and edges can be achieved with different methods.

Figure 7.

Comparison of node importance under different weight parameters θ.

Figure 8.

Comparison of the importance of nodes under different proportional coefficients β.

It can be seen from Figure 7 that the importance of nodes v1, v2, v3, v5 and v6 increases with the increase of θ, and the importance of v7, v8, v9 and v10 decreases with the increase of θ. The importance of node v8 will gradually be less than the importance of v5 and v6, the importance of v4 and v7 will gradually be less than the importance of v3, which is the opposite of the increase in the importance of β. This is because the increase in β is the contribution of the importance of the nodes to the importance of the nodes, and the increase in the value of the nodes increases. The greater the difference between the edges of the network G and the importance of the contribution of the node will be increased. When using the method proposed in this paper, the ratio coefficient and the weight coefficient must be chosen properly according to the evaluation requirements to get accurate evaluation results.

Concluding remarks

The importance evaluation of weighted network is a basic and key content of the research on the survivability of weighted network. This paper analyzes the shortcomings of predecessor's nodal shrinkage method. In view of the shortcomings, we propose a method to define the network cohesion degree. The two methods of empowerment of the network G* can be improved by keeping the computational complexity not increasing, so that the evaluation takes full account of the influence of the edge weight difference on the importance of the node itself and the importance of the edge, taking into account the node. The reliability of the results is more reliable, and the next step will be based on the study of the evaluation and optimization of the survivability of the weighted network.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Vespignani

Complex networks: the fragility of inter dependency.

Nature 2010; 464: 984–985.

Caijinyao and Lingda

An improved model of survivability evaluation of communication network. Comput Eng Appl 2013; 49: 85–88.

Galloslk

Cohenr

and Argyrakisp

Stability and topology of scale-free networks under attack and defense strategies.

Phys Rev Lett 2005; 94: 188701.

Meng

and Li

Cooperative stabilization of linear multi-agent systems with limited communication data rate. In: Proceedings of the 2014 IEEE international conference on control and automation. Washington, DC: IEEE Computer Society, 2014: 1186–1191.

Hui

Liu

Zun

and Li

Yongjun.

A comprehensive evaluation method for the importance of complex network nodes based on multiple attribute decision making. J Phys 2013; 62: 20204–020204.

and Xie

Distributed coordination of multi-agent systems with quantized-observer based encoding-decoding. IEEE Trans Autom Control 2012; 57: 3023–3037.

Xie

et al . Distributed consensus with limited communication data rate. IEEE Trans Autom Control 2011; 56: 279–292.

Zhang

Kun

Shenhaibo Zhang

Hong

et al . Comprehensive evaluation of the importance of complex network nodes based on gray relational analysis. J Nanjing Univ Sci Tech 2012; 36: 579–586.

Choe

Lee

and Kim

HD.

Structural properties and inter-organizational knowledge flows of patent citation network: the case of organic solar cells [J].

Renew Sustain Energ Rev 2016; 55: 361–370.

10.

Wang

Jiasheng

Xiaoping

Liao

Wei

et al . An improved method for evaluating the importance of nodes in weighted complex networks. Comput Eng 2012; 38: 74–76.

11.

Renzhuoming

Shao Feng

Liu

Jianguo

et al . Study on importance measure of network node based on degree and clustering coefficient. Acta Physica Sinica 2013; 62: 128901 (1–5).

12.

Zhang

You

Li-Rong

and Zhang

Yong-Sheng.

Communication of cooperative network based on weighted scale-free network [J]. J Sys Eng 2015; 33: 68–73.

13.

Wang

Guo

Qiang

and Liu

Jianguo.

Node importance measurement based on weighting method [J/OL], http://arocmag.com/article/02-2018-05-015.html (accessed 25 May 2017).

14.

Gao

Man

Yinghong

and Zhang

Mingli.

Research on weighted network based on patent cooperation request data analysis, http://arocmag.com/article/02-2018-01-024.html (accessed 19 January 2017).

15.

Xie

et al . Distributed tracking of second-order multi-agent systems with measurement noise. Proceedings of the 2013 IEEE international conference on control and automation. Washington, DC: IEEE Computer Society, 2013: 1968–1972.

16.

and Xu

Quantized innovations Kalman filter: stability and modification with scaling quantization. J Zhejiang Univ Sci C 2012; 13: 118–130.

17.

Yanggang

Zhoutao

, Wangjie et al . Epidemic spread in weighted scale – free networks. Chin Phys Lett 2005; 22: 501–513.

18.

Cheng

Keqin

Shiwei

and Zhou

Jian.

Evaluation method of network invulnerability based on edge weight. Comput Eng Appl 2010; 46: 95–100.

19.

Sun

Dong

Zhang

Yong

Liu

Yadong

et al . Effects of node shrinkage and decomposition on node weighted complex network effectiveness evaluation. Ordnan Autom 2014; 33: 52–56.

An improved node algorithm based on the evaluation of weighted network node importance

Abstract

Keywords

Introduction

Weighted network model

Node importance evaluation based on cohesion

Node importance assessment method

Defects of existing node shrinkage method

Improved method of node importance assessment

Example analysis

Concluding remarks

Footnotes

Declaration of conflicting interests

Funding

References