2025 Volume 34 Issue 3
Article Contents

Yu Zhao, Bo Yang. Vital nodes identification method integrating degree centrality and cycle ratio[J]. Chinese Physics B, 2025, 34(3): 038901. doi: 10.1088/1674-1056/ada42d
Citation: Yu Zhao, Bo Yang. Vital nodes identification method integrating degree centrality and cycle ratio[J]. Chinese Physics B, 2025, 34(3): 038901. doi: 10.1088/1674-1056/ada42d

Vital nodes identification method integrating degree centrality and cycle ratio

  • Received Date: 09/10/2024
    Accepted Date: 07/12/2024
    Available Online: 01/03/2025
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures(23)  /  Tables(2)

Article Metrics

Article views(152) PDF downloads(0) Cited by(0)

Access History

Vital nodes identification method integrating degree centrality and cycle ratio

Abstract: Identifying vital nodes is one of the core issues of network science, and is crucial for epidemic prevention and control, network security maintenance, and biomedical research and development. In this paper, a new vital nodes identification method, named degree and cycle ratio (DC), is proposed by integrating degree centrality (weight α) and cycle ratio (weight 1 − α). The results show that the dynamic observations and weight α are nonlinear and non-monotonicity (i.e., there exists an optimal value α* for α), and that DC performs better than a single index in most networks. According to the value of α*, networks are classified into degree-dominant networks (α* > 0.5) and cycle-dominant networks (α* < 0.5). Specifically, in most degree-dominant networks (such as Chengdu-BUS, Chongqing-BUS and Beijing-BUS), degree is dominant in the identification of vital nodes, but the identification effect can be improved by adding cycle structure information to the nodes. In most cycle-dominant networks (such as Email, Wiki and Hamsterster), the cycle ratio is dominant in the identification of vital nodes, but the effect can be notably enhanced by additional node degree information. Finally, interestingly, in Lancichinetti–Fortunato–Radicchi (LFR) synthesis networks, the cycle-dominant network is observed.

1.   Introduction
  • The identification of vital nodes in complex networks is a long-standing problem in network science.[1–5] It is critical for controlling outbreaks, mitigating damage caused by attacks on transportation or telecommunications networks, and finding key genes for targeted receptor proteins and molecular biologics.[6,7] Although many simple and effective methods have been applied to these problems, they have their limitations due to the diversity of evaluation criteria. For example, degree centrality[8] is simple and intuitive but does not consider the global network structure, while betweenness centrality[9] and closeness centrality[10] consider the global structure but have high computational cost. Therefore, vital nodes identification is not a simple task, and it is particularly important to constantly explore new identification strategies. The LocalRank algorithm[11] identified vital nodes by considering the information contained in the fourth-order neighbors of each node. Kitsak et al.[12] obtained the coreness of node through k-core[13] decomposition, and believed that a larger coreness value indicates a more central location in network. Lv et al.[14,15] discussed an extension of the H-index concept to quantify the importance of nodes in its network. The H-index of a node is defined to be the maximum value H such that there exists at least H neighbors of degree no less than H. Node centrality ranking based on random walk is also a feasible method. For example, the PageRank algorithm[16] constructs a network based on the relationship between web pages, and distinguishes the importance of different websites through random walks. Lin and Zhang[17] proposed a random walk method based on non-retrospective centrality, NBCRW, in which walkers are more likely to visit neighbors with high non-retrospective centrality. TOPSIS[18] regarded centrality measures as the multi-attribute of a complex network and connected the multi-attribute to evaluate node importance.

    With the rapid increases of network scale and complexity, mining vital nodes faces new challenges, and the cycle structure within networks has also received more and more attention. The cycle structure is an important part of a network and is defined as a closed path with the same start and end nodes. It plays an important role in structure organization and function realization. Fan et al.[19] proposed the cycle ratio, which quantifies the importance of an individual node by simply measuring to which extent it is involved in the shortest cycles associated with other nodes, and it performs well in scaling and control processes. Zhao et al.[20] proposed a centrality measurement method based on high-order network characteristics, including higher-order cycle ratio (HOC), higher-order degree (HOD), higher-order H-index (HOH), and higher-order PageRank (HOP), to quantify and rank the importance of cliques in a network. The results indicate that clique ranking is superior to other metrics in maintaining network connectivity. Jiang et al.[21] ranked the importance of different cycles in a network by comparing the sensitivity of the Fiedler value (the second smallest Laplacian eigenvalue), and identified the key cycles that contributed the most to the dynamic behavior of the network. Shi et al.[22] believed that the nodes participating in the cycle basis might be crucial to propagation, and proposed the basic cycle number (NC) to quantify the importance of a node.

    Although the cycle ratio is effective in identifying vital nodes in a network, the obvious shortcoming of a cycle is that it cannot be applied to trees or tree-like networks. Even for ordinary networks, there may be some nodes that are not associated with any cycle, which have different effects but are given the same importance. The degree mainly evaluates the importance of a node based on the number of its direct neighbors, but ignores the vital bridging nodes with a small degree. Therefore, this paper proposes the index DC (degree and cycle ratio) to quantify the importance of single node by combining degree (weight α) and cycle ratio (weight 1 − α), so that all nodes with equal cycle importance will be updated by considering the degree of node at the same time. In order to evaluate the performance of DC, three dynamic processes, which include connectivity test,[23–25] epidemic spreading simulations[26,27] and targeted immunization control,[28–30] are used to test the identification effect on degree-dominant network and cycle-dominant network respectively, and the results are compared with other node-ranking methods. It is found that the dynamic observations and weight α exhibit non-monotonicity characteristics, meaning that there exists an optimal parameter α that enables DC to perform better than a single index in most networks. Finally, in the Lancichinetti–Fortunato–Radicchi (LFR) synthesis network model, the cycle-dominant network was observed.

    This paper is organized as follows. In Section 2, we introduce the vital node identification method DC and the model motivation. In Section 3, we use three dynamic processes, including node percolation, epidemic spreading and targeted immunization, to verify the rationality of the method, and carry out analysis and discussion. Then the robustness is simulated and analyzed in the LFR synthesis network. In Section 4, we draw some conclusions.

