PaperlayerView exact revision on arXiv

Source-linked AI summary

Structural measures for multiplex networks

Federico Battiston, Vincenzo Nicosia, Vito Latora

arXiv:1308.3182v3physics.soc-phcs.SI

TL;DR

Single-layer aggregation can obscure the distinct relationships that shape complex systems, motivating a multiplex framework. The paper formalizes unweighted and weighted multiplexes, introduces structural measures across local and global levels, and validates them on Indonesian terrorist-network data, including evidence that trust strength is associated with ties in other layers.

  • Problem

    Aggregating different relationship types can lose multiplex structure, limiting analysis of how layers jointly shape node roles, clustering, and reachability.

  • Method

    The paper defines layer-aware metrics for unweighted and weighted multiplexes, covering node degree, edge overlap and reinforcement, clustering, transitivity, reachability, shortest paths, and centrality.

  • Results

    The measures are validated on a 78-person, four-layer Indonesian terrorist network, where trust strength is associated with communication, operations, and business links.

  • Takeaways & Limitations

    Multiplex analysis requires preserving layer-specific information because aggregated representations can miss structural features and genuine multiplex interdependence.

Abstract

from arXiv · show

Many real-world complex systems consist of a set of elementary units connected by relationships of different kinds. All such systems are better described in terms of multiplex networks, where the links at each layer represent a different type of interaction between the same set of nodes, rather than in terms of (single-layer) networks. In this paper we present a general framework to describe and study multiplex networks, whose links are either unweighted or weighted. In particular we propose a series of measures to characterize the multiplexicity of the systems in terms of: i) basic node and link properties such as the node degree, and the edge overlap and reinforcement, ii) local properties such as the clustering coefficient and the transitivity, iii) global properties related to the navigability of the multiplex across the different layers. The measures we introduce are validated on a genuine multiplex data set of Indonesian terrorists, where information among 78 individuals are recorded with respect to mutual trust, common operations, exchanged communications and business relationships.

I. INTRODUCTION

The paper argues that systems with multiple relationship types require multiplex-network descriptions rather than link aggregation. It introduces structural measures for multiplex networks and validates them on a four-layer terrorist-network dataset.

  • Motivation: Aggregating all relationship types into one graph can discard information about distinct interactions between the same units.The paper motivates retaining layer-specific relationships when characterizing complex systems.
  • Contribution: The framework provides metrics for degree distributions, edge overlap, clustering, spectral centrality, shortest paths, betweenness, and closeness.These measures address node participation, local structure, and multiplex efficiency.
  • Validation: The measures are tested on the Top Noordin Terrorist Network, containing trust, operations, communication, and business relations among 78 Indonesian terrorists.The dataset is modeled naturally as a four-layer multiplex.
  • Findings: In this dataset, the trust layer acts as a driver for communication and operations ties through relationships between trust strength and conditional link probabilities.The authors interpret the pattern as social reinforcement affecting edge formation and strengthening.

II. GENERAL FORMALISM

The formalism represents a multiplex as layer-specific adjacency matrices and vector-valued node properties, while also defining aggregated and overlapping representations for comparison. It extends the framework to weighted layers and shows why aggregation alone is insufficient for structural analysis.

  • Representation: A multiplex with N nodes and M unweighted layers is represented by a vector of layer adjacency matrices.Each layer is an undirected network, and the vector preserves which layer contains each tie.
  • Representation: The degree of each node is represented as a vector of layer-specific degrees, with capitalized quantities denoting sums over nodes or edges.This notation distinguishes node-level properties from aggregate layer or system properties.
  • Aggregated descriptions: The aggregated topological adjacency matrix joins node pairs connected in at least one layer but neglects multiple ties and tie types.It is useful as a comparison network but does not retain the full multiplex structure.
  • Limits of aggregation: Aggregated matrices lose layer-specific information needed to characterize degree, clustering, and reachability in multiplex networks.The paper therefore treats vectorial variables and explicit layer indices as necessary for preserving multiplex richness.
  • Overlap: Edge overlap counts how many layers connect a node pair, and the overlapping adjacency matrix records these counts as weighted single-layer edges.The overlap satisfies 0 ≤ o_ij ≤ M, but the matrix still omits the identity of each tie type.
  • Weighted layers: Weighted multiplexes assign positive link weights within layers and use weighted adjacency matrices, strengths, and weighted overlapping degrees to extend the same measures.The weighted framework parallels the unweighted construction.

III. THE MULTI-LAYER NETWORK OF INDONESIAN TERRORISTS

