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. So far, most works discuss the 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. The weighted STC is hard to compute, and our main contribution is an efficient 2-approximative streaming algorithm for the weighted STC in temporal networks. As a technical contribution, we introduce a fully dynamic 2-approximation for the minimum weight vertex cover problem, which is a crucial component of our streaming algorithm. Our evaluation shows that the weighted STC leads to solutions that capture the a priori knowledge given by the edge weights better than the non-weighted STC. Moreover, we show that our streaming algorithm efficiently approximates the weighted STC in large-scale social networks.

Inferring Tie Strength in Temporal Networks / Oettershagen, L.; Konstantinidis, A. L.; Italiano, Giuseppe Francesco. - LNCS, volume 13714:(2023), pp. 69-85. [10.1007/978-3-031-26390-3_5]

Inferring Tie Strength in Temporal Networks

Italiano G. F.
2023

Abstract

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. So far, most works discuss the 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. The weighted STC is hard to compute, and our main contribution is an efficient 2-approximative streaming algorithm for the weighted STC in temporal networks. As a technical contribution, we introduce a fully dynamic 2-approximation for the minimum weight vertex cover problem, which is a crucial component of our streaming algorithm. Our evaluation shows that the weighted STC leads to solutions that capture the a priori knowledge given by the edge weights better than the non-weighted STC. Moreover, we show that our streaming algorithm efficiently approximates the weighted STC in large-scale social networks.
2023
978-3-031-26389-7
978-3-031-26390-3
Temporal network, Tie strength inference, Triadic closure
Inferring Tie Strength in Temporal Networks / Oettershagen, L.; Konstantinidis, A. L.; Italiano, Giuseppe Francesco. - LNCS, volume 13714:(2023), pp. 69-85. [10.1007/978-3-031-26390-3_5]
File in questo prodotto:
File Dimensione Formato  
2206.11705.pdf

Solo gestori archivio

Tipologia: Documento in Pre-print
Licenza: DRM (Digital rights management) non definiti
Dimensione 870.67 kB
Formato Adobe PDF
870.67 kB Adobe PDF   Visualizza/Apri
978-3-031-26390-3_italiano.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: Tutti i diritti riservati
Dimensione 604.74 kB
Formato Adobe PDF
604.74 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/235499
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact