pith. sign in

arxiv: 2504.06493 · v2 · submitted 2025-04-08 · 🧮 math.PR

Co-evolving vertex and edge dynamics in dense graphs

Siva Athreya , Frank den Hollander , Adrian R\"ollin This is my paper

Pith reviewed 2026-05-22 20:23 UTC · model grok-4.3

classification 🧮 math.PR
keywords dense graphsgraphonsFisher-Wright diffusionstochastic flowsMarkov processesvertex dynamicsedge dynamicsgraph limits
0
0 comments X

The pith

In the limit of large dense graphs, a process with color-switching vertices and color-dependent edges converges to a Markov process on colored graphons.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves convergence of a finite-graph process to a continuum limit as the number of vertices goes to infinity. Vertices switch colors at rates depending on connections to the opposite color, and edges flip based on endpoint color agreement. The limit lives on colored graphons, with vertex color densities following Fisher-Wright diffusions driven by edge densities, and edge structures evolving via stochastic flows with color-dependent drifts. This matters because it allows macroscopic analysis of co-evolving network structures that would be intractable at the individual level.

Core claim

We prove that, in the limit as the graph size tends to infinity and the graph becomes dense, the graph process converges, in a suitable path topology, to a limiting Markov process that lives on a certain subset of the space of coloured graphons. In the limit, the density of each vertex colour evolves according to a Fisher-Wright diffusion driven by the density of the edges, while the underlying edge connectivity structure evolves according to a stochastic flow whose drift depends on the densities of the two vertex colours.

What carries the argument

The convergence in path topology to a Markov process on a subset of colored graphons, where dynamics separate into Fisher-Wright diffusions for color densities and stochastic flows for edges.

If this is right

  • The densities of the two vertex colors follow coupled Fisher-Wright diffusions modulated by the current edge density.
  • The edge connectivity structure evolves as a stochastic flow whose drift is determined by the pair of vertex color densities.
  • The limiting process is Markovian and lives on a restricted subset of the space of colored graphons.
  • Convergence holds for the full graph process including both vertex and edge updates.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The framework might generalize to multiple colors or weighted edges, producing higher-dimensional diffusions and flows.
  • Simulations of large finite graphs could be compared to trajectories of the limiting diffusion and flow to validate the approximation.
  • Such limits could inform models of opinion dynamics in social networks where connections and beliefs co-evolve.
  • Analysis of stationary distributions or long-term behavior in the limiting process would describe equilibrium color-edge configurations.

Load-bearing premise

The rates in the model are scaled appropriately with the graph size so that a dense limit exists and the process can be described on the space of colored graphons.

What would settle it

If large but finite graphs show color density trajectories that systematically deviate from the paths of the Fisher-Wright diffusion with the observed edge density, or if the edge structures fail to match the predicted stochastic flow.

Figures

Figures reproduced from arXiv: 2504.06493 by Adrian R\"ollin, Frank den Hollander, Siva Athreya.

