Percolation centrality via Rademacher Complexity

DOI10.1016/J.DAM.2021.07.023MaRDI QIDQ2091801zbMATH OpenOpenAlexFDO

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

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 algorithmpercolation centralitypseudo-dimensionRademacher averages

Mathematics Subject Classification ID

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

Recommendations

• Fast Approximation of Centrality
• Fast approximation of centrality
• Approximating Betweenness Centrality
• Fast approximation of betweenness centrality through sampling
• Sublinear Algorithms for Local Graph-Centrality Estimation

Cites work

• A faster algorithm for betweenness centrality*
• An improved analysis of the Rademacher data-dependent bound using its self bounding property
• Emergence of Scaling in Random Networks
• Fast approximation of betweenness centrality through sampling
• Faster all-pairs shortest paths via circuit complexity
• Foundations of machine learning
• scientific article; zbMATH DE number 3148802 (Why is no real title available?)
• scientific article; zbMATH DE number 871954 (Why is no real title available?)
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Relative (p, )-approximations in geometry
• Shape Fitting on Point Sets with Probability Distributions
• Theory of Classification: a Survey of Some Recent Advances
• Understanding machine learning. From theory to algorithms

Cited in

(2)

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

Describes a project that uses

Uses Software

• SNAP
• NLopt
• GitHub

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2091801)