PhD Seminar: Directed Networks in Hyperbolic Space

Speaker:  Ilya Kasyanov, second-year PhD student, School of Applied Mathematics, HSE Tikhonov Moscow Institute of Electronics and Mathematics  
Where: Zoom 
When: February 16, 9:30–10:50 

Many experimentally observed undirected networks have small diameter, large clustering coefficient and power-law degree distributions. Random geometric graphs in hyperbolic space have similar properties [1, 2] and thus are well suited for modeling of experimentally observed datasets. Until now, only undirected graphs have been considered within this hyperbolic framework, while there exist many practically important examples of networks with similar topological properties for which the directionality of connections is crucial. Among possible examples are networks of free associations of English [3] and Russian languages, i.e., networks in which nodes are words, and the role of connections is played by associations between them, measured experimentally by interviewing native speakers. This motivates us to study directed geometric graphs in hyperbolic space in search for possible simple models with properties similar to those observed in experimental directed networks.

We discuss several approaches to generating such stochastic directed networks, starting with a naive approach directly generalizing the results of the paper [2], however it does not explain the bidirectional connections observed in real networks.

An alternative approach is to study a nearest neighbour network on a hyperbolic disk, which is constructed as follows: Distribute points on a disk at random with a given density and then connect each point to its m nearest neighbors. We study topological properties of these networks in the limit of large disk size as a function of density of points and parameter m. It turns out that for all densities and large enough size of the disk, the networks have a distinct shell-core structure: in the core of the network (i.e., far from the boundary of the disk) the network is reminiscent of a random geometrical graph in Euclidean space, with Poissonian distribution of the in-degree of nodes. In turn, at the periphery (in the shell), in-degree strongly (exponentially) depends on the spatial coordinate of the node in a way similar to the behavior of undirected graphs studied in [1, 2]. Moreover, the ratio of the sizes of the core and the shell strongly depends on the density of the points, so that there is a sharp crossover between core-dominated regime at low densities and shell-dominated regime at high densities. In the shell-dominated regime, all the typical properties of the undirected random geometrical graphs (power law degree distribution, logarithmically low density, and large clustering coefficient) are recovered.

References
[1] Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., Boguñá, M. Hyperbolic geometry of complex networks, Phys. Rev. E 82, 036106 (2010).
[2] Papadopoulos, F., Kitsak, M., Serrano, M.Á., Boguná, M., Krioukov, M. Popularity versus similarity in growing networks, Nature 489 (7417), 537 (2012).
[3] Nelson, D.L., McEvoy, C.L., Schreiber, T.A., The University of South Florida free association, rhyme, and word fragment norms, Behavior Research Methods, Instruments, & Computers 36: 402 (2004).