2.   Motivation and model
  • Real-world networks exhibit a high degree of complexity, which is manifested not only in the number of nodes and edges but also in the ways in which nodes are connected. The connections between nodes in real-world networks are often not simply linearly arranged but instead form a complex topology. Cycles, as a fundamental topological structural element abundant in real-world networks, can well reflect the complexity and redundancy of network structures. Recent research has unveiled the topological characteristics of cycles, including the distribution of cycles of different sizes in both real-world and synthetic networks.[31] Cycles play significant roles in network functions related to storage,[32] synchronizability,[33] and controllability.[34] For instance, cycles can introduce redundant paths in network connectivity and feedback effects in network dynamics. Additionally, cycles are also used as a tool to measure the proximity of networks to tree networks, thereby revealing significant differences between synthetic networks and real-world networks.[35]

    Different cycles are likely to play different roles in network structures and dynamics, among which the smallest cycles play an important role in analysis of graphs or networks. For example, the cohesion of a network is measured by the clustering coefficient, which is essentially the fraction of all possible triangles (the smallest cycle) in a graph. In graph theory, the minimum length bases of the cycle space of a graph (MCBs) of cycle spaces have broad applications in various scientific and engineering fields, such as structural flexibility analysis, power grids, and chemical structure storage and retrieval systems.[36] In social networks, the community structure, as a fundamental characteristic, reflects the high connectivity and closeness among members within a community, naturally leading to the emergence of numerous cycle structures. In public transportation networks, such as bus and subway networks, loop lines are widely available, which increases the possibility of transfer, thus significantly improving the efficiency and flexibility of the entire transportation system. As shown in Fig. 1(a), which depicts a portion of the Beijing subway network, loop lines are ubiquitous and constitute an important part of the network layout, not only enhancing internal connectivity but also greatly facilitating convenient transfers between different lines for passengers. It is generally believed that a road network is composed of many polygons. Figure 1(b) shows a visualization of the road network of Minnesota.[37] It can be seen that a large number of cycles exist in road networks. The cycle structures exhibit good reachability. When both the initial node and the final node are specified, there are two distinct and well-connected paths, indicating good reachability. Furthermore, a cycle graph is characterized as a two-connected graph, implying that the removal of at least two vertices is necessary to disconnect it. In the field of network security, cycle structures play a crucial role in enhancing the robustness of networks.

    Cycle structure is a unique characteristic of node importance that distinguishes it from other indicators. Degree centrality focuses on considering the number of connections of nodes. Betweenness and closeness centrality essentially involve path analysis, where the former calculates the number of times a node is passed by the shortest path, while the latter evaluates the centrality by the reciprocal length of the shortest path between a node and other nodes. H-index and eigenvector centrality primarily focus on the importance of the node itself and its neighbors, without directly considering the cycle structure. The local clustering coefficient only reflects the clustering property of a node by considering the number of triangles formed by three nodes, neglecting the significance of larger cycles that still exist in large numbers in the network. Coreness determines the core status of a node by analyzing the number of neighbors of a node and the number of neighbors of its neighbors, but it fails to account for the impact of cycle structures on network structure and function. Therefore, we propose a new method for identifying vital nodes by combining cycle with degree centrality. Certainly, it is also possible to combine cycles with the other indicators mentioned above, which will be discussed in Subsection 3.1, but the results show that the combination of degree and cycle ratio has a relatively good effect.

    Based on the above considerations, this paper proposes a new vital node identification method. Considering a simple network G = (V,E), where V is the set of N nodes and E is the set of edges. The size of a cycle is equal to the number of edges it contains. The cycle containing the smallest size of node i is defined as the shortest cycle associated with node i, and the corresponding size is called the girth of node i. Si represents the set of all smallest cycles associated with i. S = ∪i∈VSi is the minimum set of all cycles in the graph G. The cycle number matrix C = [cij]N × N, where cij is the number of cycles in S that pass through both i and j when i ≠ j. If i = j, cii is the number of cycles in S that contain i. Based on the number of cycles matrix C, the formula of cycle ratio is as follows:[19]

    The identification of vital nodes under different indicators in Fig. 2 is evaluated according to the attack efficiency of complex networks. As is shown in Table 1, the metric values of each node in Fig. 2 under degree, betweenness, cycle ratio, coreness, eigenvector centrality, local clustering coefficient, H-index and DC are shown. By observing the ranking of the network in Fig. 2 and the corresponding node centrality index in Table 1, it is found that node 3 is regarded as the key node when measured according to degree, betweenness centrality and eigenvector centrality. When node 3 is removed, the size of the maximal connected subgraph of network is 6. In Fig. 2(b), nodes 4, 5, 6, 7, 8, and 9 are simultaneously considered as central nodes when measured according to cycle ratio, coreness, and H-index, so the optimal vital node cannot be determined. Local clustering coefficients are not effective in identifying important nodes in such networks. Obviously, it is inefficient to use only one metric for many nodes with the same metric. Therefore, in order to improve the attack efficiency, we put forward a new index DC to measure the importance of nodes. Each node is assigned a DC value that indicates how important the node is in the network. The coefficient α is used to adjust the importance of different metrics in DC, the DC formula is as follows:

    where ki and ri indicate the degree and cycle ratio of node i, respectively, 0 ≤ α ≤ 1.

    Figure 2(c) shows the identification of vital nodes under the DC indicator when 0 < α < 6/7. The DC identifies node 4 as the key node. When node 4 is removed, the size of the maximal connected subgraph of network is 5, and the network disassembly efficiency reaches the maximum.

