Connectivity of a Family of Bilateral Agreement Random Graphs

Graphs are powerful mathematical tools used for modeling objects in a wide variety of topics [5, 8, 11]: from the Internet and chemistry to social science and economics. These mathematical objects have been studied using algebraic, combinatorial, and stochastic methods. Studying graphs using a stochastic framework [2, 4, 12] has a long history starting from when Gilbert introduced his random graph model in [7] in $1959$, and Erdős and Rényi introduced the well-known Erdős-Rényi model in their celebrated paper [6] in $1960$. These fundamental random graph models have been extensively analyzed over the last $50$ years.

An Erdős-Rényi random graph with $n$ vertices is characterized by a parameter $0\leq p(n)\leq 1$ indicating the probability of existence of each potential undirected edge between two vertices. Edges then appear independently based on Bernoulli coin tosses with no intrinsic preference between the edges on the part of the vertices. One question that immediately arises by specifying the parameter $p(n)$ is whether the Erdős-Rényi graphs are connected when $n\rightarrow\infty$. In particular, Erdős and Rényi [6, 2, 4, 12] prove that if $p(n)=t\log(n)/n$, with high probability, the graph is connected for $t>1$ and disconnected for $t<1$; note that the mean degree in this setting is $t\log(n)$. In fact, the refined result is that if (for large enough $n$) $p(n)=(\log(n)+c)/n$, then the graph is connected with probability $e^{-e^{-c}}$.

Cooper and Frieze in [3] described a new family of random graphs based on preferences constructed using a distance measure. They considered the complete graph $K_{n}$ and assigned independent uniform $[0,1]$ random variables as distances to all edges. They then keep the $k(n)$ shortest edges incident to each vertex. In this model, the concept of distance induces a preference order on all edges. Indeed, the shorter an edge is the higher its preference is. Since the distances are i.i.d., the preference order on all the edges will be chosen uniformly over the set of all permutations. We say a vertex proposes an edge if the edge belongs to the set of the $k(n)$ most-preferred edges incident to it. Note that in this model, an edge is kept if at least one of its endpoints proposes it, which is a unilateral perspective.

Preference relations of the sort used by Cooper and Frieze create a complicated structure on any resulting graph. For example, keeping edges based on their ranking even in the unilateral mode as done by Cooper and Frieze, induces an edge dependency which is not the case for the Erdős-Rényi model. Cooper and Frieze [3] studied the connectivity of their model and proved that the graph is connected with high probability for $k\geq 3$. They also provided upper and lower bounds for the probability of connectivity as $n\rightarrow\infty$ when $k=2$.

Just like the Cooper-Frieze unilaterally proposed random graphs, bilateral agreement random graphs introduced by La and Kabkab [9], are constructed based on the same parameter $k(n)$, which is the maximum number of other vertices each vertex wants as its neighbors. Considering vertices as agents, once again, all agents have their own preferences on the potential edges with others via a priority or preference order over other agents. Then, in contrast to both the Erdos-Renyi and the Cooper-Frieze models, an edge is drawn if and only if each end vertex has the other vertex in its $k(n)$ preferred vertices, i.e., if and only if both end vertices propose an edge, which then leads to bilateral agreement.

One can interpret the bilateral agreement model as a network formation process conducted via a game (selfish objective maximization) among agents. These kinds of network formation processes [5, 8, 11] have been studied in social science and economics. Assume there are $n$ agents that are aware of their own benefits from the potential pairwise contracts with others where the benefit is assessed via an appropriate reward, cost or even distance measure. Then each agent agrees on its own $k(n)$ most profitable contracts. Finally, each contract will be concluded if and only if both parties mutually agree to it, and the graph of pairwise connections will be generated. The interpretation above highlights the importance of bilateral agreement random graphs from a game-theoretic (i.e., individual agent oriented) point of view.

