Random-walk kernels on graphs #
Kernels on the vertices of a finite simple graph G with no isolated vertex
(hd : ∀ v, 0 < G.degree v):
Kernel.uniformNeighbor G hd: move to a uniformly random neighbour,D⁻¹A. Its support is the edge set (uniformNeighbor_support) and its expectations are neighbour averages (uniformNeighbor_expect, anduniformNeighbor_expect_eq_avgin theavgform ofDynamics/GraphRounds.lean).Kernel.lazyNeighbor G hd = lazy (uniformNeighbor G hd): the lazy random walk(I + D⁻¹A)/2(lazyNeighbor_weight,lazyNeighbor_expect).
noncomputable def
Dynamics.Kernel.uniformNeighbor
{V : Type u_1}
[Fintype V]
(G : SimpleGraph V)
[DecidableRel G.Adj]
(hd : ∀ (i : V), 0 < G.degree i)
:
Kernel V
Uniform sampling among the neighbours: the simple random walk D⁻¹A on G.
Equations
Instances For
theorem
Dynamics.Kernel.uniformNeighbor_support
{V : Type u_1}
[Fintype V]
(G : SimpleGraph V)
[DecidableRel G.Adj]
(hd : ∀ (i : V), 0 < G.degree i)
(i j : V)
:
The simple random walk charges exactly the edges.
theorem
Dynamics.Kernel.uniformNeighbor_expect
{V : Type u_1}
[Fintype V]
{G : SimpleGraph V}
[DecidableRel G.Adj]
(hd : ∀ (i : V), 0 < G.degree i)
(x : V)
(f : V → ℝ)
:
Expectation under uniform neighbour sampling is the average over the neighbours.
theorem
Dynamics.Kernel.uniformNeighbor_expect_eq_avg
{V : Type u_1}
[Fintype V]
{G : SimpleGraph V}
[DecidableRel G.Adj]
(hd : ∀ (i : V), 0 < G.degree i)
(x : V)
(f : V → ℝ)
:
Expectation under uniform neighbour sampling is the uniform average avg over the
neighbour set.
noncomputable def
Dynamics.Kernel.lazyNeighbor
{V : Type u_1}
[Fintype V]
(G : SimpleGraph V)
[DecidableRel G.Adj]
[DecidableEq V]
(hd : ∀ (i : V), 0 < G.degree i)
:
Kernel V
The lazy random walk (I + D⁻¹A)/2 on G: stay with probability 1/2, otherwise move to
a uniformly random neighbour.
Equations
Instances For
theorem
Dynamics.Kernel.lazyNeighbor_weight
{V : Type u_1}
[Fintype V]
(G : SimpleGraph V)
[DecidableRel G.Adj]
[DecidableEq V]
(hd : ∀ (i : V), 0 < G.degree i)
(i j : V)
:
Entries of the lazy random walk: (I + D⁻¹A)/2.
theorem
Dynamics.Kernel.lazyNeighbor_expect
{V : Type u_1}
[Fintype V]
{G : SimpleGraph V}
[DecidableRel G.Adj]
[DecidableEq V]
(hd : ∀ (i : V), 0 < G.degree i)
(x : V)
(f : V → ℝ)
:
Expectation under the lazy random walk: half the current value plus half the neighbour average.