The Setting
Neighborhood walks study adjacency inside the neighborhood of a fixed vertex. Let be a finite simple graph on , with a real vertex weight . The neighborhood of a vertex is its set of adjacent vertices, and the mass of a vertex set is its total weight, as in (1): (1) The common neighborhood mass of vertices is the weight of their common neighbors, defined in (2): (2)✦
The oriented edges of are the ordered pairs .✦ An oriented edge has tail and head . A kernel on a finite state set is a real matrix indexed by .✦ Write for the identity matrix on . Quotients with zero denominator are taken to be zero. For real arguments, means the natural logarithm of when , with ; zero mass contributes zero to weighted entropy.
The Definition
Definition 1. Let be a finite simple graph with real vertex weight . The neighborhood transition kernel on is the matrix in (3): (3)✦ The local walk normalizer of a finite simple graph with real vertex weight is the scalar in (4): (4)✦ For a finite simple graph with real vertex weight , the local walk edge law is the real weight on given by (5): (5)✦ For a finite simple graph with real vertex weight , the destination weight is the real weight on given by (6): (6)✦
Let be a kernel on a finite set . The lazy kernel of a kernel on a finite state set is the matrix on in (7): (7)✦ For a kernel on a finite state set and an integer , the smoothed kernel is the th power of the average of and the identity kernel. (8)✦
For real weights on a finite state set , the weighted entropy is the scalar in (9): (9)✦ For a kernel and real weights on a finite state set , the average row entropy is the scalar given by the weighted sum in (10): (10)✦ The total variation distance of real weights on a finite state set is the scalar in (11): (11)✦ For a finite simple graph with real vertex weight and an integer , the mean row variation of its neighborhood walk is the scalar in (12): (12)✦
In the paper, the result reads: let have positive vertex weights, satisfy the cross-mass bound with , and have an edge, fix , assume for every and on every edge, and put ; at each nonisolated , set , , and ; put , where is the sum of over unordered triangles, and on directed edges; sampling from and from gives probability to each ordered triangle; define , and .
What Is Checked
The definitions are stated over finite simple graphs with real vertex weights, their oriented edges, and real matrix kernels and real weights on finite state sets.