The case study models Indonesian terrorist relationships as a multiplex with trust, operations, communication, and business layers, including internal sub-layer structure and selected link weights. The paper reports both full-network and three-layer representations.

  • Dataset: The dataset records trust, operational, communication, and business relations among 78 Indonesian terrorists.Trust and operations each contain four sub-layers, while the initial representation uses M = 4 layers.
  • Dataset: Trust combines classmates, friendship, kinship, and soul-mates ties, while operations combines logistics, meetings, operations, and training ties.These sub-layers provide deeper structure within two of the four principal relationship types.
  • Weighted construction: Integer weights from 1 to 4 are assigned to trust and operational edges according to the number of corresponding sub-layers containing each connection.The analysis sometimes treats these layers as unweighted and uses their weights explicitly in Section V.
  • Network size: The full multiplex contains N = 78 nodes, K = 623 non-overlapping links, O = 911 overlapping links, and O_w = 1014 weighted overlapping links.These quantities summarize the network before restricting the main analysis to three layers.
  • Three-layer representation: For the trust, communication, and operations subset, the network has N = 78, K = 620, O = 896, and O_w = 999.The three-layer representation is visualized in Fig. 1, where node colors show layer participation and node size shows overlapping degree.

IV. BASIC NODE PROPERTIES

The paper characterizes node roles in multiplex networks by comparing connectivity across layers and combining overall connectivity with how evenly links are distributed. These measures reveal structural differences that aggregated networks can miss.

  • Degree across layers: Layer-specific degree sequences are weakly correlated, so nodes that are hubs in one layer often have few connections in another.The operational degree is particularly poorly correlated with communication and trust degrees.
  • Degree across layers: Nodes with identical overlapping degree can have radically different multiplex roles when their links are distributed differently across layers.A node concentrated in one layer and a node evenly connected across layers may look identical in an aggregated network.
  • Participation across layers: Multiplex degree entropy is zero when all links lie in one layer and maximal when links are uniformly distributed across layers.Higher entropy indicates a more uniform distribution of a node’s links among layers.
  • Participation across layers: The participation coefficient Pi ranges from 0 for single-layer links to 1 when a node has equal numbers of edges in all M layers.It quantifies whether a node’s links are concentrated in a few layers or distributed uniformly across them.
  • Node-role classification: The average participation coefficient is P = 0.72, while individual values span [0, 1], indicating heterogeneous levels of participation across the three layers.Nodes are classified as focused, mixed, or truly multiplex according to Pi thresholds of 1/3 and 2/3.
  • Node-role classification: Node roles are classified jointly by participation coefficient and the Z-score of overlapping degree, distinguishing six combinations of layer participation and overall connectivity.The Z-score separates hubs with z(oi) ≥2 from regular nodes with z(oi) < 2.

V. EDGE OVERLAP AND SOCIAL REINFORCEMENT

The paper measures inter-layer edge overlap and tests whether stronger trust ties predict relationships in operational, communication, and business layers. In the terrorist multiplex, trust is identified as the leading layer, although the proposed social-reinforcement explanation is not causally testable without longitudinal data.

  • Edge overlap: 46% of edges occur in one layer, 27% in two layers, 23% in three layers, and 4% in all four layers.These distributions quantify inter-layer overlap across trust, operational, communication, and business relations.
  • Conditional overlap: The conditional probability P(a[α′]ij) measures finding an edge in layer α′ given an edge in layer α, while P_w uses the leading layer’s edge weight.The weighted analysis uses trust or operations as the leading layer and examines links in the other layers.
  • Social reinforcement: A trust weight w[T]ij = 2 implies common operations and communications in 80% of cases, while w[T]ij = 3 implies presence in all three remaining layers with probability 1.Trust strength is associated with progressively higher probabilities of links in the other layers.
  • Caveat: The trust-based social-reinforcement interpretation remains untested causally because the data lack longitudinal information on whether trust preceded links in other layers.The paper notes that trust relationships were likely established years before recorded communication, operational, or business relationships, but this does not directly test causation.
  • Social reinforcement: Randomized networks yield lower operational-layer conditional probabilities than the original network, and analogous results hold for communication and business layers.The comparison indicates that heterogeneous degree distributions alone do not explain the observed weighted overlap; trust genuinely drives the observed connection pattern in the authors’ analysis.
  • Social reinforcement: Using operations as the leading layer produces substantially smaller conditional probabilities for trust, communication, and business links than using trust as the leading layer.The authors interpret this asymmetry as consistent with stronger trust relationships boosting other interactions, while the reverse relationship is weaker.

VI. TRANSITIVITY AND CLUSTERING

The paper extends clustering and transitivity to multiplex networks to capture triangles formed across layers, which aggregated or layer-specific measures can miss. In the Indonesian terrorist multiplex, these measures reveal distinct multilayer clustering patterns.

  • Layer-level measures: Layer-specific clustering and transitivity differ substantially from values in the aggregated network.The Operations layer has the highest observed clustering and transitivity, while node rankings across layers are weakly correlated or even anti-correlated.
  • Multiplex triangles: 2-triangles use one edge from one layer and two edges from another, whereas 3-triangles use three different layers.These definitions capture triangles that cannot be formed entirely within a single layer.
  • Clustering interdependence: I1 = 0.31 and I2 is of the order of 10^-3 for the terrorist multiplex.Thus, triangles formed exclusively through two-layer interplay are appreciable, while those requiring three different layers are nearly absent.
  • Multiplex clustering coefficients: The multiplex clustering coefficients C_i,1 and C_i,2 capture different effects and are both needed to quantify multilayer triangle abundance.Their poor correlation with one another and with the aggregated coefficient shows that aggregation provides substantially different information.
  • Multiplex transitivity: T1 measures 2-triangle closure normalized by (M − 1) times 1-triads, while T2 measures 3-triangle closure normalized by (M − 2) times 2-triads.The corresponding network-level quantities T1 and T2 extend transitivity to multilayer closure patterns.
  • Configuration-model comparison: Randomizing edges while preserving each layer’s degree sequence removes inter-layer correlations and generally makes multi-triangles easier to find than in the real multiplex.The real network’s higher edge overlap is associated with fewer such multilayer triangles in the comparison.

VII. REACHABILITY, SHORTEST PATHS AND INTERDEPENDENCE

The paper uses node interdependence to quantify how much multiplex reachability depends on shortest paths spanning multiple layers. In the terrorist network, interdependence varies widely across nodes and is slightly anti-correlated with degree-related measures.

  • Definition: Node interdependence λ_i is the fraction of shortest paths from node i that use links in at least two layers.It equals 1 when all shortest paths are multilayer and 0 when every shortest path uses only one layer.
  • Empirical distribution: Most nodes have λ_i between 0.27 and 0.56 around the average λ = 0.41.Some nodes have λ_i as low as 0.1, while two nodes exceed 0.8.
  • Interpretation: λ_i is a genuine multiplex measure of reachability.It specifically tracks the extent to which shortest paths depend on links from multiple layers rather than only on single-layer connectivity.
  • Relation to node structure: λ_i is slightly anti-correlated with overlapping degree and appears slightly anti-correlated with participation measures.Higher overlapping degree provides more first-edge choices, tending to lower interdependence, whereas lower degree constrains shortest paths to fewer edges and layers.

VIII. CENTRALITY

The paper compares eigenvector centrality across individual layers, aggregated networks, and a proposed multiplex centrality based on weighted combinations of layers. These comparisons reveal weak cross-layer alignment and unequal layer contributions to multiplex centrality.

  • Layer and aggregate centrality: Eigenvector centralities across individual layers show only very weak correlations with one another and with aggregated-network centralities.A slightly higher correlation occurs between layer centralities and aggregated-network centrality, while the maximum correlation is between the topological and overlapping aggregates.
  • Layer and aggregate centrality: Aggregated-network centrality is not correlated with multiplex participation coefficient, with substantial heterogeneity in participation at fixed centrality.The reported Kendall and Pearson correlations between overlapping-network centrality and participation are τ(Ei(O), Pi) = 0.31 and r(Ei(O), Pi) = 0.43.
  • Multiplex centrality: The proposed multiplex centrality for a duplex uses a convex combination of layer adjacency matrices, with b controlling each layer’s relative contribution.b = 0 and b = 1 recover the individual layers, while b = 0.5 gives equal weights and a matrix proportional to the aggregated overlapping network.
  • Multiplex centrality: At b = 0.5, all three duplexes reach Kendall coefficient τk = 1, while T-O contributes more similarly to multiplex centrality than either T-C or O-C.The T-O curves intersect near b = 0.5; T-C and O-C intersect asymmetrically at 0.35 < b < 0.40, indicating stronger contributions from T and O than C.
  • Multiplex centrality: Multiplex centrality is generalized to M layers by weighting and combining the layer adjacency matrices under the constraint that the weights sum to one.The equal-weight benchmark b1 = ... = bM = 1/M coincides with the aggregated overlapping network.

IX. CONCLUSIONS

The paper presents a formalism for multiplex networks that preserves distinctions among relationship types while supporting binary and weighted links. It defines structural measures across multiple descriptive levels and tests them on a four-layer network of 78 Indonesian terrorists.

  • Framework and scope: The formalism distinguishes aggregated topological, overlapping, and weighted overlapping networks from the richer vector of adjacency matrices.The aggregated representations are simpler but less rich than the complete vectorial description.
  • Framework and scope: The proposed metrics cover node degree, edge overlap, node participation, clustering, reachability, and eigenvector centrality.The framework addresses systems with several layers and either binary or weighted links.
  • Validation: The measures are tested on a multiplex network containing 78 nodes and four layers.The layers represent distinct relationships in the Indonesian terrorist network.
Loading 1308.3182v3…