Introduction

Despite recent advances [1]–[4] in the analysis of complex networks, a number of areas of investigation concerned with the description, prediction, and control of the dynamics of a variety of systems, including weather networks [5], social networks [6], and the brain [7], still remain largely unexplored. A large number of these systems cannot be properly understood unless they are regarded as components of higher-level systems in which various networks are connected with one another through a complex pattern of interdependencies [6], [8]–[10]. These higher-level systems can thus be seen as networks in which the interacting nodes are networks themselves that are characterized by their own structure and function, and co-evolve over time according to various patterns. Examples of such networks of networks include multimodal transportation networks, social networks, climatic systems, economic markets, energy–supply networks, and the human brain. For instance, the same individuals, groups and organizations can play different roles within a social relationship or can be linked through different types of social relationships (e.g., family relationships, acquaintanceship, friendship, and professional collaboration) [11]–[15], can have different affiliations [16], [17], and can communicate with one another using different technologies, such as mobile phone, chat, e-mail, or video conferences [18], [19]. Each of these roles, relationships, affiliations, and communication technologies can in turn be associated with a different social network in which links between nodes refer to a distinct form of social interaction between the connected nodes. The same people, groups or organizations that interact in many different ways can thus be represented as the nodes of multiple co-evolving social networks that are themselves connected with one another as the various forms of social interaction affect one another over time [20]–[23]. Despite the ubiquity of these co-evolving and interconnected forms of interaction, so far network scientists have focused primarily on network datasets that contain only one type of social relation, thus neglecting the complexity of the connections between the various networks in which the same people interact. To uncover the nature and full breadth of social interaction, a special emphasis should be placed precisely on the structure and dynamics of the network of interacting social networks.

The system in which the same nodes belong to multiple interacting and co-evolving networks is typically referred to as a multiplex network or multigraph [24], [25]. In recent literature, there has been an upsurge of interest in multiplex networks. In particular, scholars have concentrated on the structural properties [6], [9], [10], [23], [26] and the antecedents [27], [28] of these networks, have shed light on diffusion processes [29], [30], cooperation [31], [32], exchange relations [33], [34], percolation phase transitions [8], [35], cascades [36], epidemic spreading [37], and election processes [38] occurring on them, and have developed modeling frameworks [39]–[41] and game-theoretic perspectives [32]. Among the structural properties of multiplex networks that scholars have only recently begun to address [42], [43], a crucial role is played by the centrality of nodes. In a multiplex network, the importance of a node depends on the connectivity patterns within and across the different layers of the network. For univariate networks in which no more than one link can connect the same pairs of nodes, a number of measures are available for assessing the importance of nodes. Over recent years these measures have become increasingly popular and salient for a variety of empirical domains. Among these measures, in this paper we concentrate our attention on PageRank, a centrality measure that has been successfully used not only for ranking web pages [44], but also for ranking scientists in citation networks [45] or species in food webs [46]. While PageRank was originally proposed as a centrality measure for univariate networks [44], its extension to multiplex networks remains largely unexplored. In particular, when the same pairs of nodes can be connected through multiple links co-evolving in multiple layers, a non-trivial problem is concerned with how to extend PageRank so as to capture the degree to which the ranking of nodes in one layer can affect, and be affected by, the ranking of the same nodes in other layers. This paper attempts to address this problem by proposing a generalization of PageRank to the case of multiplex networks.

To evaluate the relative popularity of a node in a network, PageRank centrality draws on the idea of a web surfer that visits different parts of the WWW at random. The random walker follows two strategies: the first is to jump to a node selected uniformly at random; the second is to jump, still randomly, to one of the walker’s neighbors. The popularity of a node is a function of the frequency with which the random walker visits the node. This frequency is then compared with the frequencies associated with all other nodes in the network. The ranking of nodes obtained according to these frequencies of being visited is precisely the ordering produced by the PageRank centrality measure, and reflects the relative popularity that each node has across the whole network.

