Paper · Oct 28, 2020

Geometric Sampling of Networks

Vladislav Barkanass, Jürgen Jost, Emil Saucan

math.DGarXiv:2010.15221v2
View PDF View HTML arXiv page

As on arXiv

Abstract

Motivated by the methods and results of manifold sampling based on Ricci curvature, we propose a similar approach for networks. To this end we make appeal to three types of discrete curvature, namely the graph Forman-, full Forman- and Haantjes-Ricci curvatures for edge-based and node-based sampling. We present the results of experiments on real life networks, as well as for square grids arising in Image Processing. Moreover, we consider fitting Ricci flows and we employ them for the detection of networks' backbone. We also develop embedding kernels related to the Forman-Ricci curvatures and employ them for the detection of the coarse structure of networks, as well as for network visualization with applications to SVM. The relation between the Ricci curvature of the original manifold and that of a Ricci curvature driven discretization is also studied.

View PDF View HTML arXiv page
Submitted
Oct 28, 2020
Last revised
Mar 3, 2021 (v2)
Subjects
math.DG, cs.CG, cs.SI, math.MG

Comments: 50 pages, 16 figures Corrections made, experiments and further material added

Ricci flowDiscrete & graph RicciNumerics & visualization

Its neighbourhood

Connected papers

The 8 papers on this site closest to this one, judged by the topics they share, the words and phrases in their titles and abstracts, and their authors. They are not its citations, but a map of the work around it. Papers here go back to 2016, plus the canon.

Connected papers This paper in the centre and the 8 papers closest to it around it, in date order clockwise from the top. The closer a paper sits to the centre, the stronger the connection. This paper Piecewise Flat Curvature and Ricci Flow in Three Dimensions (Rory Conboye and Warner A. Miller, 2016)7Conboye 2016 A Realization of Thurstons Geometrization: Discrete Ricci Flow with Surgery (Paul M. Alsing, Warner A. Miller and Shing-Tung Yau, 2017)5Alsing 2017 A physics-informed search for metric solutions to Ricci flow, their embeddings, and visualisation (Aarjav Jain, Challenger Mishra and Pietro Liò, 2022)3Jain 2022 Metric Flows with Neural Networks (James Halverson and Fabian Ruehle, 2023)6Halverson 2023 Exploring Stochastic Mean Curvature Flow on Networks Using Ito Calculus (Roman Bahadursingh, 2024)8Bahadursingh 2024 Core detection via Ricci curvature flows on weighted graphs (Juan Zhao, Jicheng Ma, Yunyan Yang et al., 2025)4Zhao 2025 Ricci Flow on Weighted Digraphs with Balancing Factor (Shuliang Bai, Rui Li, Shuang Liu et al., 2025)1Bai 2025 The weighted Forman and Lin-Lu-Yau Ricci flow on graphs (Shuliang Bai, Shuang Liu and Xin Lai, 2026)2Bai 2026
Closer to the centre: more closely connected. Clockwise from the top: oldest to newest. Ricci flowWider flowsalso connected to each other
  1. Ricci Flow on Weighted Digraphs with Balancing Factor

    Shuliang Bai, Rui Li, Shuang Liu et al.

    Topics Numerics & visualization, Discrete & graph Ricci · Shared terms “detection”

  2. The weighted Forman and Lin-Lu-Yau Ricci flow on graphs

    Shuliang Bai, Shuang Liu and Xin Lai

    Topics Discrete & graph Ricci · Shared terms “Forman”

  3. A physics-informed search for metric solutions to Ricci flow, their embeddings, and visualisation

    Aarjav Jain, Challenger Mishra and Pietro Liò

    Topics Numerics & visualization, Discrete & graph Ricci · Shared terms “embedding”

  4. Core detection via Ricci curvature flows on weighted graphs

    Juan Zhao, Jicheng Ma, Yunyan Yang et al.

    Topics Discrete & graph Ricci · Shared terms “detection”

  5. A Realization of Thurstons Geometrization: Discrete Ricci Flow with Surgery

    Paul M. Alsing, Warner A. Miller and Shing-Tung Yau

    Topics Numerics & visualization, Discrete & graph Ricci · Shared terms “Forman”

  6. Metric Flows with Neural Networks

    James Halverson and Fabian Ruehle

    Topics Numerics & visualization, Discrete & graph Ricci · Shared terms “Motivated”

  7. Piecewise Flat Curvature and Ricci Flow in Three Dimensions

    Rory Conboye and Warner A. Miller

    Topics Discrete & graph Ricci · Shared terms “sampling”

  8. Exploring Stochastic Mean Curvature Flow on Networks Using Ito Calculus

    Roman BahadursinghWider flows

    Topics Numerics & visualization

Read around it

Background reading

The guides for the topics of this paper: what each idea is, why it matters, and the papers to read first.

Ricci flow Hamilton's Ricci flow evolves a Riemannian metric by minus twice its Ricci curvature. It is a nonlinear heat equation for geometry: it spreads… Start with: Three-manifolds with positive Ricci curvature (Hamilton, 1982) Discrete & graph Ricci Curvature and Ricci flow for graphs, networks and triangulated surfaces. It runs from Chow–Luo's combinatorial flow on circle packings to Ollivier's… Start with: Combinatorial Ricci Flows on Surfaces (Chow et al., 2002) Numerics & visualization Computing and visualising Ricci flow: simulations of neckpinches and critical behaviour, pictures of rotationally symmetric flows, and… Start with: Deforming metrics in the direction of their Ricci tensors (DeTurck, 1983)

In the guidebook

  1. 6D.11
    Computing Geometric FlowsBook 6D · Diffusions, Finance and Computation

    Numerical curve shortening and mean curvature flow, level sets and phase fields, discrete Ricci flow on surfaces and in conformal mapping, rotationally symmetric neckpinches, and what computation has taught about singularities.

  2. 5A.5
    Uniformization and the Two-Dimensional Ricci FlowBook 5A · Complex Analysis and Conformal Geometry

    Constant-curvature metrics on surfaces, and Ricci flow as a heat equation for the conformal factor.

  3. 10A.12
    Curve Shortening and Minimal DiscsBook 10A · Three-Manifolds and Geometrization

    How loops shrink under curvature, how the discs they bound lose area, and Perelman's extinction estimate.