Link importance assessment strategy based on improved $k$-core decomposition in complex networks

1.   Introduction

With the discovery of complex network properties such as scale-free, small worlds, and community modules ^[1,2,3], network science has begun to become a unified cognitive framework for various domains such as social groups, ecosystems, traffic operations and public opinion flow ^[4,5,6,7]. The complex network structure of these domains makes it necessary to understand more about the structure and dynamics of the system in order to recognize its regular features or promote its evolution. Real world networks have rich network elements and complex system characteristics, and how to improve their robustness by effective means has become one of the research focuses in the field of network science.

In current research on complex networks, the focus is often on the protection and enhancement of critical nodes, which have core structural properties and perform important functional tasks, furthermore, their removal from the network can have a significant impact on the connectivity and performance of the entire network. However, for a network or system, potential random failures and deliberate damage can also occur on critical links. For example, during communication, the occlusion of critical channels can result in ineffective dissemination of information; the disruption of key hydrogen bonds in the structure of a protein molecule can result in structural breakdown and changes in the properties of the entire polymer; the failure of critical cables in power transmission can cause regional power outages; the weather-related impassability of shipping lanes in the shipping system will cause flight delays ^[8,9,10,11]. According to the current study, betweenness centrality is more effective than other link importance assessment strategies, but it should be noted that betweenness centrality has a high computational complexity ($O(NM)$). Hence, the computational complexity and time consumption of the edge betweenness in large-scale networks may make it impossible to meet the application requirements. Therefore, it is necessary to explore other link importance assessment strategies with relatively low computational complexity in order to adapt to the trend of increasing size and complexity of real networks.

As a network hierarchical method, $k$-core decomposition can be applied to large-scale networks due to its low computational complexity, as it is an important tool to analyze the hierarchical structural characteristics of networks. To date, $k$-core methods have been applied in various fields such as social network architecture analysis, epidemic infectious disease propagation trend prediction, and Internet topology detection ^[12,13,14]. Meanwhile, Yilun ^[15] developed a theoretical framework based on the generalized $k$-core ($Gk$-core) theory to further investigate the robustness of $Gk$-core against different types of damage, and they systematically analyzed the organizing principles of network system robustness and stability. In the study described in ^[16], Sun proposed that the concept of link shell can be obtained by introducing the $k$-$shell$ values of link endpoints into the domain of link importance discovery and provided three different methods for defining link shells, namely $shell$-$max$, $shell$-$min$ and $shell$-$pro$. It was found through experiments that the link shell as a new link importance assessment strategy has a better damage effect in real networks. However, as a link importance measure, the link shell suffers from a single source of link information and coarse differentiation of link importance. In this study, we improved the link shell on topological overlap theory and developed the link $t$-$shell$ as a new reference indicator for link importance assessment strategies; the method, on the one hand, fuses the local interaction information of near-neighboring links to increase the multiplicity of information sources when a link evaluation is referenced and, on the other hand, optimizes the ranking granularity to solve the problem of a large number of links being distributed in the same shell in traditional link shell evaluation strategies. We also compared it with several commonly used link importance assessment strategies and conducted numerical simulations using real networks and random networks to explore the effectiveness of the related strategies.

2.   Materials and methods

2.1.   K-core decomposition algorithm with link shell

$K$-core decomposition is the classical decomposition method in graph theory ^[17]. The method iteratively removes the network according to the node degree until all nodes are divided into a certain level (shell), and the decomposition process is as follows:

First, the number of neighboring nodes for all nodes is calculated as the node degree. Next, all nodes with the node degree $1$ and their links are removed; after this process, there will be no nodes with only one neighbor node in the network, and the set of removed nodes is called $1$-$shell$ nodes. After that, the node degree is recalculated and all nodes in the current network with a node degree of 2 and the associated links are removed in the same way; after this process, there will be no nodes with only two neighbors in the network, and the set of removed nodes is called $2$-$shell$ nodes. Gradually increase the $k$ value and repeat this iterative deletion process until all nodes in the network are assigned to a certain set of shell nodes. Define the $KS$ value of a node to characterize the number of shell layers in which the node resides.

