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.

We consider the problem of identifying failure nodes in networks under the Boolean Network Tomography ( BNT ) approach, which is based on end-to-end measurements routed in a network along paths and producing a boolean (failure/not-failure) outcome. Such end-to-end measurements paths are usually described by an incidence boolean matrix M with m rows (the measurements paths) and n columns (the nodes of the network). A key notion used in practice in this approach is that of k - identifiability . Loosely speaking, a set of m boolean measurements paths over n nodes is k -identifiable, where k is a non-negative integer, if, whenever there are fewer than k + 1 failures, it is always possible to identify unambiguously and uniquely which nodes are failing. Following the focus of some recent results analyzing maximal identifiability from a theoretical point of view, this work establishes the complexity of the optimization problem that determines the maximal k for which a set of measurement paths is k -identifiable ( MID ). We prove that such problem is NP -hard by a reduction from the Minimum Hitting Set problem and we prove that its decision version is in NP . We further consider the following extremal combinatoric question, which is also of practical relevance: given the number n of nodes of the network and a non-negative integer value k for the identifiability, what is the minimal number m of measurement paths over the n nodes to consider in such a way that the maximal identifiability is at least k ? A folklore result shows that to have maximal identifiability at least 1, then m ≥ log ( n + 1 ) (or, equivalently, that if n > 2 m − 1 , then the maximal identifiability is less than or equal 0). In this work we answer this question for each n ∈ N and for each k ≥ 2 , proving that, there is constant C such that if n > C m 1 + m k − 1 , then the maximal identifiability value is strictly smaller than k (and when k = 2 , n > C m m suffices). Finally, we study upper and lower bounds on the number of unambiguously identifiable nodes, introducing new identifiability conditions which strictly imply and are strictly implied by unambiguous identifiability. We use these new conditions to design algorithmic heuristics to count defective nodes in a fine-grained way. In particular we introduce a random model to study lower bounds on the number of unambiguously identifiable defective nodes and we use this model to estimate lower bounds on the number of identifiable nodes on real networks by a maximum likelihood estimate approach.

We study maximal identifiability, a measure recently introduced in Boolean Network Tomography to characterize networks' capability to localize failure nodes in end-to-end path measurements. Under standard assumptions on topologies and on monitors placement, we prove tight upper and lower bounds on the maximal identifiability of failure nodes for specific classes of network topologies, such as trees, bounded-degree graphs, d-dimensional grids, in both directed and undirected cases. Among other results we prove that directed d-dimensional grids with support n have maximal identifiability d using nd monitors; and in the undirected case we show that 2d monitors suffice to get identifiability of d-1. We then study identifiability under embeddings: we establish relations between maximal identifiability, embeddability and dimension when network topologies are modelled as DAGs. Through our analysis we also refine and generalize results on limits of maximal identifiability recently obtained in [12] and [1]. Our results suggest the design of networks over N nodes with maximal identifiability Ω(√log N) using 2√log N monitors and heuristics to place monitors and edges in a network to boost maximal identifiability.