A bag-of-paths node criticality measure

This work compares several node (and network) criticality measures quantifying to which extend each node is critical with respect to the communication flow between nodes of the network, and introduces a new measure based on the Bag-of-Paths (BoP) framework. Network disconnection simulation experiments show that the new BoP measure outperforms all the other measures on a sample of Erdos-Renyi and Albert-Barabasi graphs. Furthermore, a faster (still O(n^3)), approximate, BoP criticality relying on the Sherman-Morrison rank-one update of a matrix is introduced for tackling larger networks. This approximate measure shows similar performances as the original, exact, one.

• Publication year

  2017

• Venue

  Neurocomputing

• Publication date

  2017-05-24

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1016/j.neucom.2017.06.054arXiv 1705.08720
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Spectral graph theory

  2019cited by this paper
• Graph Theory

  2016cited by this paper
• Algorithms and Models for Network Data and Link Analysis

  2016cited by this paper
• Vital nodes identification in complex networks

  2016cited by this paper
• Two betweenness centrality measures based on Randomized Shortest Paths

  2015influential reference
• Hitting and commute times in large random neighborhood graphs

  2014cited by this paper
• Random walks based modularity: application to semi-supervised learning

  2014cited by this paper
• A bag-of-paths framework for network data analysis

  2013influential reference
• Resistance distance, closeness, and betweenness

  2013cited by this paper
• Semisupervised Classification Through the Bag-of-Paths Group Betweenness

  2012cited by this paper
• Network Analysis: Methodological Foundations

  2012cited by this paper
• Distributed location of the critical nodes to network robustness based on spectral analysis

  2011cited by this paper
• Matrix Computations

  2011cited by this paper
• On the Vulnerability of Large Graphs

  2010cited by this paper
• The Sum-over-Paths Covariance Kernel: A Novel Covariance Measure between Nodes of a Directed Graph

  2010cited by this paper
• Getting lost in space: large sample analysis of the commute distance

  2010cited by this paper
• Betweenness centrality and resistance distance in communication networks

  2010cited by this paper
• Networks: An Introduction

  2010cited by this paper
• Centrality measure in graphs

  2010influential reference
• Application of modal analysis in assessing attack vulnerability of complex networks

  2010influential reference
• Communicability betweenness in complex networks

  2009cited by this paper
• The Kemeny constant of a Markov chain

  2009cited by this paper
• Robustness of heterogeneous complex networks

  2009influential reference
• Statistical Analysis of Network Data

  2009cited by this paper
• Randomized Shortest-Path Problems: Two Related Models

  2009cited by this paper
• A matrix handbook for statisticians

  2007cited by this paper
• Random graphs

  2006cited by this paper
• Network robustness to targeted attacks. The interplay of expansibility and degree distribution

  2006influential reference
• Statistical Comparisons of Classifiers over Multiple Data Sets

  2006cited by this paper
• Centrality Measures Based on Current Flow

  2005cited by this paper
• A measure of betweenness centrality based on random walks

  2003cited by this paper
• Attack vulnerability of complex networks.

  2002influential reference
• A faster algorithm for betweenness centrality

  2001cited by this paper
• Matrix Analysis and Applied Linear Algebra

  2000cited by this paper
• Error and attack tolerance of complex networks

  2000influential reference
• Emergence of Scaling in Random Networks

  1999cited by this paper
• Mathematics and politics : strategy, voting, power and proof

  1997cited by this paper
• Statistique exploratoire multidimensionnelle

  1995cited by this paper
• Social Network Analysis: Methods and Applications

  1994cited by this paper
• Resistance distance

  1993cited by this paper
• Entropy optimization principles with applications

  1992cited by this paper
• Random Walks and Electric Networks: REFERENCES

  1987cited by this paper
• Network structure and minimum degree

  1983cited by this paper
• A set of measures of centrality based upon betweenness

  1977cited by this paper
• Pattern recognition

  1974cited by this paper
• Markov Chains

  1972cited by this paper
• Denumerable Markov chains

  1969cited by this paper
• Hierarchical Grouping to Optimize an Objective Function

  1963cited by this paper
• Information Theory and Statistical Mechanics

  1957cited by this paper

• Extremal Hexagonal Chains with Respect to the Kemeny's Constant

  2026cites this paper
• Detecting Signatures of Criticality Using Divergence Rate

  2025cites this paper
• Fast Computation of Kemeny's Constant for Directed Graphs

  2024cites this paper
• EEG Pattern Classification of Picking and Coordination Using Anonymous Random Walks

  2022cites this paper
• Hitting Times of Random Walks on Edge Corona Product Graphs

  2022cites this paper
• Power-Law Graphs Have Minimal Scaling of Kemeny Constant for Random Walks

  2020cites this paper
• Sparse randomized shortest paths routing with Tsallis divergence regularization

  2020cites this paper
• Covariance and correlation measures on a graph in a generalized bag-of-paths formalism

  2019cites this paper
• Covariance and Correlation Kernels on a Graph in the Generalized Bag-of-Paths Formalism

  2019cites this paper
• Randomized optimal transport on a graph: framework and new distance measures

  2018cites this paper
• A bag-of-paths framework for network data analysis

  2013cites this paper