A core question studied in the La and Kabkab paper [9] is the determination of the choice of $k(n)$ that results in the graphs produced being connected. The authors showed the following results hold with high probability: 1) if $k(n)>C\log(n)$ for $C=2.4625$, then the graph is connected; and 2) $k(n)<c\log(n)$ for $c=0.5$, then the graph has isolated vertices and so is not connected. Furthermore, using extensive simulation-based experimentation, they also conjectured that the connectivity threshold was exactly $k(n)=\log(n)$, surprisingly, which is the same threshold for connectivity of the Erdős-Rényi random graphs family in terms of the mean degree; note, however, that $k(n)$ is the maximum degree in the La-Kabkab random graph family. In this paper, we show the following:

1. 1.

   In Lemma 4.6 we show that the expected number of isolated vertices increases without bound if $k\leq\log(n)-3\sqrt{\log(n)\log\log(n)}$; see Section 4.

2. 2.

   Using Lemma 4.6 and additional results, in Theorem 4.1 we prove that graphs from the La-Kabkab random graph family are not connected with high probability if $k\leq\log(n)+t^{\prime}(\log\log(n))\sqrt{\log(n)}$ for $t^{\prime}<-1/2$; see Section 4.

3. 3.

   Theorem 5.3 then establishes that graphs from the La-Kabkab random graph family are connected with high probability if $k\geq\log(n)+t^{\prime}(\log\log(n))\sqrt{\log(n)}$ for $t^{\prime}>1/2$; see Section 5.

4. 4.

   Finally, in Theorem 6.2 assuming that $k$ grows to infinity with $k=o(n^{1/3})$, we show that the mean degree for graphs from the La-Kabkab random graph family asymptotically behaves like $k-\sqrt{\tfrac{k}{\pi}}+\tfrac{1}{8\sqrt{\pi k}}+o(\tfrac{1}{\sqrt{k}})$, i.e., the mean degree is asymptotically close to the maximum possible degree; see Section 6.

Whereas Theorem 4.1 and Theorem 5.3 establish the conjecture by La and Kabkab, they still do not precisely identify the connectivity threshold in comparison to existing results on the Erdős-Rényi random graph family [4, 12]. We believe this arises due to our use of analytically simpler sufficient conditions to prove both results, and hence, a different analysis could overcome this lacuna.

A different but related line of work from the connectivity question is that of Moharrami et al. [10], where they introduced a new branching process called the Erlang Weighted Tree (EWT) as the local weak limit of the bilateral agreement random graphs of La and Kabkab in the sparse regime. In [10] the parameter $k(n)$ is a (finite) random parameter $k$ for each vertex that is independently chosen and identically distributed with a distribution on $\mathbb{N}$ with finite mean. The authors then studied the degree distribution of the root vertex and its average. We will return to this specific result of [10] in Section 6 when we discuss the asymptotics of the mean degree. The authors of [10] also discuss the probability of extinction of an EWT, and conjecture its relevance to the size of the giant component [6, 4, 12] of the bilateral agreement random graphs of La and Kabkab, when there is one.

Consider the complete undirected graph $K_{n}$ with vertices $[n]=\{1,2,\cdots,n\}$ and edges $\{(i,j):1\leq i,j\leq n,i\neq j\}$ where we assume $(i,j)=(j,i)$. Let $k(n)$ be an integer such that $1\leq k(n)\leq n$; henceforth, to avoid cumbersome notation, we will use $k$ instead of $k(n)$. We assign independently and identically distributed random variables called priority scores to all edges of $K_{n}$. For any explicit calculations, one can assume they are uniformly distributed in $[0,1]$ or exponentially distributed with parameter $1$; this holds because we will only be interested in the order statistics. We denote the score of edge $(i,j)$ by $V(i,j)=V(j,i)$. The set of all scores of the edges of vertex $i\in[n]$ is denoted by $\mathcal{V}_{i}=\{V(i,1),\cdots,V(i,i-1),V(i,i+1),\cdots,V(i,n)\}$, and all the associated edges by $\mathcal{E}_{i}=\{(i,1),\cdots,(i,i-1),(i,i+1),\cdots,(i,n)\}$. Without loss of generality, we can also assume that the scores are distinct, then $(R_{i}^{j})_{1\leq j\leq n-1}$ represents an order on $[n]\setminus\{i\}=\{1,2,\cdots,i-1,i+1,\cdots,n\}$ based on $V(i,j)$ values. In other words, for each $1\leq i\leq n$, the random vector $\mathcal{R}_{i}=(R_{i}^{1},R_{i}^{2},\cdots,R_{i}^{n-1})$ is a permutation of $[n]\setminus\{i\}$ in which