Based on the concept of node shells, Sun ^[16] defined three $shell$ based indicators. For link $l(i, j)$, let the node shells of Node $i$ and Node $j$ be $shell_{i}$ and $shell_{j}$, respectively. Define the three $shell$-based indicators $shell$-$max$, $shell$-$min$ and $shell$-$pro$ for the link, respectively, as follows:

In Figure 1, let the link $l(o, t)$ be an example. The shell values for Node $o$ and Node $t$ are $KS(o) = 2$ and $KS(t) = 3$, respectively, so we can get $shell$-$max$ = 3, $shell$-$min$ = 2 and $shell$-$pro$ = 6. Similarly, the values of $shell$-$max$, $shell$-$min$ and $shell$-$pro$ for the link $l(p, q)$ are 2, 2 and 4, respectively. In previous studies, $shell$ based link importance assessment strategies based on the formation of link shells were experimentally verified to be effective methods for disrupting large-scale systems with much lower computational complexity than mesoscopic centrality. However, we can find two shortcomings in the link shell indicator due to its derivation based on node shells; (a) The link $shell$ is based only on information about the topological location of links in the network, ignoring the effect of local interactions between near-neighboring links. (b) The granularity of link ranking based on link shells is large, and a large number of links are distributed in the same shell, it is not possible to specify the relative removal order of links at the same layer, which leads to ambiguous decision-making during damage and affects the effectiveness of network destruction. Therefore, this paper presents a new link importance assessment strategy link $t$-$shell$ for the above problems with the link $shell$.

2.2.   New link importance assessment strategy link t-shell

Onnela ^[18] argued that the more common neighbors a node has at both ends of a link, the more substitutable and less important is the link, and the weaker its connection strength, and the less important the link is. The essence of their research idea is the principle of minimum entropy, where importance is assessed based on the amount of information contained in the link in question. Based on this idea, a topological overlap algorithm was generated, which defined the topological overlap factor $TO$ as follows:

In Eq (2.4), $n_{ij}$ characterizes the number of common neighbors of Nodes $i$ and $j$. The existence of the common neighbors of Node $i$ and Node $j$ makes the following possible when link is blocked: information can still be propagated through the path formed by the common neighbor nodes; the larger the number of links that can be replaced, the lower the importance of the link is implied.

In Figure 2(a), for the link $l(d, e)$, the shared node union $M$ = $\{b, g\}$ between Node $d$ and Node $e$; then when $l(d, e)$ breaks, the path $p(d, b, e)$ and path $p(d, g, e)$ will take up the shortest path function for information flow. In other words, the topological functions between them have overlap.

The topological overlap algorithm considers the effect of local nearest neighbor links on link strength. However, there are limitations in the application scenario: when there are independent stray node pairs in the network, the denominator of the operation is 0. Therefore, this paper presents an improved the topological overlap algorithm and introduces the enhanced topological overlap coefficient called $ETO$ as follows:

where $n_{ij}$ also characterizes the number of common neighbors of Node $i$ and Node $j$. The denominator refines the granularity by using product aggregation, and the constant value $\alpha$ can prevent the undefined case in the case of independent node pairs. Previous validation experiments have shown that adjusting $\alpha$ within an appropriate range does not have a large impact on the assessment results, and 1 is chosen here as the default value.

Because $ETO$ can determine the link strength based on local information, the authors propose to combine the link $shell$ and $ETO$ to obtain a new link importance assessment strategy with a new ranking indicator called the link topological shell (labeled as $t$-$shell$), corresponding to three $t$-$shell$ based link indicators, as follows:

In Eqs (2.6)–(2.8), $t$-$shell$ based indicators are based on the link shell, which provides information on the location of links starting from the network hierarchy, and introduces link topology overlap coefficients in combination with local link information characterized by $ETO$. $\gamma$ is used as an influencing factor to determine the degree of aggregation bias for both types of information with a full spectrum of $[0, 1]$; the smaller the value of $\gamma$ the weaker the guidance information provided by the topology bias information during link evaluation, and when no subjective information bias exists, $\gamma$ is set to 1.

2.3.   Link importance assessment strategy

