On the Number of Maximal Cliques in
Two-Dimensional Random Geometric Graphs:
Euclidean and Hyperbolic

Detecting all maximal cliques in a graph is a crucial analysis tool for real-world networks from various fields: social networks, protein-protein interaction networks, and web graphs because cliques correspond to meaningful components in the networks [22, 21, 3]. Not only does it have many direct applications, but its algorithms and techniques are used in other clique-related methods such as clique percolation [19] and $k$-clique counting [17]. This is because we can detect all cliques by enumerating only the maximal ones.

For general graph inputs, the number of maximal cliques $\mathcal{M}$ can be up to $3^{|V|/3}$ [20]. Therefore, enumerating all of them is NP-hard. However, many studies report that in real-world networks, $\mathcal{M}$ is much smaller than that. Thus, polynomial-delay algorithms, the running time of which is bounded by $poly(|V|)\cdot\mathcal{M}$, can enumerate all maximal cliques in realistic-time span even for networks with millions of vertices [8]. Also, classic Bron-Kerbosch algorithm [5] (plus graph orientation [7]) is known to be efficient in many instances [9], although its worst running time is $O^{*}(3^{|V|/3})$ and not bounded in terms of $\mathcal{M}$. Here we strike upon the question: why is the number of maximal cliques small on real-world networks?

In the study of real-world networks, networks that appear naturally in various fields are considered. In terms of the graph structure, it seems that networks from different domains are entirely different from each other. However, it is known that they share specific common properties. For example, they have a power-law degree distribution: the number of nodes with a vertex degree of $k$ is proportional to $k^{-\gamma}$. In many cases, $\gamma$ is between two and three, and these networks are called scale-free. Additionally, they have the triadic closure property, meaning that if two vertices have common neighbors, they are likely to be connected. The property is often described with a measure called the clustering coefficient, and real-world graphs often have a high clustering coefficient. Other common properties include tree-like structures, small diameter, and small clique number.

One of the most combinatorially studied models of real-world networks is hyperbolic random graphs [18]. The graph is generated by independently placing vertices according to a particular distribution in a two-dimensional space with negative curvature and connecting two vertices within a certain distance. It is thus classified as a random geometric graph. It is known that a hyperbolic plane naturally induces power-law degree distribution [18]. Also, a hyperbolic random graph satisfies a high clustering coefficient with high probability [14], which distinguishes itself from other power-law models such as Barabási-Albert [2] and Chung-Lu random graphs. Parameters studied in this model include: the number of $k$-cliques, clique number [12], treewidth [4], modularity [6], and diameter [13].

In this paper, we consider the number of maximal cliques in hyperbolic random graphs. We also consider the number on two-dimensional Euclidean random geometric graphs, which are the Euclidean counterpart to hyperbolic random graphs. Euclidean random geometric graphs are also thought to be good representations of some types of real-world graphs [15, 16], although they do not possess power-law degree distribution. Our findings are as follows:

For hyperbolic random graphs, we consider the case when $\gamma\in(2,3)$ for hyperbolic random graphs. In this case, the graphs are scale-free and have $\exp(\Omega(|V|^{(3-\gamma)/2}))$ cliques with high probability [12]. In general graphs, the number of maximal cWe and the bound we obtained is much smaller than that.

To prove the main theorem, we consider what is called an octahedral graph $O_{t}$. The definition of the graph is the following. Let $tK_{2}=(V,E)$ where $V=\{1,2,...,2t\}$ and $E=\{(i,i+t):1\leq i\leq t\}$. Therefore, $tK_{2}$ is a graph with $t$ pairwise disjoint edges. An octahedral graph $O_{t}$ is the complement of $tK_{2}$. We have the following theorems from the previous study.

Let $\tau(G)$ be the maximum $t$ such that a graph $G$ has $O_{t}$ as its vertex-induced subgraph. With these theorems, all that remains is to bound $\tau$. If $\tau$ is a constant, then the number of maximal cliques is polynomial. Unfortunately, this is not the case for the two random geometric graphs. However, our bounds on $\tau$ are much smaller than the obvious $O(|V|)$ bound.