As the scores are chosen i.i.d., the distribution of the random vector $\mathcal{R}_{i}$ is uniform among all permutations of $[n]\setminus\{i\}$ as it only depends on the order-statistics. In general, the scores also impose a permutation over all the edges. This plays an important role in defining the bilateral agreement random graphs.

Let $V(i,j)$ be realized for all edges $(i,j)$ and parameter $k$ be fixed. Then we can determine two different classes of random graphs on vertices $[n]$. We first define the notion of agreement. If $V(i,j)$ is among the $k$ largest scores in $\mathcal{V}_{i}$, i.e., $j\in\mathcal{R}_{i}^{\leq k}:=\{R_{i}^{1},R_{i}^{2},\cdots,R_{i}^{k}\}$ or $(i,j)\in\mathcal{E}_{i}^{\leq k}:=\{(i,R_{i}^{1}),\cdots,(i,R_{i}^{k})\}$, we say that vertex $i$ proposes edge $(i,j)$. The first model introduced by Cooper and Frieze [3] let the edge $(i,j)$ be present if at least one of $i$ or $j$ proposes $(i,j)$. We denote this class of random graphs by $\mathbb{F}(n,k)$, which we call the class of unilaterally proposed graphs. The second model described by La and Kabkab [9] requires the proposal by both vertices for an edge to appear, which we deem as a bilateral agreement. We denote this class by $\mathbb{G}(n,k)$ and we call it the class of bilateral agreement random graphs.

Both $\mathbb{F}(n,k),\mathbb{G}(n,k)$ only depend on the order of $V(i,j)$ not the values. This is the consequence of the scores being i.i.d., which results in a uniformly drawn permutation among all permutations of edges of $K_{n}$. Assigning a random variable to each edge only helps us to understand the extent of independence in this problem. However, in the analysis of any underlying probability, we will always refer to the permutation viewpoint of the construction of these random graphs.

In the following sections, we will analyze the connectivity of $\mathbb{G}(n,k)$ when $k$ is around $\log(n)$ as $n\rightarrow\infty$. More precisely, we will prove that when $k=t\log(n)$ with high probability this graph will be connected for $t>1$ and disconnected for $t<1$, and also attempt to determine the connectivity threshold with greater precision.

In our analysis we will use the abstraction of an infinite urn model. The next two lemmas allow us to link the probability of an event in finite permutations space to an event in the infinite urn model. In essence, we will show that the appropriate probabilities converge to a negative multinomial distribution. Before delving into details, we will consider the set of all permutations with order restrictions over some elements. The notation $x\succ y$ states that $x$ appears earlier than $y$ in the permutation. We need to work on the set of all permutations with some order restrictions. For instance, whenever we say the set of permutations of $\{1,2,3\}$ with order restrictions $\{1\succ 2,1\succ 3\}$, this narrows down the the set of all $3!=6$ permutations to $\{(1,2,3),(1,3,2)\}$.

Lemmas 3.1 and 3.2 demonstrate that a negative multinomial distribution is the limit for the distribution of number of other types before the first appearance of a given type. As mentioned earlier, this distributional convergence will help us greatly in our analysis. The special case required in this paper fixes all $h_{i}=1$. Therefore, we state the following lemma.

This section begins by recalling the negative multinomial distribution. In the special case that we need here, we present an urn model to interpret the distribution. Suppose we have a sequence of i.i.d. random variables with $k+1$ possible outcomes chosen uniformly at random. We describe these outcomes as the type of objects. Therefore, there are $k+1$ types. This sequence stops as soon as the first object of type $k+1$ occurs in the sequence. The probability that there are $i_{1}$ objects of type 1, $i_{2}$ objects of type 2, … , $i_{k}$ objects of type $k$, and finally the $n-$th observation which is of type $k+1$, follows the negative multinomial distribution below

in which $i_{t}\geq 0$ for $1\leq t\leq k$ and $i_{1}+i_{2}+\cdots+i_{k}=n-1$.

We now introduce some lemmas that help with any required computation.