To extend the PageRank centrality measure to the case of multiplex networks, we assume that the centrality a node has in one layer affects the centrality the node can obtain in another layer. This interplay between layers has a two-fold nature. First, the importance of a node in one layer may simply contribute to an increase in the node’s importance in another layer. Second, a node’s importance in one layer can amplify the node’s ability to derive benefits from the importance of other nodes that point to it in another layer. Alternatively, from the perspective of a biased random walk on complex networks, Multiplex PageRank can be described in terms of the bias that one layer exerts on the random jumps that a surfer makes in another layer [47], [48]. In this paper, we identify four versions of the Multiplex PageRank centrality measure, depending on how layers affect each other or, alternatively, exert a bias upon the random jump. First, if the bias lies in the jump the random walker makes to any other node in the network, we obtain a measure that we call Additive Multiplex PageRank. Second, if the bias is exerted upon the jump the walker makes to any of its neighboring nodes, we obtain the Multiplicative Multiplex PageRank. The third variant is motivated by the fact that it is possible to have a bias in both jumps. In this case, we obtain the Combined Multiplex PageRank. Finally, the Neutral Multiplex PageRank refers to the case in which there is no bias in either jump, and thus the measure reduces to PageRank based on one single layer. For uncorrelated networks, we show how these centrality measures are correlated with the structural properties of the networks.

To clarify the meaning of the four versions of Multiplex PageRank, we apply these measures to a multiplex network formed by the juxtaposition of two networks, and show that the centrality of a node in one network depends on the centrality of the same node in the other network. Our application is concerned with online communication and is based on a multiplex network in which the same users can interact by sending instant messages to one another and by posting messages to a forum. As users can send messages directly to one another and at the same time participate in discussion groups within a forum, they can be regarded as embedded in two related online social networks. Our results show that the Multiplicative Multiplex PageRank of users displays a broad distribution, and is thus able to capture the emergence of high-ranked nodes, unlike what can be obtained through the application of the PageRank centrality measure to a single network.

Results

Introduced as a centrality measure for assessing the “importance” of web pages, the PageRank of a node in a network with nodes is defined as [44](1)where are the elements of the adjacency matrix that are equal to one if node points to node and zero otherwise, , and is called the damping factor. PageRank can be interpreted as the stationary distribution of a random walk with additional random jumps. A random walker on site jumps to one of ’s out-neighbors with probability , and to any other site chosen uniformly at random with probability . The PageRank of a node is large to the extent that many other nodes point to it. The PageRank of a node is therefore expected to increase as a function of the node’s in-degree, and indeed in [49], [50] it was shown that, for uncorrelated networks, the PageRank of nodes can be approximated by their in-degree. If nodes in uncorrelated networks are grouped into classes depending on their extended degrees , then the average PageRank for nodes of degree-class is(2)where the symbol indicates the average over the nodes of the network.

PageRank was originally proposed for ranking web pages in response to text queries, and for this reason it was formalized as a centrality measure for directed networks [44]. It is, however, possible to extend the original definition to the case of undirected networks. For these networks, PageRank is(3)where and is the degree of node . For undirected networks, the average PageRank of a node with degree is given by

(4)

Compared to univariate networks, multiplex networks enable nodes to be connected with one another through more than one type of links, and as such offer a richer and more detailed backdrop against which the structural position of nodes can be assessed. The extension of PageRank to multiplex networks is therefore expected to shed light on novel ways for measuring the importance of nodes that capture their embeddedness in multiple interrelated relations. A ranking of nodes can thus be obtained that is likely to differ from the one originating simply from the position of nodes in one single network.

Here we offer a generalization and extension of the PageRank measure that can be applied to any multiplex network dataset. The assumption underlying our proposed measure is that the centrality of a node in one network can be affected by the centrality of the same node in another network. For the sake of simplicity, we consider the case in which the multiplex network is organized into two layers: network A and network B. Our analysis can easily be generalized to multiplex networks with more than two layers (See Materials and Methods). We indicate with the elements of the adjacency matrix of network A, and with the elements of the adjacency matrix of network B. For network A, we evaluate PageRank using Eq. (1) with the parameter . We then express the Multiplex PageRank centrality of the nodes in network B with respect to PageRank .

