Percolation centrality via Rademacher Complexity

DOI10.1016/j.dam.2021.07.023zbMath1502.05088OpenAlexW3187759259MaRDI QIDQ2091801

André L. Vignatti, Murilo V. G. da Silva, Alane M. de Lima

Publication date: 2 November 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2021.07.023

zbMATH Keywords

approximation algorithmpseudo-dimensionRademacher averagespercolation centrality

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items (2)

A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs ⋮ Estimating the clustering coefficient using sample complexity analysis

Uses Software

• SNAP
• NLopt
• GitHub

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved analysis of the Rademacher data-dependent bound using its self bounding property
• Relative \((p,\varepsilon )\)-approximations in geometry
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• Fast approximation of betweenness centrality through sampling
• A faster algorithm for betweenness centrality*
• Emergence of Scaling in Random Networks
• Theory of Classification: a Survey of Some Recent Advances
• Shape Fitting on Point Sets with Probability Distributions
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Faster all-pairs shortest paths via circuit complexity
• Understanding Machine Learning

This page was built for publication: Percolation centrality via Rademacher Complexity