Intuitively, $\tau$ is small because any pair of unconnected vertices have $2t-2$ common neighbors, which is against the triadic closure property, i.e. two vertices with common neighbors are likely to be connected. As $t$ gets larger, the more severe the violation becomes. This explanation can be mathematically justified on Euclidean and hyperbolic random geometric graphs. The arguments on the two different random graphs are basically the same even though the definitions of distance are different, and the parallel postulate does not hold on a hyperbolic plane.

Our contributions are briefly summarized as follows. Firstly, to the best of our knowledge, this is the first work that assesses the number of maximal cliques on random geometric graphs. We shed light on the importance of $O_{t}$ and develop geometric and probabilistic techniques to determine its size. Those techniques apply to both Euclidean and hyperbolic planes. Secondly, what we have found is yet another result followed by $c$-closed graphs [11] supporting that the triadic closure property plays an essential role in maximal cliques. Lastly, we give an upper bound of $\tau$ on real-world graph datasets. It turns out that $\tau$ is often at most 5-20, even on networks with hundreds of thousands of vertices (See Table 1 at the end of this paper). The upper bound of $\mathcal{M}$ given by $\tau$ is still far from the actual value. However, it is still surprising how small $\tau$ is in practice.

Here we explain how we bound $\tau$. For the lower bound, we construct regions so that vertices on them would form $O_{t}$. Here we use a technique called Poissonization introduced in [23].

To derive the upper bound, We define a set of segments $\mathcal{S}:=\{\overline{vw}:v,w\in V(G),$ the distance between $v$ and $w$ is greater than the connection distance$\}$. Since $\mathcal{S}$ is somewhat like the complement of the graph, a vertex-induced subgraph that is isomorphic to $O_{t}$ corresponds to $t$ segments that are pairwise disjoint (or we call “independent” in this paper). We soon find out that any two independent segments must intersect. Therefore, we can define an “angle” between them. By the pigeonhole principle, if $t$ is large enough, then there exists a set of segments with decent cardinality whose “angles” are small (Lemma 2.10 and Lemma 3.14). We also prove that if two intersecting segments have small “angles”, the geometry is very restricted. If we fix one segment, then endpoints of the other segments can only exist in small regions (Corollary 2.8 and Corollary 3.12). By combining the two facts, we derive that $t$ cannot get too large because the number of vertices in those small regions cannot be too large with high probability.

Unlike Euclidean random geometric graphs, vertices in hyperbolic random graphs are placed by non-uniform distribution. To deal with this, we classify the segments by the density around their endpoints. We treat the segments in dense regions slightly differently from those in sparse regions. However, the overall strategies of the proof are the same as Euclidean random geometric graphs.

In Section 2, we define Euclidean random geometric graphs and prove the main theorem. In Section 3.1-3.3, we define hyperbolic random graphs and discuss how the proof of the random geometric graphs on a Euclidean plane can be extended to a hyperbolic plane. For the upper bound, we prove the weaker version of the main theorem. In Section 3.4, we discuss how to treat the non-uniformity of hyperbolic random graphs and prove the complete version of the main theorem. Finally, Section 4 is the conclusion.

Let $n\in\mathbb{N}^{+}$, and $r\in(0,1)$. A two-dimensional Euclidean random geometric graph $G_{n,r}$ is obtained as below:

• •

  The vertex set is $V=\{1,2,...,n\}$.

• •

  The vertices are identically and independently distributed on $[0,1]^{2}$ according to a probability density function $f(x,y)=1$.

• •

  The edge set $E$ is given by $\{(u,v):dist(u,v)\leq r\}$

Here, $dist(u,v)=\sqrt{(u_{x}-v_{x})^{2}+(u_{y}-v_{y})^{2}}$ where $(u_{x},u_{y})$ and $(v_{x},v_{y})$ are the $xy$-coordinates of $u$ and $v$ respectively. From here, we often identify a vertex with its position.

