Forman-Ricci flow for change detection in large dynamic data sets

DOI10.3390/AXIOMS5040026MaRDI QIDQ2275110zbMATH OpenOpenAlexFDO

Authors Melanie Weber, Emil Saucan, Jürgen Jost

Publication date 2 October 2019

Published in Axioms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

change detectioncomplex systemsdynamic networksforman curvaturepeer-to-peer networkRicci flow

Mathematics Subject Classification ID

Direct methods ((G)-spaces of Busemann, etc.) (53C70)

Abstract: We present a viable solution to the challenging question of change detection in complex networks inferred from large dynamic data sets. Building on Forman's discretization of the classical notion of Ricci curvature, we introduce a novel geometric method to characterize different types of real-world networks with an emphasis on peer-to-peer networks. Furthermore we adapt the classical Ricci flow that already proved to be a powerful tool in image processing and graphics, to the case of undirected and weighted networks. The application of the proposed method on peer-to-peer networks yields insights into topological properties and the structure of their underlying data.

Review text

Summary: We present a viable geometric solution for the detection of dynamic effects in complex networks. Building on Forman's discretization of the classical notion of Ricci curvature, we introduce a novel geometric method to characterize different types of real-world networks with an emphasis on peer-to-peer networks. We study the classical Ricci-flow in a network-theoretic setting and introduce an analytic tool for characterizing dynamic effects. The formalism suggests a computational method for change detection and the identification of fast evolving network regions and yields insights into topological properties and the structure of the underlying data.

Recommendations

• Robust change detection for large-scale data streams
• Ricci flow embedding for rectifying non-Euclidean dissimilarity data
• High-dimensional changepoint detection via a geometrically inspired mapping
• The detection of local shape changes via the geometry of Hotelling's \(T^2\) fields
• Streaming changepoint detection for transition matrices
• A Unified Data-Adaptive Framework for High Dimensional Change Point Detection
• High-Dimensional, Multiscale Online Changepoint Detection
• Detecting change-points in multidimensional stochastic processes
• Nonparametric change detection and estimation in large-scale sensor networks

Cites work

• A metric Ricci flow for surfaces and its applications
• A survey of Ricci curvature for metric spaces and Markov chains
• A visual introduction to Riemannian curvatures and some discrete generalizations
• Bochner's method for cell complexes and combinatorial Ricci curvature
• Collective dynamics of `small-world' networks
• Combinatorial Ricci flows on surfaces.
• Discrete Laplace-Beltrami operators and their convergence
• Emergence of Scaling in Random Networks
• Forman curvature for complex networks
• scientific article; zbMATH DE number 4084495 (Why is no real title available?)
• Morse theory for filtrations and efficient computation of persistent homology
• Network science. With Márton Pósfai
• Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs
• Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
• Ricci curvature of Markov chains on metric spaces
• Ricci flow with surgery on three-manifolds
• Riemannian geometry and geometric analysis
• Spectral plot properties: towards a qualitative classification of networks
• Statistical mechanics of complex networks
• The entropy formula for the Ricci flow and its geometric applications

Cited in

(11)

• Network geometry and complexity
• A review of two network curvature measures
• Diffusion in multi-dimensional solids using Forman's combinatorial differential forms
• Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
• The geometric meaning of curvature: local and nonlocal aspects of Ricci curvature
• Curved Markov Chain Monte Carlo for Network Learning
• Forman-Ricci curvature for hypergraphs
• Feature representation learning based on graph curvature-revised deep graph learning
• Core detection via Ricci curvature flows on weighted graphs
• Continuum limits of Ollivier's Ricci curvature on data clouds: pointwise consistency and global lower bounds
• Graphs on surfaces with positive Forman curvature or corner curvature

Describes a project that uses

Uses Software

• KONECT

This page was built for publication: Forman-Ricci flow for change detection in large dynamic data sets

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