Works

Let V and U be the point sets of two independent homogeneous Poisson processes on R^d. A graph G_V with vertex set V is constructed by first connecting pairs of points ( v , u ) with v ∈ V and u ∈ U independently with probability g( v − u ), where g is a non-increasing radial function, and then connecting two points v1, v2 ∈ V if and only if they have a joint neighbor u∈U. This gives rise to a random intersection graph on R^d. Local properties of the graph, including the degree distribution, are investigated and quantified in terms of the intensities of the underlying Poisson processes and the function g. Furthermore, the percolation properties of the graph are characterized and shown to differ depending on whether g has bounded or unbounded support. 

We consider the problem of detecting whether a power-law inhomogeneous random graph contains a geometric community, and we frame this as an hypothesis testing problem. More precisely, we assume that we are given a sample from an unknown distribution on the space of graphs on n vertices. Under the null hypothesis, the sample originates from the inhomogeneous random graph with a heavy-tailed degree sequence. Under the alternative hypothesis, k=o(n) vertices are given spatial locations and connect between each other following the geometric inhomogeneous random graph connection rule. The remaining n−k vertices follow the inhomogeneous random graph connection rule. We propose a simple and efficient test, which is based on counting normalized triangles, to differentiate between the two hypotheses. We prove that our test correctly detects the presence of the community with high probability as n→∞, and identifies large-degree vertices of the community with high probability. 

In the past decade, geometric network models have received vast attention in the literature. These models formalize the natural idea that similar vertices are likely to connect. Because of that, these models are able to adequately capture many common structural properties of real-world networks, such as self-invariance and high clustering. Indeed, many real-world networks can be accurately modeled by positioning vertices of a network graph in hyperbolic spaces. Nevertheless, if one observes only the network connections, the presence of geometry is not always evident. Currently, triangle counts and clustering coefficients are the standard statistics to signal the presence of geometry. In this paper we show that triangle counts or clustering coefficients are insufficient because they fail to detect geometry induced by hyperbolic spaces. We therefore introduce a novel triangle-based statistic, which weighs triangles based on their strength of evidence for geometry. We show analytically, as well as on synthetic and real-world data, that this is a powerful statistic to detect hyperbolic geometry in networks.

Many real-world networks were found to be highly clustered and contain a large amount of small cliques. We here investigate the number of cliques of any size k contained in a geometric inhomogeneous random graph: a scale-free network model containing geometry. The interplay between scale-freeness and geometry ensures that connections are likely to form between either high-degree vertices, or between close by vertices. At the same time, it is rare for a vertex to have a high degree, and most vertices are not close to one another. This trade-off makes cliques more likely to appear between specific vertices. In this article, we formalize this trade-off and prove that there exists a typical type of clique in terms of the degrees and the positions of the vertices that span the clique. Moreover, we show that the asymptotic number of cliques as well as the typical clique type undergoes a phase transition, in which only k and the degree-exponent τ are involved. Interestingly, this phase transition shows that for small values of τ⁠, the underlying geometry of the model is irrelevant: the number of cliques scales the same as in a non-geometric network model.