Given a region $U$ on $[0,1]^{2}$ (where we can perform integration), define $F(U):=\int_{U}f(x,y)dxdy$. $F(U)$ is equal to the probability that a vertex lies on $U$. Note that we can assume no three vertices lie on a single line since the probability is 0. This avoids some corner case arguments.

Let $k\geq 4$ be an integer. Let $o^{\prime}=(1/2,1/2)$. Consider taking a polar coordinate system whose origin is $o^{\prime}$. Let $\theta_{0}:=\pi/(3k)$. For $1\leq i\leq 2k$, Define $U_{i}:=\{(r^{\prime},\phi):r_{1}\leq r^{\prime}\leq r_{2},\ 3(i-1)\theta_{0}\leq\phi\leq(3(i-1)+1)\theta_{0}\}$ where $r_{1}:=r/\sqrt{2+2\cos(\theta_{0}/2)}$ and $r_{2}:=r/\sqrt{2+2\cos(2\theta_{0})}$. With some calculations, we can confirm the following.

For $1\leq i\leq k$, let $t_{i}$ be 0-1 random variables which are equal to 1 if and only if both $U_{i}$ and $U_{i+k}$ have at least one vertex on themselves. Let $t=\sum_{i=1}^{k}t_{i}$. Then, there exists $O_{t}$ as a vertex-induced subgraph. We are left to lower bound $t$.

By combining the proposition with the Theorem 1.3, we obtain the main theorem regarding $\mathcal{M}(G_{n,r})$.

Let $\overline{vw}$ denote the segment between vertices $v$ and $w$ on a Euclidean plane. Let $\mathcal{S}:=\{\overline{vw}:v,w\in V(G),dist(v,w)>r\}$. Note that $\mathcal{S}$ is like a complement of the random graph. Two segments $\overline{v_{1}v_{2}}$ and $\overline{w_{1}w_{2}}$ in $\mathcal{S}$ are called independent if $\overline{v_{1}w_{1}}$, $\overline{v_{1}w_{2}}$, $\overline{v_{2}w_{1}}$, and $\overline{v_{2}w_{2}}$ are not in $\mathcal{S}$. Two or more segments in $\mathcal{S}$ are called independent if any pair of the segments are independent. From the definition, it is obvious that the following proposition holds.

Therefore, we are left to bound such $t$ on $G_{n,r}$. With elementary geometry, we can confirm the following.

We defer the proof to the next section. Thanks to the proposition, we can define an angle between two independent segments thanks to the proposition.

Let $s:=\overline{v_{1}v_{2}}$ and $s^{\prime}:=\overline{w_{1}w_{2}}$ be independent segments. Suppose that the counter-clockwise order of four endpoints is $v_{1}w_{1}w_{2}v_{2}$. Let $q$ be the intersection of two segments. Define a directed angle $\angle(s,s^{\prime}):=\angle w_{1}qv_{1}$. For convinience, define $\angle(s,s):=0$. It holds that $\angle(s,s^{\prime})=\pi-\angle(s^{\prime},s)$. Therefore, the order of the two segments matters.

From here, we consider conditions that two independent segments mWe angle between them is known. Again, $s=\overline{v_{1}v_{2}},s^{\prime}=\overline{w_{1}w_{2}}\in\mathcal{S}$ be independent segments. Suppose $v_{1}w_{1}v_{2}w_{2}$ is the counter-clockwise order of four endpoints. Let $m$ be the midpoint of $s$. Consider taking a polar coordinate system whose origin and polar axis are $m$ and $\overrightarrow{mv_{1}}$. Let $(r_{0},\phi)$ be the polar coordinate of $w_{1}$. Note that $r_{0}=dist(m,w_{1})$ and $\phi=\angle w_{1}mv_{1}$ (refer to Figure 3). The next proposition states that if the directed angle $\angle(s,s^{\prime})$ is small, then $r_{0}$ is bounded tight.

