Consistent Tie-Strength Labeling for Multilayer Strong Triadic Closure
For network analysts studying multilayer systems (e.g., social or biological networks), this work provides a principled method to infer consistent tie strengths across layers, addressing a key limitation of applying STC independently per layer.
The paper introduces multilayer Strong Triadic Closure (STC) and STC+ formulations that enforce cross-layer consistency in tie-strength labeling, which is NP-hard. They provide efficient approximation algorithms (2- and 6-approximation) and exact solutions, demonstrating significant improvements over baselines on real-world networks.
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.