Multiplex PageRank

Abstract

Many complex systems can be described as multiplex networks in which the same nodes can interact with one another in different layers, thus forming a set of interacting and co-evolving networks. Examples of such multiplex systems are social networks where people are involved in different types of relationships and interact through various forms of communication media. The ranking of nodes in multiplex networks is one of the most pressing and challenging tasks that research on complex networks is currently facing. When pairs of nodes can be connected through multiple links and in multiple layers, the ranking of nodes should necessarily reflect the importance of nodes in one layer as well as their importance in other interdependent layers. In this paper, we draw on the idea of biased random walks to define the Multiplex PageRank centrality measure in which the effects of the interplay between networks on the centrality of nodes are directly taken into account. In particular, depending on the intensity of the interaction between layers, we define the Additive, Multiplicative, Combined, and Neutral versions of Multiplex PageRank, and show how each version reflects the extent to which the importance of a node in one layer affects the importance the node can gain in another layer. We discuss these measures and apply them to an online multiplex social network. Findings indicate that taking the multiplex nature of the network into account helps uncover the emergence of rankings of nodes that differ from the rankings obtained from one single layer. Results provide support in favor of the salience of multiplex centrality measures, like Multiplex PageRank, for assessing the prominence of nodes embedded in multiple interacting networks, and for shedding a new light on structural properties that would otherwise remain undetected if each of the interacting networks were analyzed in isolation.

Figure 1. Data versus theory for the Additive, Multiplicative, and Combined versions of PageRank.

In each of the three panels, the PageRank of the data is plotted against the corresponding value obtained through our theoretical approximation. Multiplex PageRank was evaluated using an iterative procedure with the standard values . The accuracy of the algorithm was set at .

Figure 2. Sketch of the multiplex online social network in which users communicate by exchanging instant messages and by posting messages to a forum.

Figure 3. The Additive, Multiplicative, Combined, and Neutral users’ Multiplex PageRanks plotted against the mean field expectation (solid line) for the IM-forum multiplex network dataset.

The damping factors used for the IM and forum data are .

Figure 4. The time evolution of the values of Additive, Multiplicative, Combined, and Neutral Multiplex PageRank for the top-ranked users.

The damping factors used for the IM and forum network data are . Each time step reflects the cumulative interactions in a three-week time window.

Figure 5. The estimated ranks of users according to the sum and product of their in-degrees and degrees plotted against the values of their Additive and Multiplicative Multiplex PageRank, respectively.

In the figure and . Note that the node with rank is the most important node of the network, and therefore the Additive and Multiplicative Multiplex PageRanks of the most important nodes of the online social network are correlated, respectively, with a linear combination or the product of the users’ in-degrees and degrees.

Figure 6. The distribution of the Additive, Multiplicative, Combined, and Neutral versions of Multiplex PageRank for users in the IM-forum multiplex network dataset.

The damping factors used for the IM and forum data are .