If $v_{1},q,m,v_{2}$ are lined up in this order, we can bound $\phi$ as $0\leq\phi\leq\theta\leq\theta_{0}$. By considering the other case ($v_{1},m,q,v_{2}$ is lined up in this order) in the same way, we have the following.

Then we obtain the next lemma: if the directed angle is bounded small, the expected number of independent segments is also small.

To fully use the Lemma 2.9, we prove another lemma, which states that if there exists large $O_{t}$, we can always take a set of segments so that its size is unneglectable, and the directed angles between them are small.

We finally combine the two lemmas to upper bound $\tau$. After that, we apply Theorem 1.4 to get the upper bound of the number of maximal cliques.

Finally, we apply a union bound over all segments of which there are at most $n(n-1)/2$. We have

This goes to 0 as $n\rightarrow\infty$.  $\Box$

Given $n\in\mathbb{N^{+}}$, $\gamma\in(2,\infty)$, and $C\in\mathbb{R}$, let $R:=2\log n+C$, and $\alpha=(\gamma-1)/2$. A hyperbolic random graph $G_{n,\gamma,C}$ is obtained as below:

• •

  The vertex set is $V=\{1,2,...,n\}$.

• •

  The vertices are identically and independently distributed on a hyperbolic plane. The probability density function by a polar coordinate is:

  $\displaystyle f(r,\theta)=\begin{cases}\frac{1}{2\pi}\cdot\frac{\alpha\sinh(\alpha r)}{\cosh(\alpha R)-1}&(r\leq R)\\ 0&(r>R)\end{cases}$

• •

  The edge set $E$ is given by $\{(u,v):dist(u,v)\leq R\}$

In our work, we are interested in the case $2<\gamma<3\ (1/2<\alpha<1)$ where the generated graph is “scale-free” with high probability. Let $(r_{u},\phi_{u})$ and $(r_{v},\phi_{v})$ be polar coordinates of $u$ and $v$ respectively. Let $\theta:=\pi-|\pi-|\phi_{u}-\phi_{v}||$. Then, the hyperbolic cosine formula suggests that

Again, define $F(U):=\int_{U}f(r,\theta)drd\theta$. On a hyperbolic plane, the area of $U$ is equal to $\int\sinh rdrd\theta=:\mu(U)$. Let $\rho(r,\theta):=\frac{dF}{d\mu}=\frac{f(r,\theta)}{\sinh r}$. Since the value of $\rho(r,\theta)$ does not depend on $\theta$, we sometimes denote it as $\rho(r)$. Intuitively, $\rho$ is the the probability that a vertex lies on a single unit square around $(r,\theta)$. By differentiating $\rho$, we can confirm that it is monotonically decreasing with respect to $r$. Thus, the graph is dense near the origin of the plane.

Let $o$ be the origin of the plane. We define $B_{0}(d)$ as the set of points $p$ such that $dist(p,o)<d$. In other words, $B_{0}(d):=\{(r,\phi):r<d\}$.

To obtain the lower bound of $\mathcal{M}(G_{n,r,C})$, we do the same thing as the Euclidean random geometric graphs i.e. We take regions so that vertices on them form $O_{t}$.

Let $k\geq 4$ be an integer. Let $\theta_{0}:=\pi/(3k)$. For $1\leq i\leq 2k$, Define $U_{i}:=\{(r,\phi):r_{1}\leq r\leq r_{2},\ 3(i-1)\theta_{0}\leq\phi\leq(3(i-1)+1)\theta_{0}\}$ where $r_{1}$ and $r_{2}$ are determined as

We now assume that $r_{1}<r_{2}\leq R$. We later confirm this holds under proper $\theta_{0}$ and $n$.

For $1\leq i\leq k$, let $t_{i}$ be 0-1 random variables which are equal to 1 if and only if both $U_{i}$ and $U_{i+k}$ have at least one vertex on themselves. Let $t=\sum_{i=1}^{k}X_{i}$. Then, there exists $O_{t}$ as a vertex-induced subgraph. Again, we are left to lower bound $t$.