Formally, we define the Multiplex PageRank centrality of node as(5)where , is the Kronecker delta, is small enough to guarantee that the relation can be satisfied, and the exponents and are both greater than or equal to zero. The first term in Eq. (5) refers to the contribution to node ’s centrality that derives from the centrality of the nodes pointing to in network B. Like with the ordinary PageRank measure, this contribution is inversely proportional to the out-degree of node ’s in-neighbors. However, unlike the ordinary measure, Eq. (5) enables this contribution to be also affected by the centrality that both node and its in-neighbors in network B have in network A. This interplay between the two networks has a two-fold effect on a node’s centrality. First, the extent to which node can derive some advantage from the centrality of its in-neighbors in network B becomes more significant as the centrality of in network A becomes larger. The more prominent a node is in one layer, the more likely it is that the node can attract and gain benefit from other important nodes in another layer. Second, the contribution of each in-neighbor to ’s centrality in network B is discounted by dividing ’s centrality by the sum of the centralities that ’s out-neighbors in network B have in network A. In other words, the benefits node can derive from the centrality of any in-neighbor in network B are diluted to the extent that in network B points to many other nodes that are associated with high centrality in network A. An important node in one layer can attract important nodes in a different layer, but the benefit that can be gained in so doing are mitigated if there are many other nodes that have a similar capacity of attraction.

The second term in Eq. (5) reflects the contribution to node ’s centrality in network B that derives from ’s centrality in network A. By adding this second term, nodes that are not able to attract important neighbors in network B, can still derive some advantage simply by being central in network A. In the extreme case, a node with a zero in-degree in network B can still be associated with a non-zero value of centrality if the node has a non-zero centrality in network A. The assumption underlying this component of centrality is that the importance of a node in one layer is positively affected by the importance that the same node has in another layer, regardless of the node’s capacity to attract other important nodes in the former layer.

Alternatively, Multiplex PageRank can also be regarded as the stationary distribution of a random walk with additional biased jumps. With probability , a random walker on site jumps to site , one of ’s out–neighbors selected with probability proportional to , and with probability jumps to site chosen with probability proportional to .

In what follows, we identify four important limiting cases of the Multiplex PageRank measure:

• Additive Multiplex PageRank (, ):(6)where . This refers to the case in which the effect of network A on network B is exerted simply by “adding” some value to the centrality the nodes have in network B in proportion to the centrality they have in network A. Here the interplay between networks does not imply that the importance a node has in one network affects the node’s ability to derive benefits from important nodes in another network. Simply, being central in network A enables a node to gain more centrality in network B, regardless of the node’s capacity to attract important others in network B. Recast in terms of a random walk, this version of Multiplex PageRank refers to the case of a biased random walk, where the bias lies in the random jump to any node in network B. In particular, nodes with high PageRank in network A are preferred over other nodes with low PageRank in the same network as the destination of the random jumps that the walker makes in network B. A similar version of this PageRank measure, in which the random jumps are biased according to some predetermined distribution called “personalized vector”, has already been suggested in the computer science literature [51]. In qualitative agreement with this version, here we propose to regard a node’s PageRank in one layer as the node’s “personalized vector” in another layer.
• Multiplicative Multiplex PageRank (, ):(7)where . This refers to the case in which the effect of network A on network B lies in “multiplying” the benefits that a node gains from the importance of its in-neighbors in network B by a factor that is proportional to the node’s importance in network A. Thus, all benefits that can be obtained by being central in network A are contingent upon the connections that a node receives from important nodes in network B. The more important a node is in network A, the more value the node can extract from the connections received from important others in network B. Unlike the Additive version, the Multiplicative Multiplex PageRank does not enable a node to derive any added benefit in network B by simply being important in network A, regardless of the importance of the node’s in-neighbors in network B. Alternatively, this version of the measure also refers to the case of a biased random walk, where the bias lies in the walker’s choice of the out–neighbor as the destination of the jump. In particular, neighbors with high PageRank in network A are preferred over other neighbors with low PageRank in the same network.
• Combined Multiplex PageRank ():(8)where . This refers to the case in which the effect of network A on network B lies in “combining” the additive and multiplicative benefits a node in network B can gain by being central in network A. In this case, a node’s high centrality in network A can boost its centrality in network B both in itself and at the same time by amplifying the node’s ability to derive centrality from other important nodes. Alternatively, this version of Multiplex PageRank refers to the case in which both the destination of the random jump and the selection of the random walker’s out-neighbor in network B are biased in that they favor nodes with high PageRank in network A over nodes with low PageRank in the same network.
• Neutral Multiplex PageRank ():(9)where . This refers to the case in which there is no effect of network A upon network B, and thus Multiplex PageRank reduces to the PageRank based simply on network B in isolation.

