A bag-of-paths node criticality measure

NEUROCOMPUTING

卷:275

Article

Lebichot, Bertrand¹  Saerens, Marco¹ 

[1] Catholic Univ Louvain, Machine Learning Grp ICTEAM & LSM, Pl Doyens 1, B-1348 Louvain La Neuve, Belgium

关键词: Criticality measure;    Network vulnerability;    Vital nodes;    Graph mining;    Network science;    Network data analysis;    Betweenness centrality;   

DOI  :  10.1016/j.neucom.2017.06.054

来源: Elsevier

【 摘 要 】

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 tested measures on a sample of Erdos-Renyi and Albert-Barabasi graphs. Furthermore, a faster (but 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. (C) 2017 Elsevier B.V. All rights reserved.

【 授权许可】

Free