3.   Results and discussion
  • We used Email (email communication network from the Rovira I Virgili University in Wisconsin from the email communication network of Rovira I Virgili University in Spain),[38] Wiki (Wikipedia network),[39] Hamsterster (Social network),[40] the bus networks Chengdu-BUS, Chongqing-BUS and Beijing-BUS to study the importance of nodes. Their basic topological features are shown in Table 2. Other datasets used are in Appendixes A–C.

    Three dynamic processes, including node percolation, epidemic spreading, and targeted immunization, are used to test the rationality of DC in identifying vital nodes. The first dynamic process considers the ability of nodes to maintain network connectivity, the second focuses on the accessibility of infected nodes during epidemic outbreaks, and the third concentrates on prevention and control in the early stages of disease outbreaks. We analyze the network characteristics by dividing the degree-dominant network (Email, Wiki, Hamsterster) and the cycle-dominant network (Chongqing-BUS, Beijing-BUS, Chengdu-BUS), and verify the effectiveness of DC in identification of vital nodes. The DC index provides a new perspective and tool for vulnerability analysis of networks, protection of critical infrastructure, and prevention and control of outbreaks.

  • In order to evaluate the importance of nodes in maintaining network connectivity, this paper studies the percolation dynamics of nodes[41] and uses a static approach based on the initial state of the network to evaluate its robustness. Specifically, the nodes are ranked by their DC value in the initial network from smallest to largest, and then the nodes with the highest DC value are removed in turn. This method assumes that the network structure remains unchanged during the evaluation process, and can quickly identify nodes that have an initial impact on network connectivity. Removing nodes may change the network connectivity. The relative size of the maximal connected subgraph of a network is often used to indicate the robustness of the network to random or deliberate attack strategies. The relative size of the maximal connected subgraph of the network G can be expressed as

    where N represents the total number of nodes in the initial network, and nt represents the number of nodes in the maximal connected subgraph of network after t nodes are removed at step t, with one node removed in each step.

    Figure 3 shows the ranking of vital nodes by six real-world networks under different weights of α for the DC index. The relative size of the maximal connected subgraph g of the network changes with the proportion of removed nodes P. Obviously, it can be observed that the relative size of the maximal connected subgraph of the network varies greatly with different α, especially in Figs. 3(d)–3(f). To quantify and compare the differences between the curves in Fig. 3, we calculate the area between each curve and the horizontal and vertical axes as an indicator of the differences between curves. We use robustness to measure the efficiency of attacks under different attack strategies. For a given network G, one node is removed at each time step and the size of the maximal connected subgraph in the remaining network is calculated until the remaining network is empty. The observation R is defined as[2,19]

    which describes the area enclosed by the g vs. P curve with the x-axis and y-axis. Obviously, a smaller R means a faster breakdown of the network, resulting in a more efficient sorting of vital nodes.

    Based on the premise that the relative size of the maximal connected subgraph reaches 0.01 for the first time, this paper explores the changes of R under different coefficients α. As shown in Fig. 4, when removing nodes based on the DC attack strategy, the observation R is a function of coefficient α. Interestingly, as α increases, the observation R exhibits a nonlinear relationship with α and shows a trend of first decreasing and then increasing. This non-monotonic property reveals that there is an optimal configuration of α, which ensures that the extent of network dismantling under the ranking of vital nodes obtained according to DC index reaches the maximum. At the same time, it also proves that there are deficiencies in identifying vital nodes under a single index, and blindly enlarging the degree advantage or cycle structure advantage in the DC value of nodes by changing α cannot guarantee the best results in network dismantling.

    In order to show the effect, we take α corresponding to the lowest point of the curve in Fig. 4 as the coefficient of DC for vital node identification. Figure 5 shows the breakdown process of the real-world networks under different attack strategies, including removing nodes according to degree, betweenness, cycle ratio, H-index, coreness, closeness centrality, eigenvector centrality, local clustering coefficient and DC. Under removing nodes one by one according to different attack strategies, the relative size of the maximal connected subgraph of the network g as a function of the proportion of nodes removed P. Obviously, in most networks, DC causes the network to crash faster than other metrics. Specifically, when the node removal ratio P is small, the curves representing the relative size of the maximal connected subgraph of the nine attack strategies are constantly interleaving during the network dismantling process, which indicates that the nine attack strategies at this time have quite similar effects on network connectivity, showing equivalence. As P gradually increases, DC attack strategy gradually shows better performance than other metrics in network dismantling, and the network begins to crash faster. As can be seen from the above, in most networks, DC index shows effective performance in network disassembly and is the best index for identifying vital nodes that maintain network connectivity.

    Certainly, in addition to the aforementioned points, we also demonstrated the variation of R with respect to the weight α when integrating respectively betweenness, H-index, coreness, closeness centrality, eigenvector centrality, and local clustering coefficient metrics with the cycle ratio using the weight α. As shown in Fig. 6, it can be observed that the integration of degree centrality with the cycle ratio outperforms the integration of other metrics with the cycle ratio in terms of node percolation. Similarly, as illustrated in Fig. 7, we examined the variation of R with respect to the weight α when degree centrality was integrated with betweenness, H-index, coreness, closeness centrality, eigenvector centrality, and local clustering coefficient metrics using the weight α, respectively. Again, it is evident that the effectiveness of integrating other metrics with the cycle ratio is indeed less pronounced compared to the integration of degree centrality with the cycle ratio.

    In summary, this paper is divided into a cycle-dominant network and a degree-dominant network to discuss the influence of weight α on the dynamic process. (i) There is a nonlinear relationship between the weight α of the DC index and the observation R, and the curve shows a non-monotonic characteristic of first decreasing and then increasing or first decreasing and then flattening, which reveals that the existence of an optimal α of the DC index can cause the network to crash quickly. (ii) Email, Wiki and Hamsterster datasets are similar to cycle-dominant networks, and the optimal α is small (α < 0.5); that is to say, the DC index is inclined to identify nodes with high cycle ratio and attacks on these nodes usually destroy the cycle structure in network, so the robustness of the network is quickly weakened. (iii) Chongqing-BUS, Beijing-BUS and Chongqing-BUS are similar to degree-dominant networks, the optimal α is large (α > 0.5), and the DC index focuses on the degree of nodes. In this type of network, robustness is very sensitive to high-degree nodes (such as transportation hubs or large substations), which are often connected to multiple high-traffic sections or subnets, and congestion and power outages can quickly spread throughout the network, leading to congestion or widespread power outages.

  • In the field of epidemic spreading, identifying vital nodes in network is crucial for understanding the spreading mechanism of diseases, predicting epidemic trends, and formulating effective prevention and control strategies.[42,43] In this paper, DC is used to define the propagation centrality of nodes, which is used to rank the propagation influence of nodes. The importance of nodes can be evaluated by their role in the process of disease spreading. To quantify the impact of a selected set of nodes, we simulate the standard susceptibility–infection–recovery (SIR) propagation dynamics, where, at each time step, each susceptible node will be infected by an infected neighbor node with a probability of β, and each infected node will recover with a probability of γ. Initially, the first 0.1N nodes selected by each metric are set as infected nodes, and the other nodes are set as susceptible nodes. We consider the following infection rate β[26,27] and recovery rate γ = 1, where

    here 〈k〉 and 〈k2〉 are the average degree and average squared degree of network, respectively.

    In this paper, the cumulative number of infected populations is used to measure the spread influence of nodes. Figure 8 shows how important nodes of six real-world networks are sorted, respectively, under different weights of α for DC indicators, and how the cumulative number of infected populations It changes with the time step. Obviously, it can be observed that with different α, the cumulative number of infected groups in the network It varies greatly, especially in Figs. 8(b), 8(c), 8(e) and 8(f). To quantify and compare the differences between the curves in Fig. 8, we propose observation I to measure the performance of different metrics affected by infection, which is defined as the cumulative number of infected individuals at a steady state. The formula is as follows:

    where It is the number of infections at time t. I represents the cumulative number of infected nodes at Tmax. The larger I is, the better the infection effect is.

    Firstly, based on the premise that the number of infections and the number of recoveries in network reach a balanced state, this paper explores the change of the cumulative number of infected individuals I under stable state with different coefficients α based on the networks in Table 2. As shown in Figs. 9(a)–9(c), with the increase of α, the cumulative number of infected groups I in the network gradually decreases to a flat level. The more cumulative infections, the more important the node is. We find that the optimal value of α is generally less than 0.1, which indicates that degree plays a very weak role in the ranking of important nodes based on the DC method, and the cycle ratio predominates the ranking of important nodes to a large extent.

    As shown in Figs. 9(d)–9(f), with the increase of α, the cumulative number of infected groups I of the network shows a trend of first increasing and then decreasing. The nonlinear characteristics of the curve make DC have the optimal weight α, and when α is larger, the propagation effect is maximized, and the node degree occupies the dominant advantage in the identification of vital nodes. Take α corresponding to the highest I as the weight of the DC method. Using degree, betweenness, cycle ratio, H-index, coreness, closeness centrality, eigenvector centrality, local clustering coefficient, and DC influence indicators reflects the importance and influence of nodes in the network, so as to provide a basis for identifying vital nodes.

    Figure 10 shows the cumulative number of infected persons at different time steps t for nine indicators, which are averaged over 6000 independent runs. When the time step t gradually increases, the node propagation ability of each index gradually increases. In Figs. 10(a)–10(c), the effect of cycle ratio and DC index is the same, followed by betweenness, and the local clustering coefficient has the worst propagation effect. This indicates that in the Email, Wiki and Hamsterster datasets, the vital nodes identified by the DC index have little improvement in disease transmission, while the vital nodes identified by the cycle ratio have reached the optimal effect in SIR transmission. It is probably because these networks have an obvious community structure and a large number of small cycles, and nodes with a high cycle ratio are usually located in multiple cycles, which are easier to form transmission links with other nodes, and can quickly spread diseases or information to multiple susceptible people, thus accelerating the spread of diseases or information.

    In Figs. 10(d)–10(f), nodes have a good propagation ability under the DC index or local clustering coefficient. It may be because in Chongqing-BUS, Beijing-BUS and Chengdu-BUS, high nodes (such as a transportation hub or a large substation) are often connected to multiple high-traffic sections or subnet cores, and changes in their state (such as congestion, closure) can quickly propagate throughout the network, leading to congestion or widespread power outages. However, the nodes with a high cycle ratio are distributed in different layers or modules of the network. Because of their redundancy, they are connected to multiple cycles in the network, and their influence is relatively dispersed, and it is not easy to form a global fault effect.

    Figure 11 shows the cumulative number of infected populations in the SIR model in the first 10 time steps under different node importance influence indicators and at different transmission times. The cumulative number of the first 0.1N nodes selected by each metric in terms of β infection probability. Figure 12 reports the ranking of the nine metrics at the time steps t = 1, t = 2, t = 3, t = 4, t = 5, t = 6, t = 7, t = 8, t = 9 and t = 10, averaged over 8000 independent runs. The index with the best performance is ranked first, followed by the second, …, the worst indicator was ninth. It can be seen from the results that DC ranking is always at the top, significantly better than other indicators.

    In summary, in epidemic spreading, there is a non-monotonicity relationship between the cumulative number of infected individuals at steady state I and the weight α of the DC index, which reveals that there is an optimal weight α of DC, which makes the infection ability reach the maximum. (i) In the Email, Wiki and Hamsterster networks, the relationship curve between the cumulative number of infected individuals at steady state I and the weight α shows a trend of first decreasing and then stabilizing, and the optimal value of the weight α is generally small (α < 0.5). The results show that the propagation ability of vital nodes identified by the DC index is similar to that of the cycle ratio, and the improvement is not obvious. (ii) In the Chongqing-BUS, Beijing-BUS and Chengdu-BUS networks, the relationship curve between the cumulative number of infected individuals at steady state I and the weight α presents a trend of first rising and then declining, and the optimal value of the weight α is generally large (α > 0.5). The results show that the propagation ability of vital nodes identified by the DC index is significantly improved compared with other metrics. (iii) Therefore, it is found that for epidemic spreading, in most subways networks, the DC method can accurately identify the most influential spreaders and maximize information dissemination in a short period of time.

  • The selection of appropriate immunization strategies is extremely important for the prevention and control of infectious diseases. Targeted immunization of vital nodes through the SIS model can quickly contain infection.[28] Targeted immunization hopes to achieve the best possible immunization effect by selectively immunizing a small number of nodes. Once these nodes are immunized, it means that their connected edges can be removed from network, greatly reducing the possible connection routes for disease spreading.[29,30] This paper identifies vital nodes in network based on targeted immunization and proves that disease immunization is an effective method to measure node centrality.

    If each susceptible node is connected to one or more infected nodes, its infection rate is β. Infected nodes are cured and become susceptible nodes again with rate γ. This paper does not consider the rate of an individual being removed due to death or acquired immunization, so the individual runs randomly in the cycle of susceptibility → infection → susceptibility, which is the SIS propagation model. The simulation is implemented under a fixed spreading rate of 0.25, and the rate of an infected node recovering to a susceptible node γ = 0.5. We first infect half of nodes in network, and then update the rules of SIS model in parallel to analyze the stationary characteristics of the infected node density ρp under different immunization densities P.

    Figure 13 shows the sorting of vital nodes by six real-world networks under different weights of α for DC indicators, and the changes of ρp/ρ0 with immune density P. In Figs. 13(a)–13(c), the difference between curves is small under different α. In Figs. 13(d)–13(f), there is a big difference between the curves under different α. To quantify and compare the differences between the curves in Fig. 13, we propose observation ψ to describe the performance of metrics affected by immunization. The smaller the ψ, the better the immunization effect and the faster the elimination of disease spreading is. The formula is

    where ρ0 is the steady-state infection density without immunization, NP represents the number of equally spaced intervals taken by the horizontal coordinate, and ρi is the steady-state infection density after immunization of nodes with the proportion i ∈ P in network. It describes the area formed by the curve of ρP/ρ0 as a function of P and the x-axis and y-axis.

    Based on the premise that the steady-state infection density reaches 0, this paper explores the changes of ψ in a steady state under different weight α based on the networks in Table 2. As shown in Figs. 14(a)–14(c), with the increase of α, the observation ψ of most networks shows a trend of first decreasing and then increasing. This non-monotonicity characteristic proves that there is an optimal value of α, ensuring that the extent of immunization of the vital nodes identified by DC is maximized. As shown in Figs. 14(d)–14(f), with the increase of α, the observation ψ of the network shows a trend of decreasing first and then stabilizing. This nonlinear relationship shows that there is an optimal value for the weight α, and immunity achieves the best effect when α is larger (α > 0.5). We take the α corresponding to the bottom of the curve as the weight of DC.

    As shown in Fig. 15, under different immune indexes, steady-state infection density gradually decreased with the increase of immune density P. In Figs. 15(a)–15(c), the steady-state infection density decreased faster and the corresponding immune density threshold was smaller than other indicators based on the immunization strategy of identifying important nodes in DC. The immune effect of local clustering coefficient was the worst. These results show that the vital nodes identified by the DC indicators have a strong effect on the immune prevention and control of the cycle-dominant network, and can eliminate the spread of the virus faster than other influence indicators. In Figs. 15(d)–15(f), the immune effect of DC is the best, the speed of eliminating disease transmission is faster, and the immune density critical value is smaller. The second is degree, and the index of cycle ratio has the worst effect. This means that in the degree-dominant network, the vital nodes identified according to the cycle ratio are not effective in controlling information dissemination and solving congestion. However, only a smaller number of nodes need to be immunized to rapidly control the spread of the epidemic and ensure the maximum immunization effect under limited resources.

    In summary, the non-monotonicity relationship between the weight α of the DC index and the observation ψ reveals that there is an optimal α in DC, so that the network can minimize the speed and scope of disease spreading. (i) Generally, for Email, Wiki and Hamsterster networks, the optimal α is small (α < 0.5); that is, the weight of the cycle ratio is large, and DC is inclined to identify high cycle ratio nodes connecting different communities in high-clustering networks, which are usually located in the center of tightly connected clusters. Immunizing these nodes can significantly reduce the speed and extent of the spread of disease, rumors, etc. (ii) Generally, for Chongqing-BUS, Beijing-BUS and Chengdu-BUS, the optimal α is large (α > 0.5), that is, the DC index is focused on the node degree. Protected high-degree nodes (large interchange stations, transportation hubs, power stations or substations) can ensure the normal operation of traffic flow during peak periods or emergencies. (iii) In conclusion, for targeted immunization, the DC method shows an effective effect in cycle-dominant networks, and also proves that observation ψ is an effective indicator to measure node centrality.

  • Lancichinetti et al.[44] introduced a class of synthetic networks with a power-law distribution of both degree distribution and community size distribution, i.e., LFR benchmark, including the following parameters: the number of nodes N; the power law exponent for the degree distribution v; the power law exponent for the community size distribution δ; the mixing parameter μ; the average degree 〈k〉. The network construction steps are as follows: first, the LFR network assigns degrees to the nodes using a power-law distribution with an exponent of v, with an average degree of 〈k〉. Then, a configuration model is used to connect the nodes to maintain the degree order of the nodes. Select the community size using a power-law distribution with an exponent of δ so that the sum of all community sizes equals the number of nodes N of the graph, and ensure that nodes of any degree belong to at least one community. At the same time, the location of the nodes within the community is adjusted through the iterative process and rewiring steps, so that each node shares a part of the link 1 − μ with other nodes in its community and a part of the link μ with other nodes in the network. Such networks more closely resemble real-world networks with community structures.

    We discuss the non-monotonicity relationship between the weight α and R on the LFR networks. First setting N = 3000, v = 3, δ = 1.5, 〈k〉 = 20, and 50 LFR networks are randomly generated for testing under each μ. As shown in Fig. 16, the observation R varies with the weight α when nodes are sorted according to the DC index at μ = 0.02, 0.05, 0.1, 0.2, 0.3, 0.4. It is found that the existence of optimal α can only be observed in a certain interval of μ (0.05 < μ < 0.3).

    Next, we set N = 3000, v = 3, δ = 1.5, μ = 0.1, and 50 LFR networks are randomly generated for testing under each 〈k〉. As shown in Fig. 17, the observation R varies with the weight α when nodes are sorted according to the DC index at 〈k〉 = 10, 20, 30, 40, 50,60. With the gradual increase of 〈k〉, the non-monotonicity of the curve becomes stronger and stronger, and the optimal α gradually decreases.