Clearly these limiting cases can be generalized so as to be applied also to a multiplex network that combines two undirected networks or a directed network and an undirected one. Moreover, the above definitions can be further generalized so as to accommodate cases in which the rankings are obtained using different centrality measures, such as the eigenvector centrality.

Following [49], [50], we performed a mean-field calculation of the average Multiplex PageRank of a node with degree in network B and PageRank in network A. We define in the following way(10)where is the probability that a node has degree in network B and PageRank in network A. In particular, performing a mean-field calculation (see Materials and Methods) valid for an uncorrelated network B, we obtain

(11)

To verify the validity of Multiplex PageRank, we generated a duplex network with nodes and links in each layer. In both layers, the in- and out-degrees decay as a power law , where , and , . The dependence of the Additive, Multiplicative, and Combined versions of PageRank upon in-degree is shown in Fig. 1. For small values of PageRank, the deviation from the diagonal is due to large fluctuations of PageRank in correspondence of small values of in-degree, as was also observed by Fortunato et al. [50].

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

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 .

https://doi.org/10.1371/journal.pone.0078293.g001

Discussion

We apply the Multiplex PageRank measure to the multiplex network created from an online community at the University of California, Irvine [52]. The multiplex network includes two layers. The first layer corresponds to a directed instant messaging (IM) network in which a directed link is established from one user to another if the former sends one or more online instant messages to the latter. The second layer is a bipartite network in which a link is established between a user and a discussion group of a forum when the former posts a message to the latter. While the IM network dataset covers the period from April 19 to October 26, 2004, the forum became active at a later time when users were already communicating through instant messages. The bipartite network thus covers a more restricted period than the IM network, from May 14 to October 26, 2004. The two networks also differ in the number of users: the total number of active users recorded for the IM network is , of whom only posted at least one message in the forum. Moreover, users that were active in the forum created thematic groups, each aimed at the discussion of a specific topic.

The analysis of the multiplex network covers the restricted observation period beginning on June 4, 2004, when both networks were operational and exhibited a fairy stable pattern of activity. At any specific day, and with a daily frequency, we constructed the instantaneous cumulative networks reflecting all the social interactions that took place in the three weeks’ period ending on that day. Measurements thus create a time series with sample networks starting on June 25, 2004. The multiplex network can be represented by the juxtaposition of the two time-varying adjacency matrices and that describe the IM network and the one-mode projection of the bipartite forum network, respectively (see Fig. 2). In particular, the adjacency matrix describes directed links between users, i.e. if user sent at least one message to user in a given time window. For the forum network, the adjacency matrix describes an undirected and unweighted network between the users of the forum, where if both user and user posted at least one message to a common discussion group in a given time window.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

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

https://doi.org/10.1371/journal.pone.0078293.g002

The application of Multiplex PageRank to online communication is motivated by the fact that users can enhance their ranking by engaging in multiple and interrelated ways of communication. In our specific case, users’ prominence in the IM network (A) is likely to have an impact upon the prominence they gain by communicating and interacting in the forum network (B). To fully capture this intertwined nature of users’ prominence, we begin by calculating each user’s PageRank based on the IM network. The Multiplex PageRank of user in the forum is then obtained by expressing the PageRank user has in the forum as a function of the user’s PageRank x_i based on the IM network. Formally, the Multiplex PageRank of user in the forum at time is(12)where is the number of active users in the forum at time , denotes the average of based only on the nodes that belong to network B at time , and . In the above formula, the PageRank x_i of node in the IM network at time is given by(13)with . For the IM-forum multiplex network, we compared the values of Multiplex PageRank with the theoretical expectations obtained in the case of an uncorrelated network. We found a very good agreement between the two sets of values (see Fig. 3).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

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 .

https://doi.org/10.1371/journal.pone.0078293.g003

A crucial issue affecting a large number of applications, ranging from the online sale of books to usage of Twitter tags, that rely on measures for ranking items is concerned with the stability of the rankings over time [53]. To address this problem, here we investigate the stability of the top-ranked users in the forum, and compare the rankings obtained using the different proposed versions of Multiplex PageRank.