Most of the current methods for link importance assessment are based on the expansion of node indicators, such as $degree$-$pro$, but it has been found that when removing links based on this method, the cost of removing high product links is huge and the convergence rate is slow compared to removing high node degrees; this is because only a significant number of high product links are removed from the network, equivalent to the removal of the corresponding high node disruption effect. Betweenness centrality is considered to be the most effective link importance assessment strategy, and Newman ^[19] improved Freeman's node betweenness centrality ^[20] to propose edge betweenness centrality. Edge betweenness centrality is defined as the number of shortest paths between pairs of vertices running along an edge, and if there is more than one shortest path between a pair of vertices, each path has equal weight and the total path weight value is unitary. Edge betweenness centrality is defined as follows:

In Figure 2(b), for the path $p(b, c)$, its shortest path contains only one link, so the contribution in the edge betweenness centrality calculation of $l(b, c)$ is 1, while, for the shortest path $p(f, c)$, its shortest path contains three links, i.e., $l(f, d)$, $l(d, e)$ and $l(e, c)$, respectively; at this time, the contribution of $p(f, c)$ in the edge betweenness centrality calculation of the link $l(d, e)$ is 1/3.

Different link importance assessment strategies can be proposed based on different link evaluation indicators. In addition to those based on an evaluation indicator, random strategies exist to remove links from the network randomly. In this study, we aimed to develop a $t$-$shell$ based strategy by improving the $shell$ based strategy and explore its effectiveness.Next, we conducted simulated numerical experiments using real and random networks to verify the effectiveness of t-shell-based improvements and analyzed and compared the effectiveness of several types of strategies.

3.   Experimental simulation and numerical analysis

To verify the effectiveness of the new link strategy on complex networks, four real network systems from different domains were used for simulated damage experiments. 1) $USAir$ ^[21]: This dataset illustrates the relationship of terminal extension connections in the U.S. airline network. 2) $Email$ ^[21]: A mail network formed by the interconnectedness of communication relationships between emails. 3) $Proteins$ ^[22]: This is a network of interactions between proteins in humans. 4) $Facebook$ ^[23]: This dataset describes Facebook's social friendship network generated by user interaction behavior. The basic network properties for the four real networks are shown in Table 1.

Table 1 shows several important topological properties and the $k$-core decomposition results for the four experimental networks. $N$ and $M$ characterize the number of nodes and the number of links of the network, respectively; $CC$ is the average clustering coefficient for the network; $sl$-$avg$ characterizes the average of the shortest paths between the nodes in the network; $degree$-$max$ and $degree$-$pro$ denote the maximum and average values of node degrees in the network, respectively; $P_{\rm{inter}}$ indicates the proportion of links with different shells at the two endpoints; $P_{\rm{co}}$ characterizes the percentage of links with the same shell value at both end nodes.

3.1.   Indicator ranking monotonicity

Ranking monotonicity is the primary method for measuring the granularity of the analysis of assessment-type indicators. For a certain indicator, the higher the monotonicity of its ranking, the finer the granularity of the data evaluation and the higher the accuracy of the key elements' identification. In this paper, we use the ranking monotonicity indicator $M$ proposed by Bae ^[24], which is defined as follows:

According to the research idea of ranking monotonicity, the set of candidate solutions is first selected within the selection evaluation system, which, in this study, involves the selection of the set of candidate links. In Eq (3.1), the link importance indicator is applied to the target network to obtain the link importance score for each link in the network and the link importance ranking is obtained based on the score. The candidate link sets are selected in descending order of link scores, and the ratio of the candidate link set to the total link set is defined as $p$; $N_{p}$ denotes the size of the candidate link set. The parameter $I$ is the ranking vector for current importance assessment methods that quantifies the resolution of different ranking methods and $N_{i}$ is the number of links in the candidate set that have the same score in the evaluation indicator. The monotonicity $M(i)$ is evaluated in the range $[0, 1]$. The lower the ranking monotonicity of the link importance indicator, the worse the granularity of link importance identification; conversely, having a higher ranking monotonicity means that the metric is more accurate in identifying the importance of the link. In this study, we took $p$ = 1.0, i.e., we chose all links within the four real networks as the set of candidate links to maximize the calculation of indicator monotonicity. The monotonicity calculation results for $USAir$, $Email$, $Proteins$, and $FaceBook$ for a total of four real networks are shown in Figure 3.

