Percolation centrality: quantifying graph-theoretic impact of nodes during percolation in networks

Area of Science:

• Network Science
• Complex Systems Analysis
• Computational Social Science

Background:

• Traditional centrality measures (e.g., betweenness centrality) are insufficient for dynamic network percolation scenarios.
• Existing measures fail to account for the evolving percolation states of individual nodes during processes like disease or information spread.
• Accurate node importance assessment is critical for understanding and mitigating cascading failures or transmissions in complex networks.

Purpose of the Study:

• To propose a novel centrality measure, percolation centrality, designed for network percolation scenarios.
• To quantify the relative impact of nodes by integrating topological connectivity with their dynamic percolation states.
• To demonstrate the applicability and computational efficiency of the proposed measure.

Main Methods:

• Development of the percolation centrality metric, incorporating both static topological features and dynamic node states.
• Extension of the measure to include random walk-based definitions for enhanced analysis.
• Comparative analysis of computational complexity against established measures like betweenness centrality.

Main Results:

• Percolation centrality effectively quantifies node importance in dynamic network percolation contexts.
• The computational complexity of percolation centrality is comparable to that of betweenness centrality.
• Successful application demonstrated on canonical, simulated, and real-world scale-free and random networks.

Conclusions:

• Percolation centrality offers a more accurate assessment of node influence in dynamic network processes.
• The new measure provides valuable insights for network analysis in fields such as epidemiology and cybersecurity.
• Further research can explore advanced extensions and applications of percolation centrality.