Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)

DOI10.1007/s00453-019-00665-7zbMath1441.68172arXiv1808.05676OpenAlexW3002369578WikidataQ126294395 ScholiaQ126294395MaRDI QIDQ2182087

Farzane Yahyanejad, Mano Vikash Janardhanan, Bhaskar Das Gupta

Publication date: 21 May 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1808.05676

zbMATH Keywords

approximation algorithmsinapproximabilityexact algorithmsanomaly detectiongeometric curvatureGromov-hyperbolic curvature

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (2)

On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions ⋮ A review of two network curvature measures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the hardness of approximating minimum vertex cover
• Inferring (biological) signal transduction networks via transitive reductions of directed graphs
• Expanders are not hyperbolic
• Bochner's method for cell complexes and combinatorial Ricci curvature
• Which problems have strongly exponential complexity?
• Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications
• On the complexity of Newman's community finding approach for biological and social networks
• Scaled Gromov four-point condition for network graph curvature computation
• Forman-Ricci flow for change detection in large dynamic data sets
• Computing the Gromov hyperbolicity of a discrete metric space
• Complexity of approximating bounded variants of optimization problems
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Reverse-engineering of polynomial dynamical systems
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Euclidean versus Hyperbolic Congestion in Idealized versus Experimental Networks
• Statistical mechanics of complex networks
• On Khot’s unique games conjecture
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• On the power of unique 2-prover 1-round games
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Packing and Covering δ-Hyperbolic Spaces by Balls
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Sequential change‐point detection based on direct density‐ratio estimation
• Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs
• Node-and edge-deletion NP-complete problems
• Approximation Algorithms for the Gromov Hyperbolicity of Discrete Metric Spaces
• Multiplying matrices faster than coppersmith-winograd
• Scaled Gromov hyperbolic graphs
• Parameterized Algorithms
• Algorithms and Computation
• Networks
• On the complexity of \(k\)-SAT

This page was built for publication: Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)