Analysis of the monotonicity calculation results for the above link assessment indicators revealed that the monotonicity of the ranking based on the $t$-$shell$ indicators ranking method consistently outperformed the monotonicity of similar $shell$-based indicator ranking methods in the monotonicity ranking within four different domain networks, demonstrating a more granular identification of the relative importance of links. This ensures that the method is able to accurately assess links in more complex network systems, demonstrating that the fusion of global network information with topological overlap information can effectively support link importance assessment efforts.

3.2.   Damage simulation experiments on real-world networks

In the next experiments, eight different strategies were used, including a random damage (labeled as $random$) and seven deliberate importance assessment strategies, i.e., betweenness strategies (labeled as $betweenness$), three $shell$-based strategies (labeled as $shell$-$min$, $shell$-$max$, $shell$-$pro$) and three $t-shell$-based strategies (labeled as $t$-$shell$-$min$, $t$-$shell$-$max$, $t$-$shell$-$pro$). Here, the maximum connection component $S$ was used to characterize the network connectivity after link deletion; the ratio of deleted connections to total links in the network was characterized using $D$. Following deletion of links of the same size, the smaller $S$ indicates that the importance assessment strategy is more effective in destroying fewer nodes and links that still belong to the maximum component.

For the $USAir$ network, the simulated importance assessment effect is shown in Figure 4(a), where the $betweenness$ damage strategy shows the strongest damage in the network, while the $shell$-$max$ importance assessment strategy effect is better than $shell$-$min$ and $shell$-$pro$. However, the $t$-$shell$ based importance assessment strategy performed better than the $shell$ based attack strategy overall, proving that it is easier to identify important links in combination with local link information and achieve a better network deletion effect. For $Email$ in Figure 4(b), the $t$-$shell$-$max$ based importance assessment strategy achieved a better cyber damage effect in all phases, and the maximum component size of the network continuously decreased at a faster rate in the process of link deletion; it even outperformed the betweenness strategy in certain phases. In Figure 4(c), for $Proteins$, the $t$-$shell$-based indicators consistently outperformed the $shell$ based indicators on network deletion. For the $Facebook$ network, the $t$-$shell$-based strategy exhibited similar policy superiority; its simulated damage effect is shown in Figure 4(d). The $t$-$shell$-$max$ strategy was second only to the importance assessment strategy based on betweenness centrality, and there was nearly double the improvement in damage compared to the $shell$-based strategy; the difference in the robustness of different networks against these importance assessment strategies depends mainly on the different linking methods of the networks.

In the numerical simulation experiments involving link damage based on the above eight strategies, the dissimilar network connections were the main reason why the maximum component sizes of different networks exhibited different shrinkage rates. We can observe that the link deletion simulation with the betweenness strategy had particular advantages when applied to the $Proteins$ network compared to the other three networks. On the one hand, this is due to the fact that the $Proteins$ network had the smallest network average and low connectivity complexity. On the other hand, the clustering coefficient for the $Proteins$ network ($Min(CC)\{0.62, 0.61, 0.04, 0.61\}\geq 0.04$) was the smallest among the experimental networks; this means that there is no densely connected cluster of nodes formed locally in the network. The higher average shortest path ($Max(sl$-$avg)$ $\{2.738, 2.759, 3.843, 3.692\}\geq 3.843$) also shows the weak connectivity of this network in terms of global connectivity. The above performance means that the $Proteins$ network does not form a more complete small world system like the other three networks.

