The Setting
Let be a finite simple graph and let be a vertex weight. Write for the neighborhood of a vertex , the set of vertices adjacent to .✦ The vertex sets need not be disjoint.
Neighborhood Contributions
For a real vertex weight on , the common neighborhood mass of vertices is the weighted sum in (1). (1)✦ For a real vertex weight on , the neighborhood triangle contribution at a vertex is the weighted sum in (2). (2)✦
The Definition
Definition 1. For a real vertex weight on , the mass of a vertex set is the sum in (3). (3)✦ For a real vertex weight on , the cross mass between vertex sets is the sum over adjacent pairs directed from to in (4). (4)✦ The unordered edge mass of a real vertex weight on is the quadratic expression in (5). (5)✦ Let denote the set of unordered triangles of . The unordered triangle mass of a real vertex weight on is the cubic sum in (6). (6)✦ The vertex potential is the function in (7), with natural logarithms and the convention . (7)✦ Subtracting the unordered edge mass from the sum of the vertex potentials gives the graph potential of a real vertex weight , as in (8). (8)✦ A global optimizer of is a weight belonging to the set defined by (9). (9)✦
In the paper, the definitions read: , , , and , with also defined for every real vector , while on nonnegative weights and , using .
What Is Checked
These definitions are stated over finite simple graphs, real vertex weights and vertex subsets, with global optimization taken over nonnegative weights.