Source-linked AI summary
Multiplex PageRank
Arda Halu, Raul J. Mondragon, Pietro Panzarasa, Ginestra Bianconi
TL;DR
Multiplex networks require node rankings that account for importance across interdependent layers, rather than evaluating each network in isolation. The paper introduces four biased-random-walk versions of Multiplex PageRank and applies them to an online social network. The application shows that multiplex analysis can produce different rankings and reveal structural properties not detected in single-layer networks.
Problem
Node ranking in multiplex networks must reflect importance across multiple interdependent layers, whereas network analysis has often focused on single-layer relations.
Method
The paper defines Additive, Multiplicative, Combined, and Neutral Multiplex PageRank variants using biased random walks to model cross-layer effects on centrality.
Results
The online social-network application shows that Multiplicative Multiplex PageRank substantially changes rankings, while Additive Multiplex PageRank changes them little relative to Neutral PageRank.
Takeaways & Limitations
Accounting for multiplex social interaction uncovers node rankings and structural properties that remain undetected when interacting networks are analyzed separately.
Takeaways & Limitations
The multilayer extension generally allows exponents β and γ to depend on layers, although the analysis uses exponents that do not depend on ℓ.
Abstract
from arXiv · showhide
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.
Introduction
Complex systems often comprise multiple interacting networks over the same nodes, but network analysis has largely treated single relation types separately. The paper extends PageRank with biased random walks so node importance can reflect cross-layer interplay, and applies four variants to online communication networks.
- Multiplex systems represent the same nodes across multiple interacting and co-evolving networks with distinct relationships or communication media.
- Network scientists have primarily analyzed datasets containing one social relation, neglecting interdependencies among the networks in which the same people interact.
- PageRank ranks nodes by their visitation frequency under random jumps and neighbor-following steps by a random walker.
- Multiplex PageRank assumes that a node’s centrality in one layer can increase or amplify its centrality in another layer.
- The Additive, Multiplicative, Combined, and Neutral variants place cross-layer bias in random jumps, neighbor choices, both, or neither, respectively.
- An online multiplex network application examines users interacting through instant messages and forum discussion groups.
Results
The paper generalizes PageRank to multiplex networks by allowing a node’s centrality in one layer to affect its centrality in another. Additive, Multiplicative, Combined, and Neutral variants capture different interlayer effects, with theoretical analysis and synthetic-network validation supporting the framework.
- PageRank foundation: PageRank ranks nodes through the stationary visitation frequency of a random walker that combines random jumps with neighbor-following.The walker jumps uniformly to any node or randomly to one of its neighbors.
- Multiplex PageRank: Multiplex PageRank expresses centrality in network B with respect to PageRank in network A, and can be generalized beyond two layers.The framework uses adjacency matrices for networks A and B and is stated to apply to any multiplex network dataset.
- Interlayer effects: A node central in network A can gain centrality in network B even without important incoming neighbors, including when its network-B in-degree is zero.The additive contribution from network A provides a direct source of centrality, while the multiplicative effect changes the value obtained from important neighbors.
- Four variants: Interlayer coupling can add centrality directly, amplify benefits from important in-neighbors, combine both effects, or be absent in the Neutral version.The Additive, Multiplicative, Combined, and Neutral variants correspond respectively to bias in random jumps, neighbor selection, both, or neither.
- Theoretical approximation: Mean-field analysis derives average Multiplex PageRank for nodes grouped by network-B degree and network-A PageRank in an uncorrelated network.The calculation is based on the joint probability of degree in network B and PageRank in network A.
- Validation: In a synthetic duplex network, deviations from the theoretical diagonal at small PageRank values were attributed to fluctuations associated with small in-degree.The evaluation used a duplex network with 10^7 nodes, while Figure 1 compares data with theoretical approximations for three variants.
Discussion
The study applies four Multiplex PageRank variants to an IM–forum network and finds that multiplex interactions affect rankings, approximations, and temporal stability. Multiplicative and Combined variants most strongly alter top-user rankings, while multiplex degree relationships explain Additive and Multiplicative scores.
- Online multiplex network: The dataset combines a directed instant-messaging layer with a user–discussion-group forum layer, covering 1,899 IM users, 899 forum posters, and 552 thematic groups.The IM data span April 19–October 26, 2004, while forum data span May 14–October 26, 2004.
- Temporal analysis: The analysis constructs 124 daily cumulative multiplex networks from three-week interaction windows during the period when both networks were operational.Measurements begin on June 25, 2004, after the restricted observation period began on June 4.
- Model assessment: The four variants are compared with mean-field expectations, with the empirical Multiplex PageRanks showing very good agreement for the IM–forum dataset.The damping factors for both layers are αA = αB = 0.85.
- Ranking stability: Multiplicative and Combined PageRank produce the same top five users, whereas Additive and Neutral produce the same top five except for users 297 and 511.Neutral PageRank coincides with ranking users by their forum position alone.
- Ranking differences: Biasing neighbor selection substantially changes rankings, unlike additive bias in random jumps, revealing synergies between users’ IM and forum activities.The authors interpret these changes as evidence that prominence in one network affects prominence in the other.
- Degree relationships: Additive and Multiplicative PageRank are well approximated by, respectively, linear combinations and products of node degrees across layers.For the most important nodes, Additive and Multiplicative scores correlate with the specified cross-layer degree combinations.
- Distributional findings: The Multiplex PageRank distribution is broad, especially for the Multiplicative and Combined variants, consistent with positive cross-layer degree correlations in this dataset.
- Implications: The empirical application indicates that multiplex analysis uncovers rankings and structural properties that single-layer analysis would leave undetected.
Materials and Methods
The methods define iterative and mean-field procedures for computing Multiplex PageRank across interacting network layers. The framework begins with single-layer PageRank and recursively incorporates information from additional layers, with assumptions about degree and PageRank correlations.
- The dataset contains anonymized communication records, with users assigned random identification numbers for privacy protection.
- Multiplex PageRank values are calculated iteratively, updating the vector at each time step through a recursive equation.
- Nodes are grouped into classes sharing the same in-degree, out-degree, and PageRank, enabling average PageRank calculations by degree class.
- The method uses mean-field approximations and uncorrelated-network assumptions to estimate neighbor and predecessor contributions.
- The duplex formulation extends to M-layer multiplex networks by starting with single-layer PageRank and recursively incorporating the structure of subsequent layers.