Inferring tie strengths in social networks is an essential task in social network analysis. Common approaches classify the ties as weak and strong ties based on the strong triadic closure (STC). The STC states that if for three nodes, A, B, and C, there are strong ties between A and B, as well as A and C, there has to be a (weak or strong) tie between B and C. A variant of the STC called STC+ allows adding a few new weak edges to obtain improved solutions. So far, most works discuss the STC or STC+ in static networks. However, modern large-scale social networks are usually highly dynamic, providing user contacts and communications as streams of edge updates. Temporal networks capture these dynamics. To apply the STC to temporal networks, we first generalize the STC and introduce a weighted version such that  empirical a priori knowledge given in the form of edge weights is respected by the STC. Similarly, we introduce a generalized weighted version of the STC+. The weighted STC is hard to compute, and our main contribution is an efficient 2-approximation (resp. 3-approximation) streaming algorithm for the weighted STC (resp. STC+) in temporal networks. As a technical contribution, we introduce a fully dynamic k-approximation for the minimum weighted vertex cover problem in hypergraphs with edges of size k, which is a crucial component of our streaming algorithms. An empirical evaluation shows that the weighted STC leads to solutions that better capture the a priori knowledge given by the edge weights than the non-weighted STC. Moreover, we show that our streaming algorithm efficiently approximates the weighted STC in real-world large-scale social networks.

Giuseppe F. Italiano is a professor of computer science at LUISS University in Rome. He received his laurea summa cum laude in electrical engineering from Sapienza University of Rome in 1986, and a PhD in computer science from Columbia University in 1991. He was research staff member (1991-1996) at the IBM Thomas J. Watson Research Center and a full professor of computer science at the University of Salerno (1994-1995), at the Ca' Foscari University of Venice (1995-1998), and at the University of Rome Tor Vergata (1998-2018), where he was department chair from 2004 to 2012. Since 2018 he is professor of computer science at LUISS University. From 2008 to 2014, he was editor-in-chief of the ACM Journal of Experimental Algorithmics. He is an EATCS fellow.