Can the PageRank centrality be manipulated to obtain any desired ranking?

The significance of the PageRank algorithm in shaping the modern Internet cannot be overstated, and its complex network theory foundations continue to be a subject of research. In this article, we carry out a systematic study of the structural and parametric controllability of PageRank's outcomes, translating a spectral graph theory problem into a geometric one, where a natural characterization of its rankings emerges. Furthermore, we show that the change of perspective employed can be applied to the biplex PageRank proposal, performing numerical computations on both real and synthetic network datasets to compare centrality measures used.

Distances in Higher-Order Networks and the Metric Structure of Hypergraphs.

We explore the metric structure of networks with higher-order interactions and introduce a novel definition of distance for hypergraphs that extends the classic methods reported in the literature. The new metric incorporates two critical factors: (1) the inter-node distance within each hyperedge, and (2) the distance between hyperedges in the network. As such, it involves the computation of distances in a weighted line graph of the hypergraph. The approach is illustrated with several ad hoc synthetic hypergraphs, where the structural information unveiled by the novel metric is highlighted. Moreover, the method's performance and effectiveness are shown through computations on large real-world hypergraphs, which indeed reveal new insights into the structural features of networks beyond pairwise interactions. Namely, using the new distance measure, we generalize the definitions of efficiency, closeness and betweenness centrality for the case of hypergraphs. Comparing the values of these generalized measures with their analogs calculated for the hypergraph clique projections, we show that our measures provide significantly different assessments on the characteristics (and roles) of the nodes from the information-transferability point of view. The difference is brighter for hypergraphs in which hyperedges of large sizes are frequent, and nodes relating to these hyperedges are rarely connected by other hyperedges of smaller sizes.

A comprehensive approach for discrete resilience of complex networks.

The research and use of the term resilience in various types of technological, physiological, and socioeconomic systems has become very topical in recent years since this term has been applied in different fields with different meanings and connotations. One of the most common meanings of resilience is related to a positive idea that addresses recovery from failures. This study proposes to establish a theoretical and mathematical framework for discrete resilience that allows different systems to be quantitatively compared from this point of view. Also, a definition and a local view of the concept of resilience applicable to different characteristic measures in the field of complex networks is provided. Furthermore, several computational experiments are presented on the values of this new parameter in different types of synthetic and real-world networks, supplying a new set of conceptual tools for network science research.

Parametric controllability of the personalized PageRank: Classic model vs biplex approach.

Measures of centrality in networks defined by means of matrix algebra, like PageRank-type centralities, have been used for over 70 years. Recently, new extensions of PageRank have been formulated and may include a personalization (or teleportation) vector. It is accepted that one of the key issues for any centrality measure formulation is to what extent someone can control its variability. In this paper, we compare the limits of variability of two centrality measures for complex networks that we call classic PageRank (PR) and biplex approach PageRank (BPR). Both centrality measures depend on the so-called damping parameterα that controls the quantity of teleportation. Our first result is that the intersection of the intervals of variation of both centrality measures is always a nonempty set. Our second result is that when α is lower that 0.48 (and, therefore, the ranking is highly affected by teleportation effects) then the upper limits of PR are more controllable than the upper limits of BPR; on the contrary, when α is greater than 0.5 (and we recall that the usual PageRank algorithm uses the value 0.85), then the upper limits of PR are less controllable than the upper limits of BPR, provided certain mild assumptions on the local structure of the graph. Regarding the lower limits of variability, we give a result for small values of α. We illustrate the results with some analytical networks and also with a real Facebook network.

On the edges' PageRank and line graphs.

Two different approaches on a directed (and possibly weighted) network G are considered in order to define the PageRank of each edge of G with the focus on its applications. It is shown that both approaches are equivalent, even though it is clear that one approach has clear computational advantages over the other. The usefulness of this concept in the context of applications is illustrated by means of some examples within the area of cybersecurity and some simulations and examples within the scope of subway networks.

A biplex approach to PageRank centrality: From classic to multiplex networks.

In this paper, we present a new view of the PageRank algorithm inspired by multiplex networks. This new approach allows to introduce a new centrality measure for classic complex networks and a new proposal to extend the usual PageRank algorithm to multiplex networks. We give some analytical relations between these new approaches and the classic PageRank centrality measure, and we illustrate the new parameters presented by computing them on real underground networks.

Introduction to Focus Issue: Complex Dynamics in Networks, Multilayered Structures and Systems.

In the last years, network scientists have directed their interest to the multi-layer character of real-world systems, and explicitly considered the structural and dynamical organization of graphs made of diverse layers between its constituents. Most complex systems include multiple subsystems and layers of connectivity and, in many cases, the interdependent components of systems interact through many different channels. Such a new perspective is indeed found to be the adequate representation for a wealth of features exhibited by networked systems in the real world. The contributions presented in this Focus Issue cover, from different points of view, the many achievements and still open questions in the field of multi-layer networks, such as: new frameworks and structures to represent and analyze heterogeneous complex systems, different aspects related to synchronization and centrality of complex networks, interplay between layers, and applications to logistic, biological, social, and technological fields.

