An influential node identification method considering multi-attribute decision fusion and dependency

Chaoyang Chen, Dingrong Tan, Xiangyi Meng, Jianxi GaoScientific 2022 · DOI

TL;DR

This paper introduces a novel method for identifying influential nodes in interdependent networks by considering their multi-attribute influence, including their neighbors, and a more realistic nonlinear load-capacity model for cascading failures. This approach leads to a more accurate assessment of network robustness and provides better insights for managing complex infrastructure systems.

What Problem Does This Paper Address?

Modern infrastructure systems, such as power grids, communication networks, and transportation systems, are increasingly interconnected and interdependent. This interdependence creates vulnerabilities, where failures in one system can cascade and trigger failures in others, leading to widespread disruptions. Traditional models often simplify these interactions, assuming random initial failures and linear relationships between node load and capacity. However, real-world systems exhibit more complex dynamics: initial failures are often targeted at influential nodes, and the load-capacity relationship is nonlinear, with lower-capacity nodes sometimes having higher idle capacity. This paper addresses the gap in accurately modeling and identifying critical nodes within these complex, interdependent systems by proposing a more realistic approach to cascading failure and node influence assessment.

Methods

The core of this paper lies in two main methodological advancements:

  1. Nonlinear Load-Capacity Cascading Failure Model: Instead of the traditional linear model, the authors propose a nonlinear relationship between a node's capacity and its initial load. This is crucial because real-world networks often show that nodes with lower capacity might have more idle capacity, which is not captured by linear models. The initial load of a node is also not assumed to be random but is determined by its influence and the influence of its neighbors.
  2. Multi-Attribute Fusion Centrality (MAFC) Algorithm: To identify influential nodes, the paper introduces a novel MAFC algorithm. This algorithm goes beyond single centrality measures (like degree or betweenness) by:
  3. Multi-Attribute Decision Making: It combines multiple centrality indicators (degree, betweenness, eigenvector, closeness, and K-shell) to provide a more comprehensive evaluation of a node's importance.
  4. Entropy Weight Method: To avoid subjective weighting of different centrality measures, it uses an entropy weight method to objectively determine the importance of each attribute based on its information content.
  5. Considering Neighbors: Crucially, the influence of a node is not just based on its own attributes but also incorporates the influence of its nearest and next-nearest neighbors. This captures the broader impact a node might have within its local network context.
  6. Interdependence Mapping: For interdependent networks, the algorithm constructs a linear mapping function to represent how the influence of nodes in one network affects nodes in another, considering the coupling relationship between them.

Datasets

The study evaluates its proposed methods using several network topologies:

  • Erdos-Renyi (ER) networks: These represent random graph models.
  • Barabasi-Albert (BA) networks: These represent scale-free networks, which are more characteristic of real-world infrastructure.
  • IEEE 118 power grid: A real-world power system network is used as a case study to validate the findings.

The paper does not introduce new datasets but uses these established network models and a real-world benchmark to test the proposed algorithms.

Key Insights and Ideas

  • Nonlinearity Matters: The nonlinear load-capacity model significantly impacts cascading failure dynamics, offering a more realistic representation of how failures propagate and how networks respond to stress.
  • Beyond Individual Nodes: Node influence is not solely an intrinsic property but is heavily influenced by its neighbors. MAFC's consideration of nearest and next-nearest neighbors is a key improvement for understanding real-world network dynamics.
  • Objective Weighting is Crucial: Using entropy to weight centrality measures provides a more objective and robust way to combine different indicators of node importance, avoiding arbitrary human bias.
  • Assortative Coupling Enhances Robustness: Connecting nodes with similar high-influence characteristics (assortative linking) between interdependent networks leads to significantly higher robustness compared to random or disassortative linking.
  • Coupling Strength is a Double-Edged Sword: While interdependence is necessary, stronger coupling between networks can paradoxically decrease robustness by facilitating faster failure propagation.

Key Results

  • The proposed nonlinear model demonstrates better connectivity and robustness compared to traditional linear models, especially as the proportion of initial failed nodes increases.
  • The MAFC algorithm consistently outperforms classical centrality methods in identifying influential nodes across different network types (ER, BA, and IEEE 118). It leads to faster network decay when influential nodes are targeted, indicating its accuracy in pinpointing critical points.
  • Robustness analysis shows that assortative link coupling generally yields the highest robustness, followed by random link, and then disassortative link.
  • Increasing coupling strength between networks generally decreases robustness, highlighting the need for careful management of interdependencies.
  • The study shows that network parameters (like α, β, η, θ in their model) can be tuned to improve robustness, often with diminishing returns after a certain threshold, suggesting a trade-off between cost and resilience.

Limitations and Future Work

  • Computational Complexity: While MAFC is more accurate, it involves calculating multiple centrality measures and entropy weights, which can be computationally intensive for very large networks.
  • Generalizability: While tested on various network types, further validation on a wider range of real-world complex systems would be beneficial.
  • Dynamic Environments: The current model primarily focuses on static network structures and initial failure scenarios. Future work could explore how these methods perform in dynamic environments with evolving network topologies and continuous load changes.
  • Specific Failure Mechanisms: The paper focuses on load-capacity failures. Extending the model to incorporate other failure mechanisms (e.g., targeted attacks, hardware malfunctions) could provide a more holistic view of network resilience.

Summary updated

Abstract

It is essential to study the robustness and centrality of interdependent networks for building reliable interdependent systems. Here, we consider a nonlinear load-capacity cascading failure model on interdependent networks, where the initial load distribution is not random, as usually assumed, but determined by the influence of each node in the interdependent network. The node influence is measured by an automated entropy-weighted multi-attribute algorithm that takes into account both different centrality measures of nodes and the interdependence of node pairs, then averaging for not only the node itself but also its nearest neighbors and next-nearest neighbors. The resilience of interdependent networks under such a more practical and accurate setting is thoroughly investigated for various network parameters, as well as how nodes from different layers are coupled and the corresponding coupling strength. The results thereby can help better monitoring interdependent systems.
BibTeX
@inproceedings{chen2022influential,
  author = {Chaoyang Chen and Dingrong Tan and Xiangyi Meng and Jianxi Gao},
  title = {{An influential node identification method considering multi-attribute decision fusion and dependency}},
  booktitle = {Scientific},
  year = {2022},
  doi = {10.1038/s41598-022-23430-3},
}
Figure