4.   Conclusion
  • In this paper, combining degree (weight α) and cycle ratio (weight 1 − α), a new vital node identification method, the DC method (degree and cycle ratio), is proposed to quantify the importance of a single node. This method not only makes up for the defect of vital node identification under a single degree index, but also overcomes the limitation caused by the omission of cycle-based nodes without direct correlation. In this paper, networks are divided into cycle-dominant networks and degree-dominant networks, and three dynamic processes, node percolation, epidemic spreading, and targeted immunization, are used to test the effectiveness of the DC method.

    First, in node percolation, there is a non-monotonicity relationship between the observation R and the weight α of the DC index, which reveals that the existence of the optimal α of the DC index can cause the network to collapse quickly. In general, for cycle-dominant networks, the optimal α is small (α < 0.5), and the effect of the cycle ratio is more obvious, which occupies a dominant position in identifying vital nodes. For degree-dominant networks, the optimal α is large (α > 0.5), the degree value effect is significant, and the DC index focuses on the degree of nodes.

    Secondly, in epidemic spreading, there is a non-monotonicity relationship between the cumulative number of infected individuals at steady state I and the weight α of the DC index, which reveals that there is an optimal weight α of DC index to maximize the infection capacity. Generally, for cycle-dominant networks, the relationship curve between the cumulative number of infected individuals I and α shows a trend of first decreasing and then stabilizing, and the optimal value of α is generally small (α < 0.5). The propagation ability of vital nodes identified by the DC index is similar to the effect of cycle ratio, and the improvement is not obvious. While, for degree-dominant networks, the relationship curve between the cumulative number of infected individuals at steady state I and α shows a trend of first rising and then declining, and the optimal value of α is generally large (α > 0.5). The propagation ability of vital nodes identified by the DC index is significantly improved compared with the other eight indicators.

    Next, in targeted immunization, the non-monotonicity relationship between the weight α of DC index and the observation ψ reveals that there is an optimal α of DC so that the network can minimize the speed and range of disease spreading. Generally, for cycle-dominant networks, the optimal α is small (α < 0.5), and the cycle ratio is dominant in identifying vital nodes. The immunization effect of vital nodes identified by the DC index was significantly improved compared with the other eight indicators. However, for degree-dominant networks, the optimal α is large (α > 0.5), and the degree is dominant in identifying vital nodes. The propagation ability of vital nodes identified by the DC index is similar to the effect of cycle ratio, and the improvement is not obvious.

    Finally, this paper uses the LFR synthetic network model to explore the relationship between the weight α and observation R, and finds that the change of mixed parameters μ or 〈k〉 has a great influence on the non-monotonicity of R vs. α curve, and the optimal α is usually small.

    In conclusion, this paper uses three dynamic processes, namely, node percolation, epidemic spreading, and targeted immunization, to test the effectiveness of the DC vital node identification method, and verifies that, in most networks, DC performs better than a single metric.

Appendix A Node percolation
  • The code for the program has been uploaded to GitHub at https://github.com/kust-yangbo/Degree-and-Cycle-ratio and is also openly available in Science Data Bank at https://www.doi.org/10.57760/sciencedb.j00113.00158, which are freely available to academic users. The program was written based on the windows operating platform, which is commonly used for Python software, making it easy to use with other software. For more detail, please read the README.md file in the Degree-and-Cycle-ratio program.

Figure (23)  Table (2) Reference (46)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return