A Partial Characterization of Robinsonian $L^{p}$ Graphons

The analysis of structure in large networks has been an important question since the beginnings of computer science—many real world data structures are modeled as vast, complex graphs, and determining both local and global behavior is more desirable now than ever. In particular, many physical networks are dynamic in nature, growing in size and structure as new data is collected; equally as important in such changing systems is recognizing and characterizing emergent properties such as clustering or connectedness. The language of graph limit theory offers a powerful method to attack these problems in the form of $L^{p}$ graphons, symmetric measurable functions from $[0,1]^{2}\to{\mathbb{R}}$ with finite $p$-norm $\|\cdot\|_{p}$.

First introduced by Lovász and Szegedy [15], graphons are symmetric measurable functions from $[0,1]^{2}\to[0,1]$, and can be viewed as the limit objects of sequences of graphs under the cut norm $\|\cdot\|_{\Box}$, where

For any labeled graph $G$, the adjacency matrix $A_{G}$ can be inserted into the unit square as a $\{0,1\}$–valued step function $w_{G}$; graphons form the completion of these functions under $\|\cdot\|_{\Box},$ and we denote the space of graphons by ${\mathcal{W}}_{0}$. Given an unlabeled graph $H$, where the adjacency matrix is ill defined, we compare its distance to a graphon using the cut distance $\delta_{\Box}$—the minimum difference in cut norm over all labelings of $H$. This embedding of the adjacency matrix forces sequences of graphs $\{G_{n}\}$ with vanishing edge density to converge to the zero graphon, yielding a trivial result for many classes of networks, such as any graph family whose edges are governed by a power law. Borgs et al. resolved this issue in [1, 2] by instead considering the convergence of the graph sequence $\{G_{n}\}$ normalized by its edge density $\{G_{n}/\|G_{n}\|_{1}\}$. The limit functions of these sequences need only be bounded in $p$-norm and are thus commonly known as $L^{p}$ graphons, whose space is denoted ${\mathcal{W}}^{p}.$

The main attraction of graph limit theory is the ability to answer combinatorial problems using analytic tools. Thus, when considering the problem of recognizing emergent structure and behaviors in a collection of large networks $\mathcal{G}$, it is tempting to find an $L^{p}$ graphon $w$ that is extremely close to $\mathcal{G}$ in cut norm and then test $w$ for the desired structure or behavior. While this approach is often quite powerful, it is not always the case that a combinatorial property of graphs translates to graphons (see for example [11]). Thus, recognizing and characterizing the properties that do extend from graphs to graphons is very useful for the analysis of growing networks, as determining the underlying graphon of a collection of networks can give insight into the collection as a whole.

We study here the Robinson property: an $L^{p}$ graphon $w$ is Robinson if for all $x\leq y\leq z$, then

These functions were defined as diagonally increasing in [4] because they increase toward the main diagonal along a horizontal or vertical line, and are generalizations of Robinson matrices. Sometimes called R-matrices, Robinson matrices appear in the classic problem of seriation (see [14] for a comprehensive review of seriation) and their study is a field of much interest [3, 5, 6, 13]. Given a sequence of graphs $\{G_{n}\}$, can one recognize if they are sampled from a Robinson graphon? It is simpler to tackle the labeled case first and then extend to the unlabeled case, so the problem becomes the following: Construct a function $\Phi:{\mathcal{W}}^{p}\to[0,\infty)$ that measures the Robinson property of a graphon. Such functions are called graphon parameters, and can be chosen to recognize desired structure in $w$. A graphon parameter $\Phi$ is suitable for Robinson measurement if it is subadditive and satisfies the following three properties:

• 1.

  (Recognition) $\Phi(w)=0$ if and only if $w$ is Robinson a.e.

• 2.

  (Continuity) $\Phi$ is continuous with respect to the cut norm.

• 3.

  (Stability) Given a graphon $w$, there exists a Robinson graphon $u$ such that $\|w-u\|_{\Box}\leq f(\Phi(w))$, where $f:[0,\infty)\to[0,\infty)$ is a nondecreasing function with $\lim_{x\to 0^{+}}f(x)=0.$

Provided a sequence of associated graphons $\{w_{G_{n}}\}$ and a graphon $w\in{\mathcal{W}}^{p}$ such that $\|w_{G_{n}}-w\|_{\Box}\to 0$, recognition and stability combined with subadditivity guarantee that the Robinson graphon $u$ is close in cut norm to each $w_{G_{n}}$ by some measure of how Robinson $w$ is, while continuity ensures that the if the $\{w_{G_{n}}\}$ are Robinson, then so is $w$. Thus, any such $\Phi$ will be able to recognize when a sequence of labeled graphs is sampled from a Robinson graphon or a graphon that is almost Robinson (see [10]). However, extending these results to unlabeled graphs is both difficult and dependent on the density of the graph sequence in question.

In this paper, we resolve this problem for unlabeled graphs that converge to $L^{p}$ graphons for $p>5$ in terms of the graphon parameter $\Lambda$ defined in [10]. All graphons in ${\mathcal{W}}^{p}$ for $p>5$ are “$\Lambda$-close” to certain Robinson graphons in the cut norm—thus, if a graph sequence $\{G_{n}\}$ whose associated graphons $\{w_{G_{n}}\}$ grow increasingly Robinson converges to a graphon $w$ in cut distance, there must exist a sequence of Robinson graphons that converge to $w$ in cut distance. Through a combination of the specific properties of these Robinson approximations and functional analytic arguments, we showed that in this case there must exist some Robinson graphon $u$ such that $\delta_{\Box}(u/\|u\|_{1},w/\|w\|_{1})=0$. Therefore, $w$ is Robinsonian precisely when it is the limit object of a sequence of simple graphs $\{G_{n}\}$ such that $\Lambda(G_{n}/\|G_{n}\|_{1})\to 0$.