In order to evaluate the stability of rankings in our dataset, we select the top five users with the highest Multiplex PageRank at the end of the whole observation period (), and track their evolution over time. In Fig. 4 we plot the time evolution of the values of PageRank of the five users with the highest Additive, Multiplicative, Combined, and Neutral PageRanks. Users are ranked in decreasing order, from top to bottom. The figure indicates that the top five users with the highest values of Multiplicative Multiplex PageRank and Combined Multiplex PageRank are the same, and the top five users with the highest values of Additive and Neutral Multiplex PageRank are the same (with the exception of user 297 and user 511; note that user 297 has extremely high PageRank in the IM network). The Neutral Multiplex PageRank refers to the case in which and in Eq. (5), and thus produces a ranking of users that coincides with the one obtained by taking into consideration only users’ position in the forum.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

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.

https://doi.org/10.1371/journal.pone.0078293.g004

When the importance of the users in the forum is adjusted to also reflect their position in the IM network simply by adding a bias in the random jump to any node, as occurs with the Additive Multiplex PageRank, the identity of the top five users in the resulting ranking does not change significantly. On the contrary, the introduction of a bias in the random walker’s choice of the out-neighbor as the destination of the jump, as occurs with the Multiplicative Multiplex PageRank, is responsible for a substantial change in the ranking of users. In particular, the emergence of new top-ranked users when the Multiplicative Multiplex PageRank is adopted suggests that there are synergies between the activities of these users in the IM and forum networks. The way they communicate and rise to prominence in one network affects how they communicate and rise to prominence in the other network. Thus, taking into account the multiplex nature of the dataset helps unveil these synergies and the multi-faceted nature of users’ prominence that would otherwise remain undetected if only one layer were investigated. Moreover, Fig. 4 shows that the Combined Multiplex PageRank, by adding a bias both in the random jump to any node and in the walker’s choice of the out-neighbor, does not produce any substantial change in the ordering of the top-ranked users with respect to the ranking that is obtained with the Multiplicative Multiplex PageRank.

In most applications, the use of PageRank for assessing the importance of nodes is aimed primarily at producing a ranking of nodes rather than associate each of them with a specific value of centrality. As in a variety of networks nodes’ PageRank is closely related to their in-degree, especially for nodes with high in-degree, it has become common practice to use in-degree as a proxy for PageRank. In the case of the multiplex online social network, drawing on our theoretical framework, we tested the hypothesis that the Additive Multiplex PageRank correlates with a linear combination of nodes’ in-degree in network A and their degree in network B, while the Multiplicative PageRank correlates with the product between nodes’ in-degree in network A and their degree in network B. Fig. 5 does indeed provide support in favor of our hypothesis. Findings thus suggest that the Additive and Multiplicative versions of PageRank can be well approximated by the following two simple measures of centrality for multiplex networks: respectively, the linear combination of nodes’ degrees in the different layers, and the multiplication of nodes’ degrees in the different layers.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

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.

https://doi.org/10.1371/journal.pone.0078293.g005

Finally, we found that in our dataset the distribution of Multiplex PageRank is broad, especially the one of the Multiplicative and Combined versions of Multiplex PageRank (See Figure 6), as is expected in the case of multiplex networks with positive correlations between degrees of nodes in the different layers.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

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 .

https://doi.org/10.1371/journal.pone.0078293.g006

In conclusion, in this paper we introduced Multiplex PageRank, namely a centrality measure that can be used to identify and rank important nodes in multiplex networks. In particular, we defined four versions of this measure: the Additive, Multiplicative, Combined, and Neutral Multiplex PageRank. We then analyzed how these measures correlate with the degree of the nodes in the different layers, both at the mean-field level and using data on an online social network. The empirical application of these measures to our dataset indicated that taking into consideration the multiplex nature of social interaction helps uncover the emergence of rankings of nodes and of structural properties that would otherwise remain undetected if only univariate single networks were investigated.

Materials and Methods

The dataset used in this paper consists of communication records of anonymized users that were randomly assigned an identification number. This ensures privacy protection and compliance with ethical guidelines. The dataset can be obtained upon request from Pietro Panzarasa. The use of the dataset is free, provided the appropriate credit is given to the authors and a reference is made to this paper and to paper [52].