Union of Random Hyperbolic Graphs

This brief (and unfinished) post describes the basis of ongoing work regarding the properties of the union of RHGs, a type of graphs that can repsresent real social networks with high fidelity. The social network similarity is corroborated by the power-law degree distribution observed in RHGs. This distribution manifests within a specific parameter range of the model. In this regime, where the degree distribution conforms to a power law with an exponent between 2 and 3, the emergence of a giant component is guaranteed almost surely (a.a.s.). We want to explore various characteristics of the union of hyperbolic graphs, such as the size of the \(k\)-core, the number of connected components, and the diameter of the giant component.

We define such union in the following way. Let \(G=(V, E)\) be a random hyperbolic graph. Let edges \(e\in E(G)\) be labelled $uv$ for \(u<v\) and \(u, v\in V(G)\) connected. For a collection of \(k\) graphs with the same labelling and number of vertices, we define the union graph \(U\) as:

\[U(V, E)=\left(V, \bigcup_{i\in k}E(G_i) \right)\]

We have observed that the curves defined by the \(k\)-core size indicate that the sizes of \(k\)-cores increase following a sigmoid growth. Those cores with smaller $k$ value grow more rapidly than those with greater $k$. This is explained through the degree distribution of RHG, known to be a power law. For greater \(k\) values, the \(k\)-core is smaller since few vertices have large degrees, and to build such great negihborhoods by union is slow.