[Network seminar] 17th November at LPI x online: Nearest-neighbour network in hyperbolic space
Liubov
Title of the talk: Nearest-neighbour network in hyperbolic space: a simple model with applications to recommendation systems. Case of a model with a directed network with asymmetric degree distribution
Mike Tamm is ERA Chair for Cultural Data Analytics, School of Digital Technologies, Tallinn University, Tallinn, Estonia
Abstract:
Reference and recommendation networks are ubiquitous: encyclopedia articles and scientific papers refer to each other, people recommend each other books, films and music, online shops are full of “people who like this also like that” recommendations. Such networks are substantially asymmetric: the rules according to which a node becomes a source are different from those according to which it becomes a target. Often, the number of recommendations given is effectively bounded, while the number of times a node is recommended (in-degree) is unlimited and has a wide distribution.
Here we suggest a relatively simple model of a directed network with asymmetric degree distribution: narrow distribution of out degree and (generally speaking) wide distribution of the in degree, and study its structural properties. Our model belongs to the hyperbolic class and is a direct generalization of nearest-neighbor models studied extensively for the case of Euclidean metric spaces.
Consider a disk on a hyperbolic space, put a large number of points onto the disk uniformly at random, and then connect each point by directed links to a fixed number m of its nearest neighbors. We study the properties of resulting networks in the limit when the area of the disk diverges while the dimensionless density of the points (measured in the space curvature units) remains constant. We show that the resulting networks consist of two distinct parts, a central core where the in-degree has an approximately Poissonian distribution with average m, and peripheral part, where the average in-degree is position-dependent and increases exponentially with increasing distance from the periphery of the disk. The distribution of nodes between core and periphery is controlled by the dimensionless density of the nodes: in high-density networks the core dominates, while the low-density ones are dominated by the periphery.
The resulting overall in-degree distribution is a truncated power law with exponent -3, the width of the power-law region depends on the density, in the limit of low density the distribution becomes a true power law. Notably, the average in-degree of the network remains finite and equal to m in the thermodynamic limit.
We calculate additional structural properties of the network, such as the fraction of bidirectional links, and show how it can be regulated by introducing an additional temperature-like parameter governing the probability of link formation.