In this section, we define basic notation used throughout the paper; afterwards, we present graph limit theory, stating required definitions alongside notable results, then transition into explanation of the Robinson property for both matrices and graphons.

All functions and sets discussed during this paper are assumed to be measurable. The Lebesgue measure of a set $A\subseteq{\mathbb{R}}$ is denoted by $|A|$. The notation $\|\cdot\|_{p}$ is used to represent the standard $p$-norm; that is, for a function $f:X\to{\mathbb{R}}$ and $1\leq p<\infty$,

Let $X$ be a normed vector space with inner product $\langle\cdot,\cdot\rangle,$ and let $X^{*}=\{\phi:X\to{\mathbb{R}}~{}|~{}\phi\text{ continuous}\}$ be the dual of $X.$ If $\{\mu_{n}\}_{n\geq 1}\subset X^{*}$ and $\mu\in X^{*}$, we say that $\mu_{n}$ converges weak^∗ to $\mu$, writing $\mu_{n}\to\mu$, if for all $x\in X$, we have that

In particular, the function space $L^{p}[0,1]^{2}$ has $L^{q}[0,1]^{2}$ as its dual, where $q=p/(p-1)$. Thus, for $f_{n}$ to converge weak^∗ to $f$ in $L^{q}[0,1]^{2}$, for all $g\in L^{p}[0,1]^{2}$, it must be true that

In this section we state and prove our main result regarding the characterization of Robinsonian $L^{p}$ graphons. Specifically, we shall prove a generalization of Theorem 2.3 where $w\in\mathcal{W}^{p}$ and where the simple graphs $\{G_{n}\}_{n\geq 1}$ that converge to $w$ do so by satisfying $\delta_{\Box}(G_{n}/\|G_{n}\|_{1},w/\|w\|_{1})\to 0.$ However, while $\Gamma$ is a suitable measurement of the Robinson property for graphons in the space ${\mathcal{W}}_{0}$, the techniques used to show continuity and stability of $\Gamma$ on ${\mathcal{W}}_{0}$ are unable to be extended to the more general space ${\mathcal{W}}^{p}$. Thus, we shall instead prove our characterization result in terms of the graphon parameter $\Lambda$, which was introduced in [10] to address this discrepancy between ${\mathcal{W}}_{0}$ and ${\mathcal{W}}^{p}$. We recall its definition and relevant properties here.

The goal is thus to show for $w$ and $\{G_{n}\}$ where $\delta_{\Box}(G_{n}/\|G_{n}\|_{1},w/\|w\|_{1})\to 0$ that $w$ is Robinsonian if and only if there exists a sequence of vertex labelings $\{\phi_{n}\}_{n\geq 1}$ such that $\Lambda(G_{n}^{\phi_{n}}/\|G_{n}\|_{1})\to 0.$ While the forward direction is rather direct, the reverse direction requires some heavier machinery. There are two ways to show that $w$ is Robinsonian: Firstly, find a measure preserving bijection $\psi$ such that $\Lambda(w^{\psi})=0,$ and secondly, find a Robinson graphon $u\in{\mathcal{W}}^{p}$ such that $\delta_{\Box}(u/\|u\|_{1},w/\|w\|_{1})=0$.

Finding such a $\psi$ is not obvious—indeed, while it is tempting to think of $\psi$ as the limit object of the $\{\phi_{n}\}$, it is not clear that such an object need exist. Proposition 3.2 (iii) provides an avenue of attack for the latter option of showing that $w$ is Robinsonian, as we can use these Robinson approximations of the associated graphons $w_{G_{n}}$ to find a Robinson graphon $u$ of cut distance 0 from $w$. We proceed with this plan below, beginning with a technical lemma showing that for certain partitions $\mathcal{P}$ of $[0,1]$, the step graphon $w_{\mathcal{P}}$ is Robinsonian.

With this lemma at our disposal, we now state and prove our main result about the partial characterization of Robinsonian $L^{p}$ graphons.

Several natural questions present themselves as extensions to this work, the most immediate of which is whether the statement of Theorem 3.5 holds for $1\leq p\leq 5$. As the requirement of $p>5$ is an artifact of the proof method for Proposition 3.2 (iii), an obvious method of attack for this question would be to improve the techniques used to show this result. It is additionally interesting to consider whether this characterization result could be shown for a more general concept of sparse graphons, such as the $k$-shapes introduced in [12], especially as these objects are defined independently of the vertex labeling of the graphs they are associated with. It is likely that a new parameter would need to be defined to quantify these approximation results in this extended setting, and it is of significant interest to the author to see whether similar claims could hold true for these more general objects. Finally, it is natural to wonder whether there are other graph properties for which such characterization results hold—monotonicity is a likely candidate due to its similarity to Robinsonicity, and categorizing other such properties seems a fruitful direction for future work.

The author would like to acknowledge Dr. Mahya Ghandehari, Charli Klein, and Sarah Tillman for their help in editing this paper and the Department of Mathematics at Toronto Metropolitan University for its continued support throughout the process of this research. This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.