Figure 1
Figure 1. Figure 1: These plots visualise a simulation for n = 1000 with η = 1.0, ρ = 1.1, sc,0 = 1.5, sd,0 = 0.7, sc,1 = 0.5, and sd,1 = 2.0. Since the diffusion coefficient does not decrease to zero, the process eventually gets absorbed in a state of consensus. Simulation [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: These plots visualise a simulation for n = 1000 with η = 1.0, ρ = 2.0, sc,0 = sd,0 = 0.0 and sc,1 = sd,1 = 1.0. The left plot shows the colour densities for each respective colour. The right plot shows the overall edge density as well as the fraction of concordant and discordant edges. The rapid homogenisation is clearly visible close to time 0. Since the diffusion coefficient decreases to zero, the proces… view at source ↗
read the original abstract

We consider a random graph in which vertices can have one of two possible colours. Each vertex switches its colour at a rate that is proportional to the number of vertices of the other colour to which it is connected by an edge. Each edge turns on or off according to a rate that depends on whether the vertices at its two endpoints have the same colour or not. We prove that, in the limit as the graph size tends to infinity and the graph becomes dense, the graph process converges, in a suitable path topology, to a limiting Markov process that lives on a certain subset of the space of coloured graphons. In the limit, the density of each vertex colour evolves according to a Fisher-Wright diffusion driven by the density of the edges, while the underlying edge connectivity structure evolves according to a stochastic flow whose drift depends on the densities of the two vertex colours.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper considers a Markovian random graph process on n vertices with two colors, where each vertex flips color at a rate proportional to its number of opposite-color neighbors, and each edge flips on/off at a rate depending on whether its endpoints have matching colors. The central claim is that, under suitable scaling of the rates with n, as n→∞ the rescaled process converges in an appropriate path topology to a Markov process on a subset of the space of colored graphons; in the limit the color densities evolve as a Fisher-Wright diffusion whose coefficients are functionals of the edge density, while the edge structure evolves according to a stochastic flow whose drift depends on the two color densities.

Significance. If the convergence theorem holds, the work supplies a rigorous dense-graphon limit for a feedback-driven vertex-edge process, explicitly linking the limit to the Fisher-Wright diffusion from population genetics and to stochastic flows on graphons. This is a non-trivial technical contribution that could serve as a template for other co-evolving network models; the explicit form of the limit generator is a clear strength that permits further analytic study.

major comments (2)
  1. [Model definition and main theorem statement] The rate scaling with n (vertex flip rate proportional to opposite-color degree, edge rates depending on color agreement) is load-bearing for the claimed non-degenerate limit. The manuscript must state the precise factors (e.g., division by n or n-1) in the model definition and verify that they produce the exact drift and diffusion coefficients of the Fisher-Wright process rather than a frozen or trivial limit; without this explicit scaling the convergence statement in the abstract cannot be checked.
  2. [Main convergence theorem] The choice of path topology on the space of colored graphons is invoked to obtain both tightness and the Markov property of the limit. The manuscript must specify the topology (e.g., cut metric, weak topology on measures, or Skorokhod-type) in the statement of the convergence theorem and show that it is strong enough to preserve the Markov property yet weak enough for the tightness argument; this choice directly determines whether the limit process remains on the claimed subset of colored graphons.
minor comments (2)
  1. [Introduction / Preliminaries] Notation for the colored graphon space and the subset on which the limit lives should be introduced with a short definition or reference to standard graphon literature before the main theorem.
  2. [Abstract] The abstract claims the edge structure evolves via a 'stochastic flow'; a brief sentence clarifying whether this is a deterministic flow driven by a random drift or a fully stochastic flow would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive overall assessment and for the detailed comments on scaling and topology. We address both major comments point by point below and have revised the manuscript to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [Model definition and main theorem statement] The rate scaling with n (vertex flip rate proportional to opposite-color degree, edge rates depending on color agreement) is load-bearing for the claimed non-degenerate limit. The manuscript must state the precise factors (e.g., division by n or n-1) in the model definition and verify that they produce the exact drift and diffusion coefficients of the Fisher-Wright process rather than a frozen or trivial limit; without this explicit scaling the convergence statement in the abstract cannot be checked.

    Authors: We agree that explicit scaling is essential for verifying the limit. In the model definition (Section 2), the vertex color-flip rate is exactly (opposite-color degree)/(n-1) and the edge flip rates are scaled by a constant factor independent of n chosen so that the expected number of edge updates per unit time remains order n^2. We have added a new Remark 2.4 that directly computes the infinitesimal generator applied to the color-density and edge-density functionals and confirms that the resulting drift and diffusion coefficients are precisely those of the Fisher-Wright diffusion with edge-density-dependent coefficients, as claimed in the abstract and Theorem 1.1. The abstract has been updated to read “with vertex rates scaled by 1/(n-1)”. These additions make the scaling fully checkable and rule out degenerate limits. revision: yes

  2. Referee: [Main convergence theorem] The choice of path topology on the space of colored graphons is invoked to obtain both tightness and the Markov property of the limit. The manuscript must specify the topology (e.g., cut metric, weak topology on measures, or Skorokhod-type) in the statement of the convergence theorem and show that it is strong enough to preserve the Markov property yet weak enough for the tightness argument; this choice directly determines whether the limit process remains on the claimed subset of colored graphons.

    Authors: We accept that the topology must be named explicitly. Theorem 1.1 now states convergence in the Skorokhod topology on D([0,∞), 𝒲), where 𝒲 is the space of colored graphons metrized by the cut distance. Section 4.2 has been expanded to verify that this topology is weak enough for the Aldous-Rebolledo tightness criterion (via uniform integrability of the quadratic variations) yet strong enough that the generator of the limit process is continuous, allowing the martingale-problem characterization to yield the Markov property. A new Lemma 4.5 shows that the limit measure is supported on the claimed subset of colored graphons. These changes directly address the referee’s concern about the interplay between topology, tightness, and the Markov property. revision: yes

Circularity Check

0 steps flagged

No circularity; standard limit theorem from explicit rates

full rationale

The paper states a convergence theorem: finite-n vertex/edge flip rates (proportional to opposite-color neighbors or color agreement) are scaled by 1/n factors so that, as n→∞ with the graph dense, the rescaled process converges in a path topology to a Markov process on a subset of colored graphons whose marginals satisfy a Fisher-Wright diffusion and a color-dependent stochastic flow. This is a first-principles derivation from the microscopic rates via standard graphon tightness and generator characterization arguments; the scaling is an explicit modeling choice to obtain a non-degenerate limit, not a fitted parameter renamed as a prediction, and no self-citation chain or self-definitional step is invoked to justify the result. The derivation chain is therefore self-contained against external analytic machinery.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Review based solely on the abstract; the central claim rests on standard background results from probability theory and graphon theory rather than new free parameters or invented entities.

axioms (2)
  • standard math Existence and regularity properties of the space of colored graphons and the path topology used for convergence
    Invoked to state that the process converges to a Markov process living on a subset of colored graphons.
  • domain assumption The rate functions are Lipschitz or otherwise regular enough for the limiting stochastic flow and diffusion to be well-defined
    Required for the Fisher-Wright diffusion and color-dependent edge flow to exist in the limit.

pith-pipeline@v0.9.0 · 5676 in / 1343 out tokens · 67317 ms · 2026-05-22T20:23:23.216287+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    the graph process converges, in a suitable path topology, to a limiting Markov process that lives on a certain subset of the space of coloured graphons... density of each vertex colour evolves according to a Fisher-Wright diffusion driven by the density of the edges, while the underlying edge connectivity structure evolves according to a stochastic flow

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    Lemma 3.2 (Action of generator on (regular) subgraph densities)... μv_F(G), μe_F(G), σv_F,F'(G) defined via multisets S(F), S◦(F), T(F,F')

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages · 1 internal anchor

  1. [1]

    Aldous, D. (1989). Stopping times and tightness II.Ann. Probab.17, 586–595

    work page 1989

  2. [2]

    , and Röllin, A

    Athreya, S., den Hollander, F. , and Röllin, A. (2021). Graphon-valued stochastic processes from population genetics.Ann. Appl. Probab.31, 1724–1745

    work page 2021

  3. [3]

    , and Röllin, A

    Athreya, S., den Hollander, F. , and Röllin, A. (2025+). The Moran model with random resampling rates. Preprint at arXiv:2402.01333. To appear inAnn. Appl. Probab

    work page arXiv 2025

  4. [4]

    Avena, R

    Athreya, S. and Röllin, A. (2016). Dense graph limits under respondent-driven sampling. Ann. Appl. Probab.26, 2193–2210. A vena, L., Baldasso, R. , Hazra, R.S. , den Hollander, F. , and Quat- tropani, M. (2024). Discordant edges for the voter model on regular random graphs. ALEA Lat. Am. J. Probab. Math. Stat.21, 431–464. 54 A vena, L., Baldasso, R. , Haz...

    work page arXiv 2016

  5. [5]

    Baldassarri, P

    Baldassarri, S. , Braunsteins, P. , den Hollander, F. , and Mandjes, M. (2024). Opinion dynamics on dense dynamic random graphs. Preprint at arXiv:2410.14618

    work page arXiv 2024

  6. [6]

    Functional central limit theorem for the subgraph count of the voter model on dynamic random graphs

    Baldassarri, S. and Kriukov, N. (2025). Functional central limit theorem for the subgraph count of the voter model on dynamics random graphs. Preprint at arXiv:2503.11541

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  7. [7]

    and Sly, A

    Basu, R. and Sly, A. (2017). Evolving voter model on dense random graphs.Ann. Appl. Probab.27, 1235–1288

    work page 2017

  8. [8]

    , and Wu, R

    Bayraktar, E., Chakraborty, S. , and Wu, R. (2023). Graphon mean field systems. Ann. Appl. Probab.33, 3587–3619

    work page 2023

  9. [9]

    and Miftakhov, A.F

    Bogachev, V.I. and Miftakhov, A.F. (2016). On weak convergence of finite- dimensional and infinite-dimensional distributions of random processes.Theory Stoch. Process.21, 1–11

    work page 2016

  10. [10]

    , V asconcelos, V.V., and Pinheiro, F.L

    Borges, H.M. , V asconcelos, V.V., and Pinheiro, F.L. (2024). How social rewiring preferences bridge polarized communities. Chaos Solit. Fractals 180, 114594

    work page 2024

  11. [11]

    , and Vesztergombi, K

    Borgs, C., Chayes, J., Lovász, L., Sós, V. , and Vesztergombi, K. (2008). Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing.Adv. Math.219, 1801–1851

    work page 2008

  12. [12]

    Braunsteins, F

    Braunsteins, P., den Hollander, F. , and Mandjes, M. (2025+). Graphon- valued processes with vertex-level fluctuations. Preprint at arXiv:2209.01544. To appear inStoch. Proc. Appl

    work page arXiv 2025

  13. [13]

    (2024) Evolution of discordant edges in the voter model on random sparse digraphs

    Capannoli, F. (2024) Evolution of discordant edges in the voter model on random sparse digraphs. Preprint at arXiv:2407.06318

    work page arXiv 2024

  14. [14]

    , Choi, J

    Chen, Y.-T. , Choi, J. , and Cox, J.T. (2016). On the convergence of densities of finite voter models to the Wright-Fisher diffusion.Ann. Inst. Henri Poincaré Probab. Stat.52, 286–322. 55 Černý, J. and Klimovsky, A. (2018). Markovian dynamics of exchangeable ar- rays. InGenealogies of Interacting Particle Systems, volume 38 ofLecture Notes

    work page 2016

  15. [15]

    and Kadelka, D

    Cremers, H. and Kadelka, D. (1986). On weak convergence of integral func- tionals of stochastic processes with applications to processes taking paths inLE p . Stochastic Process. Appl.21, 305–317

    work page 1986

  16. [16]

    , Khare, A

    Diao, P., Guillot, D. , Khare, A. , and Rajaratnam, B. (2015). Differential calculus on graphon space.J. Combin. Theory Ser. A133, 183–227

    work page 2015

  17. [17]

    Durrett, R., Gleeson, J.P., Lloyd, A.L., Mucha, P.J., Shi, F., Siv akoff, D., Socolar, J.E.S., and V arghese, C. (2012). Graph fission in an evolving voter model.Proc. Natl. Acad. Sci. USA109, 3682–3687

    work page 2012

  18. [18]

    and Seiler, M

    Eichhorn, R., Hermann, F. and Seiler, M. (2025). The Offended Voter Model. Preprint at arXiv:2502.18619

    work page arXiv 2025

  19. [19]

    and Kurtz, T.G

    Ethier, S.N. and Kurtz, T.G. (1986). Markov Processes: Characterization and Convergence. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, New York

    work page 1986

  20. [20]

    and Zanette, D.H

    Gil, S. and Zanette, D.H. (2006). Coevolution of agents and networks: Opinion spreading and community disconnection.Phys. Lett. A356, 89–94

    work page 2006

  21. [21]

    Grinblat, L.Š. (1976). A limit theorem for measurable random processes and its applications. Proc. Amer. Math. Soc.61, 371–376

    work page 1976

  22. [22]

    Henry, A.D., Pralat, P., andZhang, C.Q. (2011). Emergence of segregation in evolving social networks.Proc. Natl. Acad. Sci. USA108, 8605–8610

    work page 2011

  23. [23]

    and Liggett, T.M

    Holley, R.A. and Liggett, T.M. (1975). Ergodic theorems for weakly interacting infinite systems and the voter model.Ann. Probab.3, 643–663

    work page 1975

  24. [24]

    and Newman, M

    Holme, P. and Newman, M. (2006). Nonequilibrium phase transition in the co- evolution of networks and opinions.Phys. Rev. E74, 056108

    work page 2006

  25. [25]

    and Kurt, N

    Jansen, S. and Kurt, N. (2014). On the notion(s) of duality for Markov processes. Probab. Surv.11, 59–120

    work page 2014

  26. [26]

    Kurtz, T.G. (1991). Random time changes and convergence in distribution under the Meyer-Zheng conditions.Ann. Probab.19, 1010–1034. 56

    work page 1991

  27. [27]

    Liu, J., Huang, S., Aden, N.M., Johnson, N.F., and Song, C. (2023). Emer- gence of polarization in coevolving networks.Phys. Rev. Lett.130, 037401. Lovász, L. (2012). Large Networks and Graph Limits. American Mathematical Society. Lovász, L. and Szegedy, B. (2006). Limits of dense graph sequences.J. Combin. Theory Ser. B96, 933–957

    work page 2023

  28. [28]

    Coevolution of strat- egy and structure in complex networks with dynamical linking.Phys

    Pacheco, J.M., Traulsen, A., and Now ak, M.A.(2006). Coevolution of strat- egy and structure in complex networks with dynamical linking.Phys. Rev. Lett. 97, 258103

    work page 2006

  29. [29]

    Protter, P.E. (2005). Stochastic Integration and Differential Equations. Springer, Berlin

    work page 2005

  30. [30]

    and Miguel, M.S

    Raducha, T. and Miguel, M.S. (2020). Emergence of complex structures from nonlinear interactions and noise in coevolving networks.Sci. Rep.10, 15660

    work page 2020

  31. [31]

    and Pitman, J.W

    Rogers, L.C.G. and Pitman, J.W. (1981). Markov functions.Ann. Probab.9, 573–582

    work page 1981

  32. [32]

    Skorohod, A.V. (1965). Studies in the Theory of Random Processes.Addison- Wisley 1965 (originally published in Kiev)

    work page 1965

  33. [33]

    Yamada, T.and W atanabe, S.(1971).Ontheuniquenessofsolutionsofstochastic differential equations.J. Math. Kyoto Univ.11, 155–167

    work page 1971