Giuseppe F. Italiano

Lutz Oettershagen, Athanasios L. Konstantinidis, Fariba Ranjbar et al.

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.

Andrea D'Ascenzo, Giuseppe F. Italiano, Sotiris Kanellopoulos et al.

Computing paths in graph structures is a fundamental operation in a wide range of applications, from transportation networks to data analysis. The beer path problem, which captures the option of visiting points of interest, such as gas stations or convenience stops, prior to reaching the final destination, has been recently introduced and extensively studied in static graphs. However, existing approaches do not account for temporal information, which is often crucial in real-world scenarios. For instance, transit services may follow fixed schedules, and shops may only be accessible during certain hours. In this work, we introduce the notion of beer paths in temporal graphs, where edges are time-dependent and certain vertices (beer vertices) are active only at specific time instances. We formally define the problems of computing earliest-arrival, latest-departure, fastest, and shortest temporal beer paths and propose efficient algorithms for these problems under both edge stream and adjacency list representations. The time complexity of each of our algorithms is aligned with that of corresponding temporal pathfinding algorithms, thus preserving efficiency. Additionally, we present preprocessing techniques that enable efficient query answering under dynamic conditions, for example new openings or closings of shops. We achieve this through appropriate precomputation of selected paths or by transforming a temporal graph into an equivalent static graph.

Giuseppe D'Acquisto, Maurizio Naldi, Giuseppe F. Italiano

Every time the customer (individual or company) has to release personal information to its service provider (e.g., an online store or a cloud computing provider), it faces a trade-off between the benefits gained (enhanced or cheaper services) and the risks it incurs (identity theft and fraudulent uses). The amount of personal information released is the major decision variable in that trade-off problem, and has a proxy in the maximum loss the customer may incur. We find the conditions for a unique optimal solution to exist for that problem as that maximizing the customer's surplus. We also show that the optimal amount of personal information is influenced most by the immediate benefits the customer gets, i.e., the price and the quantity of service offered by the service provider, rather than by maximum loss it may incur. Easy spenders take larger risks with respect to low-spenders, but an increase in price drives customers towards a more careful risk-taking attitude anyway. A major role is also played by the privacy level, which the service provider employs to regulate the benefits released to the customers. We also provide a closed form solution for the limit case of a perfectly secure provider, showing that the results do not differ significantly from those obtained in the general case. The trade-off analysis may be employed by the customer to determine its level of exposure in the relationship with its service provider.