Line graphs for a multiplex network.

It is well known that line graphs offer a good summary of the graphs properties, which make them easier to analyze and highlight the desired properties. We extend the concept of line graph to multiplex networks in order to analyze multi-plexed and multi-layered networked systems. As these structures are very rich, different approaches to this notion are required to capture a variety of situations. Some relationships between these approaches are established. Finally, by means of some simulations, the potential utility of this concept is illustrated.

Optimal distributions for multiplex logistic networks.

This paper presents some mathematical models for distribution of goods in logistic networks based on spectral analysis of complex networks. Given a steady distribution of a finished product, some numerical algorithms are presented for computing the weights in a multiplex logistic network that reach the equilibrium dynamics with high convergence rate. As an application, the logistic networks of Germany and Spain are analyzed in terms of their convergence rates.

Synchronization in dynamical networks with unconstrained structure switching.

We provide a rigorous solution to the problem of constructing a structural evolution for a network of coupled identical dynamical units that switches between specified topologies without constraints on their structure. The evolution of the structure is determined indirectly from a carefully built transformation of the eigenvector matrices of the coupling Laplacians, which are guaranteed to change smoothly in time. In turn, this allows one to extend the master stability function formalism, which can be used to assess the stability of a synchronized state. This approach is independent from the particular topologies that the network visits, and is not restricted to commuting structures. Also, it does not depend on the time scale of the evolution, which can be faster than, comparable to, or even secular with respect to the dynamics of the units.

Eigenvector centrality of nodes in multiplex networks.

We extend the concept of eigenvector centrality to multiplex networks, and introduce several alternative parameters that quantify the importance of nodes in a multi-layered networked system, including the definition of vectorial-type centralities. In addition, we rigorously show that, under reasonable conditions, such centrality measures exist and are unique. Computer experiments and simulations demonstrate that the proposed measures provide substantially different results when applied to the same multiplex structure, and highlight the non-trivial relationships between the different measures of centrality introduced.

Emergence of network features from multiplexity.

Many biological and man-made networked systems are characterized by the simultaneous presence of different sub-networks organized in separate layers, with links and nodes of qualitatively different types. While during the past few years theoretical studies have examined a variety of structural features of complex networks, the outstanding question is whether such features are characterizing all single layers, or rather emerge as a result of coarse-graining, i.e. when going from the multilayered to the aggregate network representation. Here we address this issue with the help of real data. We analyze the structural properties of an intrinsically multilayered real network, the European Air Transportation Multiplex Network in which each commercial airline defines a network layer. We examine how several structural measures evolve as layers are progressively merged together. In particular, we discuss how the topology of each layer affects the emergence of structural properties in the aggregate network.

A new method for comparing rankings through complex networks: model and analysis of competitiveness of major European soccer leagues.

In this paper, we show a new technique to analyze families of rankings. In particular, we focus on sports rankings and, more precisely, on soccer leagues. We consider that two teams compete when they change their relative positions in consecutive rankings. This allows to define a graph by linking teams that compete. We show how to use some structural properties of this competitivity graph to measure to what extend the teams in a league compete. These structural properties are the mean degree, the mean strength, and the clustering coefficient. We give a generalization of the Kendall's correlation coefficient to more than two rankings. We also show how to make a dynamic analysis of a league and how to compare different leagues. We apply this technique to analyze the four major European soccer leagues: Bundesliga, Italian Lega, Spanish Liga, and Premier League. We compare our results with the classical analysis of sport ranking based on measures of competitive balance.

Evolutionary games defined at the network mesoscale: the Public Goods game.

The evolutionary dynamics of the Public Goods game addresses the emergence of cooperation within groups of individuals. However, the Public Goods game on large populations of interconnected individuals has been usually modeled without any knowledge about their group structure. In this paper, by focusing on collaboration networks, we show that it is possible to include the mesoscopic information about the structure of the real groups by means of a bipartite graph. We compare the results with the projected (coauthor) and the original bipartite graphs and show that cooperation is enhanced by the mesoscopic structure contained. We conclude by analyzing the influence of the size of the groups in the evolutionary success of cooperation.

(Psi,p,q)-vulnerabilities: a unified approach to network robustness.

We define a new general framework, the family of (psi,p,q)-vulnerabilities, as a tool that produces many new vulnerability functions that measure the capacity of a network to maintain its functional performance under random damages or malicious attacks. This new framework comprises most of the vulnerability definitions appearing in the literature and allows to calculate some relationships between the different (psi,p,q)-vulnerabilities in terms of their function psi or their parameters p, q that improve several known results for the vulnerability functions. Some graphics of simulations are provided in order to show the sharpness of these relationships.

Multiscale vulnerability of complex networks.

We present a novel approach to quantify the vulnerability of a complex network, i.e., the capacity of a graph to maintain its functional performance under random damages or malicious attacks. The proposed measure represents a multiscale evaluation of vulnerability, and makes use of combined powers of the links' betweenness. We show that the proposed approach is able to properly describe some cases for which earlier measures of vulnerability fail. The relevant applications of our method for technological network design are outlined.