SpringerLink
Log in

Inferring Tie Strength in Temporal Networks

  • Conference paper
  • First Online:
Machine Learning and Knowledge Discovery in Databases (ECML PKDD 2022)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 13714))

  • 792 Accesses

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.

Giuseppe F. Italiano is partially supported by MUR, the Italian Ministry for University and Research, under PRIN Project AHeAD (Efficient Algorithms for HArnessing Networked Data).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 79.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 99.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    We use WeightedMinSTC for the decision and the optimization problem in the following if the context is clear.

References

  1. Adriaens, F., De Bie, T., Gionis, A., Lijffijt, J., Matakos, A., Rozenshtein, P.: Relaxing the strong triadic closure problem for edge strength inference. Data Min. Knowl. Disc. 34, 1–41 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  2. Ahmadian, S., Haddadan, S.: A theoretical analysis of graph evolution caused by triadic closure and algorithmic implications. In: International Conference on Big Data (Big Data), pp. 5–14. IEEE (2020)

    Google Scholar 

  3. Bhattacharya, S., Henzinger, M., Italiano, G.F.: Deterministic fully dynamic data structures for vertex cover and matching. J. Comput. 47(3), 859–887 (2018)

    MathSciNet  MATH  Google Scholar 

  4. Candia, J., González, M.C., Wang, P., Schoenharl, T., Madey, G., Barabási, A.L.: Uncovering individual and collective human dynamics from mobile phone records. J. Phys. A Math. Theor. 41(22), 224015 (2008)

    Article  MathSciNet  Google Scholar 

  5. Chen, J., Molter, H., Sorge, M., Suchý, O.: Cluster editing in multi-layer and temporal graphs. In: International Symposium on Algorithms and Computation, ISAAC, LIPIcs, vol. 123, pp. 24:1–24:13. Schloss Dagstuhl-LZI (2018)

    Google Scholar 

  6. Easley, D.A., Kleinberg, J.M.: Networks, Crowds, and Markets - Reasoning About a Highly Connected World. Cambridge University Press, Cambridge (2010)

    Book  MATH  Google Scholar 

  7. Eckmann, J.P., Moses, E., Sergi, D.: Entropy of dialogues creates coherent structures in e-mail traffic. Proc. Natl. Acad. Sci. 101(40), 14333–14337 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  8. Gallai, T.: Transitiv orientierbare graphen. Acta M. Hung. 18(1–2), 25–66 (1967)

    Article  MathSciNet  MATH  Google Scholar 

  9. Génois, M., Barrat, A.: Can co-location be used as a proxy for face-to-face contacts? EPJ Data Sci. 7(1), 11 (2018)

    Article  Google Scholar 

  10. Gilbert, E., Karahalios, K.: Predicting tie strength with social media. In: Proceedings of the 27th International Conference on Human Factors in Computing Systems, CHI, pp. 211–220. ACM (2009)

    Google Scholar 

  11. Gilbert, E., Karahalios, K., Sandvig, C.: The network in the garden: an empirical analysis of social media in rural life. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pp. 1603–1612 (2008)

    Google Scholar 

  12. Granovetter, M.S.: The strength of weak ties. A. J. Soc. 78(6), 1360–1380 (1973)

    Article  Google Scholar 

  13. Grüttemeier, N., Komusiewicz, C.: On the relation of strong triadic closure and cluster deletion. Algorithmica 82, 853–880 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  14. Hanneke, S., **ng, E.P.: Discrete temporal models of social networks. In: Airoldi, E., Blei, D.M., Fienberg, S.E., Goldenberg, A., **ng, E.P., Zheng, A.X. (eds.) ICML 2006. LNCS, vol. 4503, pp. 115–125. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73133-7_9

    Chapter  Google Scholar 

  15. Hessel, J., Tan, C., Lee, L.: Science, askscience, and badscience: on the coexistence of highly related communities. In: Proceedings of the International AAAI Conference on Web and Social Media, vol. 10, pp. 171–180 (2016)

    Google Scholar 

  16. Himmel, A., Molter, H., Niedermeier, R., Sorge, M.: Adapting the bron-kerbosch algorithm for enumerating maximal cliques in temporal graphs. Soc. Netw. Anal. Min. 7(1), 35:1–35:16 (2017)

    Google Scholar 

  17. Holme, P., Edling, C.R., Liljeros, F.: Structure and time evolution of an internet dating community. Social Netw. 26(2), 155–174 (2004)

    Article  Google Scholar 

  18. Holme, P., Saramäki, J.: Temporal networks. Phys. Rep. 519(3), 97–125 (2012)

    Article  Google Scholar 

  19. Huang, H., Tang, J., Wu, S., Liu, L., Fu, X.: Mining triadic closure patterns in social networks. In: International Conference on World Wide Web, WWW, pp. 499–504. ACM (2014)

    Google Scholar 

  20. Kahanda, I., Neville, J.: Using transactional information to predict link strength in online social networks. In: Proceedings of the International AAAI Conference on Web and Social Media, vol. 3, pp. 74–81 (2009)

    Google Scholar 

  21. Kempe, D., Kleinberg, J.M., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820–842 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kleinberg, J., Tardos, E.: Algorithm Design. Pearson Education, Noida (2006)

    Google Scholar 

  23. Klimt, B., Yang, Y.: The enron corpus: a new dataset for email classification research. In: Boulicaut, J.-F., Esposito, F., Giannotti, F., Pedreschi, D. (eds.) ECML 2004. LNCS (LNAI), vol. 3201, pp. 217–226. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30115-8_22

    Chapter  Google Scholar 

  24. Konstantinidis, A.L., Nikolopoulos, S.D., Papadopoulos, C.: Strong triadic closure in cographs and graphs of low maximum degree. Theor. Comp. Sci. 740, 76–84 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  25. Konstantinidis, A.L., Papadopoulos, C.: Maximizing the strong triadic closure in split graphs and proper interval graphs. Disc. Appl. Math. 285, 79–95 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  26. Kossinets, G., Watts, D.J.: Empirical analysis of an evolving social network. Science 311(5757), 88–90 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  27. Latapy, M., Viard, T., Magnien, C.: Stream graphs and link streams for the modeling of interactions over time. Soc. Netw. Anal. Min. 8(1), 61:1–61:29 (2018)

    Google Scholar 

  28. Lin, N., Dayton, P.W., Greenwald, P.: Analyzing the instrumental use of relations in the context of social structure. Sociol. Meth. Res. 7(2), 149–166 (1978)

    Article  Google Scholar 

  29. Matakos, A., Gionis, A.: Strengthening ties towards a highly-connected world. Data Min. Knowl. Disc. 36(1), 448–476 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  30. Mislove, A., Marcon, M., Gummadi, K.P., Druschel, P., Bhattacharjee, B.: Measurement and analysis of online social networks. In: Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, pp. 29–42 (2007)

    Google Scholar 

  31. Moinet, A., Starnini, M., Pastor-Satorras, R.: Burstiness and aging in social temporal networks. Phys. Rev. Lett. 114(10), 108701 (2015)

    Article  Google Scholar 

  32. Oettershagen, L., Konstantinidis, A.L., Italiano, G.F.: Inferring tie strength in temporal networks (2022). https://arxiv.org/abs/2206.11705

  33. Oettershagen, L., Kriege, N.M., Morris, C., Mutzel, P.: Classifying dissemination processes in temporal graphs. Big Data 8(5), 363–378 (2020)

    Article  Google Scholar 

  34. Ozella, L., et al.: Using wearable proximity sensors to characterize social contact patterns in a village of rural malawi. EPJ Data Sci. 10(1), 46 (2021)

    Article  Google Scholar 

  35. Paranjape, A., Benson, A.R., Leskovec, J.: Motifs in temporal networks. In: Proceedings of the tenth ACM International Conference on Web Search and Data Mining, pp. 601–610 (2017)

    Google Scholar 

  36. Pyatkin, A., Lykhovyd, E., Butenko, S.: The maximum number of induced open triangles in graphs of a given order. Optim. Lett. 13(8), 1927–1935 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  37. Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: AAAI (2015). https://networkrepository.com/

  38. Rozenshtein, P., Tatti, N., Gionis, A.: Inferring the strength of social ties: a community-driven approach. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1017–1025. ACM (2017)

    Google Scholar 

  39. Sintos, S., Tsaparas, P.: Using strong triadic closure to characterize ties in social networks. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1466–1475 (2014)

    Google Scholar 

  40. Stehlé, J., et al.: High-resolution measurements of face-to-face contact patterns in a primary school. PloS One 6(8), e23176 (2011)

    Article  Google Scholar 

  41. Tantipathananandh, C., Berger-Wolf, T.Y.: Finding communities in dynamic social networks. In: International Conference on Data Mining, ICDM, pp. 1236–1241. IEEE (2011)

    Google Scholar 

  42. Wei, H.T., Hon, W.K., Horn, P., Liao, C.S., Sadakane, K.: An O(1)-approximation algorithm for dynamic weighted vertex cover with soft capacity. In: Approximation, Random, and Combinatorial Optics Algorithm and Techniques (APPROX/RANDOM 2018). LIPIcs, vol. 116, pp. 27:1–27:14. Schloss Dagstuhl-LZI (2018)

    Google Scholar 

  43. Wu, B., Yi, K., Li, Z.: Counting triangles in large graphs by random sampling. IEEE Trans. Knowl. Data Eng. 28(8), 2013–2026 (2016)

    Article  Google Scholar 

  44. **ang, R., Neville, J., Rogati, M.: Modeling relationship strength in online social networks. In: International Conference on World Wide Web, WWW, pp. 981–990. ACM (2010)

    Google Scholar 

  45. Zhou, L., Yang, Y., Ren, X., Wu, F., Zhuang, Y.: Dynamic network embedding by modeling triadic closure process. In: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, pp. 571–578. AAAI Press (2018)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Computer Science, University of Bonn, Bonn, Germany

    Lutz Oettershagen

  2. Luiss University, Rome, Italy

    Athanasios L. Konstantinidis & Giuseppe F. Italiano

Authors
  1. Lutz Oettershagen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Athanasios L. Konstantinidis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Giuseppe F. Italiano
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lutz Oettershagen .

Editor information

Editors and Affiliations

  1. Grenoble Alpes University, Saint Martin d'Hères, France

    Massih-Reza Amini

  2. INSA Rouen Normandy, Saint Etienne du Rouvray, France

    Stéphane Canu

  3. Ruhr-Universität Bochum, Bochum, Germany

    Asja Fischer

  4. KU Leuven, Leuven, Belgium

    Tias Guns

  5. Central European University, Vienna, Austria

    Petra Kralj Novak

  6. Aristotle University of Thessaloniki, Thessaloniki, Greece

    Grigorios Tsoumakas

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Oettershagen, L., Konstantinidis, A.L., Italiano, G.F. (2023). Inferring Tie Strength in Temporal Networks. In: Amini, MR., Canu, S., Fischer, A., Guns, T., Kralj Novak, P., Tsoumakas, G. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2022. Lecture Notes in Computer Science(), vol 13714. Springer, Cham. https://doi.org/10.1007/978-3-031-26390-3_5

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-26390-3_5

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-26389-7

  • Online ISBN: 978-3-031-26390-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation