Consistent Tie-Strength Labeling for Multilayer Strong Triadic Closure

Abstract

Inferring tie strengths (strong vs. weak) is a core task in network analysis, often guided by the Strong Triadic Closure (STC) principle. In multilayer networks, such as social platforms or biological systems, applying STC independently to each layer can lead to inconsistent tie labels, undermining interpretations that rely on coherent relationship semantics across layers. We propose new formulations, multilayer STC and its extension STC+, which are axiomatically grounded and enforce cross-layer consistency. These problems are NP-hard; we present efficient 2- and 6-approximation algorithms alongside exact solutions. Experiments on real-world networks demonstrate that our methods produce consistent tie strength labelings with a transparent structural justification, significantly improving over the baselines.

Accepted for ECML PKDD 2026 Journal track

References in corpus (9)

• Multilayer Networks
• The structure and dynamics of multilayer networks
• Mathematical Formulation of Multi-Layer Networks
• Layer aggregation and reducibility of multilayer interconnected networks
• Emergence of network features from multiplexity
• Estimating Potential Infection Transmission Routes in Hospital Wards Using Wearable Proximity Sensors
• MuxViz: A Tool for Multilayer Analysis and Visualization of Networks
• Inferring the strength of social ties: a community-driven approach
• From acquaintance to best friend forever: robust and fine-grained inference of social tie strengths