The robustness exhibited by the network against link damage is also related to the heterogeneity of the links. According to the $k$-core decomposition method, there are two types of links in the network: co-layer links and inter-layer links. The nodes at both ends of the co-layer link have the same shell value and connect nodes with similar network locations; the nodes at both ends of the inter-layer link have different shell values and then assume the connection function in different shell layers. The study in ^[16] demonstrated that removing links connecting different layers in the network will accelerate network collapse. We compared the percentage of inter-layer links in the total links in each network, as follows: $P_{\rm{inter}}(Proteins)$ = 0.81] $>$ [$P_{\rm{inter}}(Email)$ = 0.74] $>$ [$P_{\rm{inter}}(USAir)$ = 0.68] $>$ [$P_{\rm{inter}}(FaceBook)$ = 0.54]. This is one of the reasons why the betweenness strategy achieved the best performance for the $Proteins$ network.

We need to note that the degree of aggregation of the local links in the network will affect how well the $t$-$shell$ indicators are optimized, unlike the $shell$ indicators. This is because a higher degree of aggregation of local links means that there is a greater likelihood of link topology overlap in the network, which allows the $t$-$shell$ indicators to gain more supporting information about the local characteristics of the network and better refine the link importance identification accuracy; furthermore, the degree of aggregation of the local links in the network can be characterized as the size of the average network clustering coefficient.

3.3.   Damage simulation experiments on scale-free network

To further verify the effectiveness of the $t$-$shell$-based strategy in link damage, further simulation experiments were conducted using scale-free (labeled as SF) random networks. We generated four scale-free random networks with an exponentially increasing average degree ($degree$-$avg$ = {2, 4, 8, 16}) and found that $tshell$-$max$ was the most destructive importance assessment strategy. This is because the $t$-$shell$-based strategy takes into account the link strength and delineates more clearly the order of destruction in the same layer of links.

In Figure 5, the numerical simulation results show that, as the average degree of nodes increases, it will generate higher link complexity in the network, making the robustness against target link damage higher in the case of removing the same proportion of links. Additionally, the critical network links in the scale-free random networks have a close correlation, so they performed better in the process of removing the top links; furthermore, the smaller the network average, the greater the role of these critical links.

The experimental results from link directed damage on real networks with scale-free random networks show that betweenness is indeed the most effective strategy to date for attacking complex networks at the link level. However, in the case of large-scale network applications, the $betweenness$-based link importance assessment strategy may not meet the application requirements due to its high computational complexity; the $shell$-based indicator proposed by Sun is considered as an effective alternative to destroy large-scale networks due to its much lower computational complexity and better destructive effect than the betweenness method. Compared with $shell$-based indicators, the proposed $t$-$shell$-based indicators combined with topological overlap information offer more accurate identification granularity and a better network-breaking effect without changing the computational complexity; this can provide new ideas for large-scale network destruction strategies.

4.   Conclusions

In this study, we incorporated the topological overlap theory to improve the $shell$-based indicator and developed a new target link importance assessment indicator called the link topological shell ($t$-$shell$). The effectiveness of various importance assessment strategies was compared by performing numerical simulation experiments within real networks and scale-free random networks. The experimental results show that the improved $t$-$shell$ based indicator, which was obtained by combining link global location information and local link strength information, has a better network destruction effect but the same computational complexity as the $shell$-based indicator. Therefore, $t$-$shell$ based strategies can provide new ideas for crippling large-scale networks and systems, meaning that the approach can be targeted to guide the protection and hardening of critical links in the network, thus building systems with higher robustness.

The networks used in the above experiments all have the characteristics of a powerless and directionless network, but $t$-$shell$ based indicators can also be extended to more application scenarios. Examples include weighted networks, directed networks, multilayer networks, network of network (NON), etc^{[25,26,27,28]}. However, the indicators must be adjusted accordingly to meet the application requirements of relevant scenarios. Most of the current targeted network importance assessment strategies assess the robustness of the target network based on how the giant components change during the network damage. However, when it comes to specific application scenarios, more tailored robustness assessment tools are often needed, such as the $Gk$-core structure, which is an ideal structure to reflect the impact of virus or epidemic propagation on network resilience ^[29]. Meanwhile, new damage unit-based network metrics such as the generalized $k$-core^[15] and node link visualization^[30] have been proposed, and as a next step we will continue to investigate how we can rely on new damage units and indicators to assess the network robustness of more diverse network systems and explore the distribution patterns of key components, which we consider to be very valuable.

Conflict of interest

The authors declare there is no conflict of interest.