Determining the dimensionality of complex networks using hyperbolic geometry

A new method allows determining the dimensionality of complex networks using hyperbolic geometry.

Reducing redundant information to find simplifying patterns in complex data sets and networks is a scientific challenge in many areas of knowledge. Furthermore, detecting the dimensionality of the data is still a difficult problem to solve.

Researchers have devised a method to infer the dimensionality of complex networks by applying hyperbolic geometry, which captures the complexity of real-world relational structures in widely diverse domains.

The team is made up of M. Ángeles Serrano and Marián Boguñá, from the Faculty of Physics and the Institute of Complex Systems of the University of Barcelona (UB), and Pedro Almargo, from the Higher Technical School of Computer Engineering of the University of Seville, in Spain. The research provides a multidimensional hyperbolic model of complex networks that faithfully reproduces their connectivity, with ultra-low dimensionality and customizable for each specific network. This makes it possible to better characterize its structure —for example, at the community level— and improve its predictive capacity.

The study reveals unexpected regularities, such as the extremely low dimensions of molecular networks associated with biological tissues; the slightly higher dimensionality required by social networks and the Internet and the discovery that brain connectomes are close to the three dimensions of their automatic organization.

The team infers the dimensionality of the hyperbolic space underlying real networks from properties that relate to the dimension of their geometry. (Image: UB)

Hyperbolic versus Euclidean geometry

The intrinsic geometry of data sets or complex networks is not obvious, a fact that becomes an obstacle to determine the dimensionality of real networks. Another challenge is that the definition of distance has to be established according to its relational and connectivity structure, and this also requires sophisticated models.

Now, the new approach has as reference the geometry of complex networks, and more specifically, the configurational geometric model or SD model. “This model, which we have developed in previous works, describes the structure of complex networks based on fundamental principles”, explains Professor M. Ángeles, ICREA researcher at the UB’s Department of Condensed Matter Physics.

«More specifically -he continues-, the model postulates a law of interconnection of the elements of the network (or nodes) that is of gravitational type, so that the closest nodes in a space of similarity -of spherical geometry in D dimensions- and with more popularity—an extra dimension corresponding to the importance of the node—they are more likely to make connections

In the study, the similarity and popularity variables are combined to give rise to the hyperbolic geometry of the model, which emerges as the natural geometry that represents the hierarchical architecture of complex networks.

In previous work, the team had applied the simplest version of the SD model in one dimension—the S1 model—to explain many typical features of real-world networks: the small-world property (the six degrees of separation), the distributions heterogeneous number of neighbors per node, and high levels of transitive relationships (triangle connections that can be illustrated with the phrase my friend’s friend is also my friend).

“In addition, the application of statistical inference techniques allows us to obtain maps of real networks in the hyperbolic plan that are consistent with the established model,” highlights the researcher. “Beyond visualization, these representations have been used in a multitude of tasks, including efficient navigation methods, detection of self-similarity patterns, detection of communities of strongly interacting nodes, and implementation of a renormalization procedure. networks that reveals hidden symmetries in the multiscalar organization of complex networks and allows the production of replicas of the network at a reduced or increased scale”.

Now the team infers the dimensionality of the hyperbolic space underlying real networks from properties that relate to the dimension of their geometry. In particular, the work measures the statistics of higher order cycles (triangles, squares, pentagons) associated with the connections.

A methodology applicable to all complex networks

In computer science, applied techniques are based on data that usually make similarity distance definitions between their elements, an approach that involves the construction of graphs that are mapped onto a latent space of Euclidean features.

“Our estimates of the dimensionality of complex networks fall well short of our estimates based on Euclidean space, since hyperbolic space is more suitable for representing the hierarchical structure of real complex networks. For example, the Internet only requires D = 7 dimensions to be mapped into the hyperbolic space of our model, while this name is multiplied by six and scaled to D = 47 in one of the most recent techniques using Euclidean space.” Professor Marián Boguñá.

Furthermore, techniques for mapping complex data often assume a latent space, with a predetermined name of dimensions, or implement heuristics to find a suitable value. Thus, the new method is based on a model that does not require the spatial mapping of the network to determine the dimension of its geometry.

In the field of network science, many methodologies use the shortest distances to study the connectivity structure of the network (shortest paths) as a metric space. However, these distances are strongly affected by the small-world property and do not provide a wide range of distance values.

“Our model uses a completely different definition of distance based on an underlying hyperbolic space, and we don’t need to map the network. Our methodology is applicable to any real network or data series with a complex structure and a size that is typically thousands or tens of thousands of nodes but that can reach hundreds of thousands in a reasonable computing time”, emphasizes M. Ángeles Highlander.

What is the real dimensionality of social networks and the Internet?

The dimension of social networks and the Internet is higher (between 6 and 9) compared to networks in other areas, according to the conclusions of the study. However, it is still very low —6 or 7 times less— compared to that obtained by other methods. This reflects the fact that the interactions in these systems are more complex and determined by a greater variety of factors.

On the other hand, friendship-based social networks are at the forefront of the dimensionality ranking. “It is an unexpected result, since in principle it could be thought that friendship is a freer type of affective relationship, but our results are linked to the fact that homophily in human interactions is determined by a multitude of sociological factors such as age. , sex, social class, beliefs, attitudes or interests”, points out M. Ángeles Serrano.

In the case of the Internet, even though it is a technological network, its greater dimensionality is a reflection of the fact that for an autonomous system, connecting does not mean only accessing the system, as might be thought a priori. Rather, many different factors influence the formation of these connections, and as a consequence, a variety of other relationships may be present (eg, provider-customer, peer-to-peer, exchange-based peering, etc.). .).

“What is really surprising, both for social networks and for the Internet, is that our theoretical framework – which does not use any annotation about the connections beyond its existence – is able to capture this multidimensional reality that is not explicit in our data. », concludes the team, which is currently working on the construction of hyperbolic multidimensional maps of complex networks that are consistent with the theoretical framework established by the SD model.

The study is entitled “Detecting the ultra low dimensionality of real networks”. And it has been published in the academic journal Nature Communications. (Source: UB)