Skip to main content
Top
Published in: Artificial Intelligence Review 4/2021

30-09-2020

Tensor decomposition for analysing time-evolving social networks: an overview

Authors: Sofia Fernandes, Hadi Fanaee-T, João Gama

Published in: Artificial Intelligence Review | Issue 4/2021

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Social networks are becoming larger and more complex as new ways of collecting social interaction data arise (namely from online social networks, mobile devices sensors, ...). These networks are often large-scale and of high dimensionality. Therefore, dealing with such networks became a challenging task. An intuitive way to deal with this complexity is to resort to tensors. In this context, the application of tensor decomposition has proven its usefulness in modelling and mining these networks: it has not only been applied for exploratory analysis (thus allowing the discovery of interaction patterns), but also for more demanding and elaborated tasks such as community detection and link prediction. In this work, we provide an overview of the methods based on tensor decomposition for the purpose of analysing time-evolving social networks from various perspectives: from community detection, link prediction and anomaly/event detection to network summarization and visualization. In more detail, we discuss the ideas exploited to carry out each social network analysis task as well as its limitations in order to give a complete coverage of the topic.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literature
go back to reference Acar E, Kolda TG, Dunlavy DM (2011) All-at-once optimization for coupled matrix and tensor factorizations. arXiv preprint arXiv:11053422 Acar E, Kolda TG, Dunlavy DM (2011) All-at-once optimization for coupled matrix and tensor factorizations. arXiv preprint arXiv:​11053422
go back to reference Ahn KJ, Guha S, McGregor A (2012) Graph sketches: sparsification, spanners, and subgraphs. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems, pp 5–14 Ahn KJ, Guha S, McGregor A (2012) Graph sketches: sparsification, spanners, and subgraphs. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems, pp 5–14
go back to reference Akoglu L, Tong H, Koutra D (2015) Graph based anomaly detection and description: a survey. Data Min Knowl Discov 29(3):626–688MathSciNet Akoglu L, Tong H, Koutra D (2015) Graph based anomaly detection and description: a survey. Data Min Knowl Discov 29(3):626–688MathSciNet
go back to reference Al-Sharoa E, Al-khassaweneh M, Aviyente S (2017) A tensor based framework for community detection in dynamic networks. In: 2017 IEEE international conference on acoustics, speech and signal processing (ICASSP). IEEE, pp 2312–2316 Al-Sharoa E, Al-khassaweneh M, Aviyente S (2017) A tensor based framework for community detection in dynamic networks. In: 2017 IEEE international conference on acoustics, speech and signal processing (ICASSP). IEEE, pp 2312–2316
go back to reference Andersson CA, Bro R (2000) The n-way toolbox for matlab. Chemom Intell Lab Syst 52(1):1–4 Andersson CA, Bro R (2000) The n-way toolbox for matlab. Chemom Intell Lab Syst 52(1):1–4
go back to reference Araujo MR, Ribeiro PMP, Faloutsos C (2017) Tensorcast: forecasting with context using coupled tensors (best paper award). In: 2017 IEEE international conference on data mining (ICDM). IEEE, pp 71–80 Araujo MR, Ribeiro PMP, Faloutsos C (2017) Tensorcast: forecasting with context using coupled tensors (best paper award). In: 2017 IEEE international conference on data mining (ICDM). IEEE, pp 71–80
go back to reference Araujo M, Papadimitriou S, Günnemann S, Faloutsos C, Basu P, Swami A, Papalexakis EE, Koutra D (2014) Com2: fast automatic discovery of temporal (‘comet’) communities. In: Pacific-Asia conference on knowledge discovery and data mining. Springer, pp 271–283 Araujo M, Papadimitriou S, Günnemann S, Faloutsos C, Basu P, Swami A, Papalexakis EE, Koutra D (2014) Com2: fast automatic discovery of temporal (‘comet’) communities. In: Pacific-Asia conference on knowledge discovery and data mining. Springer, pp 271–283
go back to reference Austin W, Ballard G, Kolda TG (2016) Parallel tensor compression for large-scale scientific data. In: 2016 IEEE international parallel and distributed processing symposium. IEEE, pp 912–922 Austin W, Ballard G, Kolda TG (2016) Parallel tensor compression for large-scale scientific data. In: 2016 IEEE international parallel and distributed processing symposium. IEEE, pp 912–922
go back to reference Bader BW, Harshman RA, Kolda TG (2007) Temporal analysis of semantic graphs using asalsan. In: ICDM. IEEE, pp 33–42 Bader BW, Harshman RA, Kolda TG (2007) Temporal analysis of semantic graphs using asalsan. In: ICDM. IEEE, pp 33–42
go back to reference Bader BW, Kolda TG (2008) Efficient matlab computations with sparse and factored tensors. SIAM J Sci Comput 30(1):205–231MathSciNetMATH Bader BW, Kolda TG (2008) Efficient matlab computations with sparse and factored tensors. SIAM J Sci Comput 30(1):205–231MathSciNetMATH
go back to reference Bauer F, Lizier JT (2012) Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach. EPL (Europhys Lett) 99(6):68007 Bauer F, Lizier JT (2012) Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach. EPL (Europhys Lett) 99(6):68007
go back to reference Beutel A, Talukdar PP, Kumar A, Faloutsos C, Papalexakis EE, Xing EP (2014) Flexifact: scalable flexible factorization of coupled tensors on hadoop. In: Proceedings of the 2014 SIAM international conference on data mining. SIAM, pp 109–117 Beutel A, Talukdar PP, Kumar A, Faloutsos C, Papalexakis EE, Xing EP (2014) Flexifact: scalable flexible factorization of coupled tensors on hadoop. In: Proceedings of the 2014 SIAM international conference on data mining. SIAM, pp 109–117
go back to reference Billio M, Getmansky M, Lo AW, Pelizzon L (2012) Econometric measures of connectedness and systemic risk in the finance and insurance sectors. J Financ Econ 104(3):535–559 Billio M, Getmansky M, Lo AW, Pelizzon L (2012) Econometric measures of connectedness and systemic risk in the finance and insurance sectors. J Financ Econ 104(3):535–559
go back to reference Boldi P, Vigna S (2004) The webgraph framework I: compression techniques. In: Proceedings of the 13th international conference on World Wide Web. ACM, pp 595–602 Boldi P, Vigna S (2004) The webgraph framework I: compression techniques. In: Proceedings of the 13th international conference on World Wide Web. ACM, pp 595–602
go back to reference Boyd S, Parikh N, Chu E, Peleato B, Eckstein J et al (2011) Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn 3(1):1–122MATH Boyd S, Parikh N, Chu E, Peleato B, Eckstein J et al (2011) Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn 3(1):1–122MATH
go back to reference Bro R, De Jong S (1997) A fast non-negativity-constrained least squares algorithm. J Chemom J Chemom Soc 11(5):393–401 Bro R, De Jong S (1997) A fast non-negativity-constrained least squares algorithm. J Chemom J Chemom Soc 11(5):393–401
go back to reference Bro R, Kiers HA (2003) A new efficient method for determining the number of components in parafac models. J Chemom J Chemom Soc 17(5):274–286 Bro R, Kiers HA (2003) A new efficient method for determining the number of components in parafac models. J Chemom J Chemom Soc 17(5):274–286
go back to reference Brunetti C, Harris JH, Mankad S, Michailidis G (2019) Interconnectedness in the interbank market. J Financ Econ 133(2):520–538 Brunetti C, Harris JH, Mankad S, Michailidis G (2019) Interconnectedness in the interbank market. J Financ Econ 133(2):520–538
go back to reference Carroll JD, Chang JJ (1970) Analysis of individual differences in multidimensional scaling via an n-way generalization of “eckart-young” decomposition. Psychometrika 35(3):283–319MATH Carroll JD, Chang JJ (1970) Analysis of individual differences in multidimensional scaling via an n-way generalization of “eckart-young” decomposition. Psychometrika 35(3):283–319MATH
go back to reference Ceulemans E, Kiers HA (2006) Selecting among three-mode principal component models of different types and complexities: a numerical convex hull based method. Br J Math Stat Psychol 59(1):133–150MathSciNet Ceulemans E, Kiers HA (2006) Selecting among three-mode principal component models of different types and complexities: a numerical convex hull based method. Br J Math Stat Psychol 59(1):133–150MathSciNet
go back to reference Chen H, Chung W, Qin J, Reid E, Sageman M, Weimann G (2008) Uncovering the dark web: a case study of jihad on the web. J Am Soc Inf Sci Technol 59(8):1347–1359 Chen H, Chung W, Qin J, Reid E, Sageman M, Weimann G (2008) Uncovering the dark web: a case study of jihad on the web. J Am Soc Inf Sci Technol 59(8):1347–1359
go back to reference Chi EC, Kolda TG (2012) On tensors, sparsity, and nonnegative factorizations. SIAM J Matrix Anal Appl 33(4):1272–1299MathSciNetMATH Chi EC, Kolda TG (2012) On tensors, sparsity, and nonnegative factorizations. SIAM J Matrix Anal Appl 33(4):1272–1299MathSciNetMATH
go back to reference Choi JH, Vishwanathan S (2014) Dfacto: distributed factorization of tensors. In: Advances in neural information processing systems, pp 1296–1304 Choi JH, Vishwanathan S (2014) Dfacto: distributed factorization of tensors. In: Advances in neural information processing systems, pp 1296–1304
go back to reference da Silva Fernandes S, Tork HF, da Gama JMP (2017) The initialization and parameter setting problem in tensor decomposition-based link prediction. In: 2017 IEEE international conference on data science and advanced analytics (DSAA), pp 99–108 da Silva Fernandes S, Tork HF, da Gama JMP (2017) The initialization and parameter setting problem in tensor decomposition-based link prediction. In: 2017 IEEE international conference on data science and advanced analytics (DSAA), pp 99–108
go back to reference Drineas P, Mahoney MW (2007) A randomized algorithm for a tensor-based generalization of the singular value decomposition. Linear Algebra Appl 420(2–3):553–571MathSciNetMATH Drineas P, Mahoney MW (2007) A randomized algorithm for a tensor-based generalization of the singular value decomposition. Linear Algebra Appl 420(2–3):553–571MathSciNetMATH
go back to reference Dunlavy DM, Kolda TG, Acar E (2011) Temporal link prediction using matrix and tensor factorizations. ACM Trans Knowl Discov Data (TKDD) 5(2):10 Dunlavy DM, Kolda TG, Acar E (2011) Temporal link prediction using matrix and tensor factorizations. ACM Trans Knowl Discov Data (TKDD) 5(2):10
go back to reference Erdos D, Miettinen P (2013) Discovering facts with Boolean tensor tucker decomposition. In: Proceedings of the 22nd ACM international conference on conference on information and knowledge management. ACM, pp 1569–1572 Erdos D, Miettinen P (2013) Discovering facts with Boolean tensor tucker decomposition. In: Proceedings of the 22nd ACM international conference on conference on information and knowledge management. ACM, pp 1569–1572
go back to reference Faloutsos M, Faloutsos P, Faloutsos C (1999) On power-law relationships of the internet topology. SIGCOMM Comput Commun Rev 29(4):251–262MATH Faloutsos M, Faloutsos P, Faloutsos C (1999) On power-law relationships of the internet topology. SIGCOMM Comput Commun Rev 29(4):251–262MATH
go back to reference Fanaee-T H, Gama J (2016a) Event detection from traffic tensors: a hybrid model. Neurocomputing 203:22–33 Fanaee-T H, Gama J (2016a) Event detection from traffic tensors: a hybrid model. Neurocomputing 203:22–33
go back to reference Fanaee-T H, Gama J (2016b) Tensor-based anomaly detection: an interdisciplinary survey. Knowl Based Syst 98:130–147 Fanaee-T H, Gama J (2016b) Tensor-based anomaly detection: an interdisciplinary survey. Knowl Based Syst 98:130–147
go back to reference Fernandes S, Fanaee-T H, Gama J (2018) Dynamic graph summarization: a tensor decomposition approach. Data Min Knowl Discov 32(5):1397–1420MathSciNet Fernandes S, Fanaee-T H, Gama J (2018) Dynamic graph summarization: a tensor decomposition approach. Data Min Knowl Discov 32(5):1397–1420MathSciNet
go back to reference Fernandes S, Fanaee-T H, Gama J (2019) Evolving social networks analysis via tensor decompositions: from global event detection towards local pattern discovery and specification. In: International conference on discovery science. Springer, pp 385–395 Fernandes S, Fanaee-T H, Gama J (2019) Evolving social networks analysis via tensor decompositions: from global event detection towards local pattern discovery and specification. In: International conference on discovery science. Springer, pp 385–395
go back to reference Ferrara E, De Meo P, Catanese S, Fiumara G (2014) Detecting criminal organizations in mobile phone networks. Expert Syst Appl 41(13):5733–5750 Ferrara E, De Meo P, Catanese S, Fiumara G (2014) Detecting criminal organizations in mobile phone networks. Expert Syst Appl 41(13):5733–5750
go back to reference Gahrooei MR, Paynabar K (2018) Change detection in a dynamic stream of attributed networks. J Qual Technol 50(4):418–430 Gahrooei MR, Paynabar K (2018) Change detection in a dynamic stream of attributed networks. J Qual Technol 50(4):418–430
go back to reference Gauvin L, Panisson A, Cattuto C (2014) Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach. PloS ONE 9(1):e86028 Gauvin L, Panisson A, Cattuto C (2014) Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach. PloS ONE 9(1):e86028
go back to reference Génois M, Vestergaard CL, Fournet J, Panisson A, Bonmarin I, Barrat A (2015) Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers. Netw Sci 3:326–347 Génois M, Vestergaard CL, Fournet J, Panisson A, Bonmarin I, Barrat A (2015) Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers. Netw Sci 3:326–347
go back to reference Goldfarb D, Qin Z (2014) Robust low-rank tensor recovery: models and algorithms. SIAM J Matrix Anal Appl 35(1):225–253MathSciNetMATH Goldfarb D, Qin Z (2014) Robust low-rank tensor recovery: models and algorithms. SIAM J Matrix Anal Appl 35(1):225–253MathSciNetMATH
go back to reference Goñi J, Esteban FJ, de Mendizábal NV, Sepulcre J, Ardanza-Trevijano S, Agirrezabal I, Villoslada P (2008) A computational analysis of protein-protein interaction networks in neurodegenerative diseases. BMC Syst Biol 2(1):52 Goñi J, Esteban FJ, de Mendizábal NV, Sepulcre J, Ardanza-Trevijano S, Agirrezabal I, Villoslada P (2008) A computational analysis of protein-protein interaction networks in neurodegenerative diseases. BMC Syst Biol 2(1):52
go back to reference Görlitz O, Sizov S, Staab S (2008) Pints: peer-to-peer infrastructure for tagging systems. In: IPTPS, p 19 Görlitz O, Sizov S, Staab S (2008) Pints: peer-to-peer infrastructure for tagging systems. In: IPTPS, p 19
go back to reference Gorovits A, Gujral E, Papalexakis EE, Bogdanov P (2018) Larc: learning activity-regularized overlapping communities across time. In: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1465–1474 Gorovits A, Gujral E, Papalexakis EE, Bogdanov P (2018) Larc: learning activity-regularized overlapping communities across time. In: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1465–1474
go back to reference Grünwald PD (2007) The minimum description length principle. MIT Press, Cambridge Grünwald PD (2007) The minimum description length principle. MIT Press, Cambridge
go back to reference Harshman RA (1970) Foundations of the PARAFAC procedure: models and conditions for an “explanatory” multi-modal factor analysis. In: UCLA working papers in phonetics, vol 16, no 1, p 84 Harshman RA (1970) Foundations of the PARAFAC procedure: models and conditions for an “explanatory” multi-modal factor analysis. In: UCLA working papers in phonetics, vol 16, no 1, p 84
go back to reference Heiberger RH (2018) Predicting economic growth with stock networks. Phys Stat Mech Appl 489:102–111 Heiberger RH (2018) Predicting economic growth with stock networks. Phys Stat Mech Appl 489:102–111
go back to reference Hitchcock FL (1927) The expression of a tensor or a polyadic as a sum of products. J Math Phys 6(1–4):164–189MATH Hitchcock FL (1927) The expression of a tensor or a polyadic as a sum of products. J Math Phys 6(1–4):164–189MATH
go back to reference Isella L, Stehlé J, Barrat A, Cattuto C, Pinton JF, Van den Broeck W (2011) What’s in a crowd? Analysis of face-to-face behavioral networks. J Theor Biol 271(1):166–180MathSciNetMATH Isella L, Stehlé J, Barrat A, Cattuto C, Pinton JF, Van den Broeck W (2011) What’s in a crowd? Analysis of face-to-face behavioral networks. J Theor Biol 271(1):166–180MathSciNetMATH
go back to reference Jeon I, Papalexakis EE, Kang U, Faloutsos C (2015) Haten2: billion-scale tensor decompositions. In: 2015 IEEE 31st international conference on data engineering (ICDE). IEEE, pp 1047–1058 Jeon I, Papalexakis EE, Kang U, Faloutsos C (2015) Haten2: billion-scale tensor decompositions. In: 2015 IEEE 31st international conference on data engineering (ICDE). IEEE, pp 1047–1058
go back to reference Jeon B, Jeon I, Sael L, Kang U (2016) Scout: scalable coupled matrix-tensor factorization-algorithm and discoveries. In: IEEE 32nd international conference on data engineering (ICDE), 2016. IEEE, pp 811–822 Jeon B, Jeon I, Sael L, Kang U (2016) Scout: scalable coupled matrix-tensor factorization-algorithm and discoveries. In: IEEE 32nd international conference on data engineering (ICDE), 2016. IEEE, pp 811–822
go back to reference Jordán F, Nguyen TP, Wc L (2012) Studying protein–protein interaction networks: a systems view on diseases. Brief Funct Genom 11(6):497–504 Jordán F, Nguyen TP, Wc L (2012) Studying protein–protein interaction networks: a systems view on diseases. Brief Funct Genom 11(6):497–504
go back to reference Kang U, Papalexakis E, Harpale A, Faloutsos C (2012) Gigatensor: scaling tensor analysis up by 100 times-algorithms and discoveries. In: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 316–324 Kang U, Papalexakis E, Harpale A, Faloutsos C (2012) Gigatensor: scaling tensor analysis up by 100 times-algorithms and discoveries. In: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 316–324
go back to reference Keeling MJ, Eames KT (2005) Networks and epidemic models. J R Soc Interface 2(4):295–307 Keeling MJ, Eames KT (2005) Networks and epidemic models. J R Soc Interface 2(4):295–307
go back to reference Kiers HA (1993) An alternating least squares algorithm for parafac2 and three-way dedicom. Comput Stat Data Anal 16(1):103–118MathSciNetMATH Kiers HA (1993) An alternating least squares algorithm for parafac2 and three-way dedicom. Comput Stat Data Anal 16(1):103–118MathSciNetMATH
go back to reference Kiers HAL (2000) Towards a standardized notation and terminology in multiway analysis. J Chemom 14(3):105–122MathSciNet Kiers HAL (2000) Towards a standardized notation and terminology in multiway analysis. J Chemom 14(3):105–122MathSciNet
go back to reference Kiers HA, Kinderen A (2003) A fast method for choosing the numbers of components in tucker3 analysis. Br J Math Stat Psychol 56(1):119–125MathSciNet Kiers HA, Kinderen A (2003) A fast method for choosing the numbers of components in tucker3 analysis. Br J Math Stat Psychol 56(1):119–125MathSciNet
go back to reference Kolda TG, Sun J (2008) Scalable tensor decompositions for multi-aspect data mining. In: Eighth IEEE international conference on data mining, 2008. ICDM’08. IEEE, pp 363–372 Kolda TG, Sun J (2008) Scalable tensor decompositions for multi-aspect data mining. In: Eighth IEEE international conference on data mining, 2008. ICDM’08. IEEE, pp 363–372
go back to reference Kossaifi J, Panagakis Y, Anandkumar A, Pantic M (2019) Tensorly: tensor learning in python. J Mach Learn Res 20(1):925–930MATH Kossaifi J, Panagakis Y, Anandkumar A, Pantic M (2019) Tensorly: tensor learning in python. J Mach Learn Res 20(1):925–930MATH
go back to reference Koutra D, Papalexakis EE, Faloutsos C (2012) Tensorsplat: spotting latent anomalies in time. In: 2012 16th Panhellenic conference on informatics (PCI). IEEE, pp 144–149 Koutra D, Papalexakis EE, Faloutsos C (2012) Tensorsplat: spotting latent anomalies in time. In: 2012 16th Panhellenic conference on informatics (PCI). IEEE, pp 144–149
go back to reference Kwak H, Lee C, Park H, Moon S (2010) What is twitter, a social network or a news media? In: Proceedings of the 19th international conference on World wide web. ACM, pp 591–600 Kwak H, Lee C, Park H, Moon S (2010) What is twitter, a social network or a news media? In: Proceedings of the 19th international conference on World wide web. ACM, pp 591–600
go back to reference LeFevre K, Terzi E (2010) Grass: graph structure summarization. In: Proceedings of the 2010 SIAM international conference on data mining. SIAM, pp 454–465 LeFevre K, Terzi E (2010) Grass: graph structure summarization. In: Proceedings of the 2010 SIAM international conference on data mining. SIAM, pp 454–465
go back to reference Leskovec J, Adamic LA, Huberman BA (2007) The dynamics of viral marketing. ACM Trans Web (TWEB) 1(1):5 Leskovec J, Adamic LA, Huberman BA (2007) The dynamics of viral marketing. ACM Trans Web (TWEB) 1(1):5
go back to reference Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. ACM, pp 177–187 Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. ACM, pp 177–187
go back to reference Leskovec J, Mcauley JJ (2012) Learning to discover social circles in ego networks. In: Advances in neural information processing systems, pp 539–547 Leskovec J, Mcauley JJ (2012) Learning to discover social circles in ego networks. In: Advances in neural information processing systems, pp 539–547
go back to reference Ley M (2002) The dblp computer science bibliography: evolution, research issues, perspectives. In: International symposium on string processing and information retrieval. Springer, pp 1–10 Ley M (2002) The dblp computer science bibliography: evolution, research issues, perspectives. In: International symposium on string processing and information retrieval. Springer, pp 1–10
go back to reference Li J, Bien J, Wells M, Li MJ (2018) Package ‘rtensor’. J Stat Softw 87:1–31 Li J, Bien J, Wells M, Li MJ (2018) Package ‘rtensor’. J Stat Softw 87:1–31
go back to reference Lin YR, Sun J, Castro P, Konuru R, Sundaram H, Kelliher A (2009) Metafac: community discovery via relational hypergraph factorization. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 527–536 Lin YR, Sun J, Castro P, Konuru R, Sundaram H, Kelliher A (2009) Metafac: community discovery via relational hypergraph factorization. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 527–536
go back to reference Liu J, Musialski P, Wonka P, Ye J (2013) Tensor completion for estimating missing values in visual data. IEEE Trans Pattern Anal Mach Intell 35(1):208–220 Liu J, Musialski P, Wonka P, Ye J (2013) Tensor completion for estimating missing values in visual data. IEEE Trans Pattern Anal Mach Intell 35(1):208–220
go back to reference Liu K, Da Costa JPCL, So HC, Huang L, Ye J (2016) Detection of number of components in candecomp/parafac models via minimum description length. Digit Signal Process Rev J 51:110–123MathSciNet Liu K, Da Costa JPCL, So HC, Huang L, Ye J (2016) Detection of number of components in candecomp/parafac models via minimum description length. Digit Signal Process Rev J 51:110–123MathSciNet
go back to reference Liu Y, Safavi T, Dighe A, Koutra D (2018) Graph summarization methods and applications: a survey. ACM Comput Surv (CSUR) 51(3):62 Liu Y, Safavi T, Dighe A, Koutra D (2018) Graph summarization methods and applications: a survey. ACM Comput Surv (CSUR) 51(3):62
go back to reference Lü L, Zhou T (2011) Link prediction in complex networks: a survey. Phys Stat Mech Appl 390(6):1150–1170 Lü L, Zhou T (2011) Link prediction in complex networks: a survey. Phys Stat Mech Appl 390(6):1150–1170
go back to reference Ma X, Dong D (2017) Evolutionary nonnegative matrix factorization algorithms for community detection in dynamic networks. IEEE Trans Knowl Data Eng 29(5):1045–1058 Ma X, Dong D (2017) Evolutionary nonnegative matrix factorization algorithms for community detection in dynamic networks. IEEE Trans Knowl Data Eng 29(5):1045–1058
go back to reference Mankad S, Michailidis G (2013) Structural and functional discovery in dynamic networks with non-negative matrix factorization. Phys Rev E 88(4):042812 Mankad S, Michailidis G (2013) Structural and functional discovery in dynamic networks with non-negative matrix factorization. Phys Rev E 88(4):042812
go back to reference Maruhashi K, Guo F, Faloutsos C (2011) Multiaspectforensics: pattern mining on large-scale heterogeneous networks with tensor analysis. In: 2011 International conference on advances in social networks analysis and mining (ASONAM). IEEE, pp 203–210 Maruhashi K, Guo F, Faloutsos C (2011) Multiaspectforensics: pattern mining on large-scale heterogeneous networks with tensor analysis. In: 2011 International conference on advances in social networks analysis and mining (ASONAM). IEEE, pp 203–210
go back to reference Mastrandrea R, Fournet J, Barrat A (2015) Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys. PloS ONE 10(9):e0136497 Mastrandrea R, Fournet J, Barrat A (2015) Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys. PloS ONE 10(9):e0136497
go back to reference Matsubara Y, Sakurai Y, Faloutsos C, Iwata T, Yoshikawa M (2012) Fast mining and forecasting of complex time-stamped events. In: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 271–279 Matsubara Y, Sakurai Y, Faloutsos C, Iwata T, Yoshikawa M (2012) Fast mining and forecasting of complex time-stamped events. In: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 271–279
go back to reference Michalski R, Palus S, Kazienko P (2011) Matching organizational structure and social network extracted from email communication. In: Lecture notes in business information processing, vol 87. Springer, Berlin, pp 197–206 Michalski R, Palus S, Kazienko P (2011) Matching organizational structure and social network extracted from email communication. In: Lecture notes in business information processing, vol 87. Springer, Berlin, pp 197–206
go back to reference Milgram S (1967) The small world problem. Psychol Today 2:60–67 Milgram S (1967) The small world problem. Psychol Today 2:60–67
go back to reference Mørup M, Hansen LK (2009) Automatic relevance determination for multi-way models. J Chemom 23(7–8):352–363 Mørup M, Hansen LK (2009) Automatic relevance determination for multi-way models. J Chemom 23(7–8):352–363
go back to reference Mørup M, Hansen LK, Arnfred SM (2008) Algorithms for sparse nonnegative tucker decompositions. Neural Comput 20(8):2112–2131MATH Mørup M, Hansen LK, Arnfred SM (2008) Algorithms for sparse nonnegative tucker decompositions. Neural Comput 20(8):2112–2131MATH
go back to reference Oliveira M, Gama J (2011) Visualizing the evolution of social networks. In: Portuguese conference on artificial intelligence. Springer, pp 476–490 Oliveira M, Gama J (2011) Visualizing the evolution of social networks. In: Portuguese conference on artificial intelligence. Springer, pp 476–490
go back to reference Papalexakis EE (2016) Automatic unsupervised tensor mining with quality assessment. In: Proceedings of the 2016 SIAM international conference on data mining. SIAM, pp 711–719 Papalexakis EE (2016) Automatic unsupervised tensor mining with quality assessment. In: Proceedings of the 2016 SIAM international conference on data mining. SIAM, pp 711–719
go back to reference Papalexakis EE, Faloutsos C (2015) Fast efficient and scalable core consistency diagnostic for the parafac decomposition for big sparse tensors. In: ICASSP, pp 5441–5445 Papalexakis EE, Faloutsos C (2015) Fast efficient and scalable core consistency diagnostic for the parafac decomposition for big sparse tensors. In: ICASSP, pp 5441–5445
go back to reference Papalexakis EE, Faloutsos C, Sidiropoulos ND (2012) Parcube: sparse parallelizable tensor decompositions. In: Joint European conference on machine learning and knowledge discovery in databases. Springer, pp 521–536 Papalexakis EE, Faloutsos C, Sidiropoulos ND (2012) Parcube: sparse parallelizable tensor decompositions. In: Joint European conference on machine learning and knowledge discovery in databases. Springer, pp 521–536
go back to reference Papalexakis EE, Sidiropoulos ND, Bro R (2013) From k-means to higher-way co-clustering: multilinear decomposition with sparse latent factors. IEEE Trans Signal Process 61(2):493–506 Papalexakis EE, Sidiropoulos ND, Bro R (2013) From k-means to higher-way co-clustering: multilinear decomposition with sparse latent factors. IEEE Trans Signal Process 61(2):493–506
go back to reference Papalexakis EE, Faloutsos C, Sidiropoulos ND (2016) Tensors for data mining and data fusion: models, applications, and scalable algorithms. ACM Trans Intell Syst Technol 8(2):1–44 Papalexakis EE, Faloutsos C, Sidiropoulos ND (2016) Tensors for data mining and data fusion: models, applications, and scalable algorithms. ACM Trans Intell Syst Technol 8(2):1–44
go back to reference Papalexakis E, Pelechrinis K, Faloutsos C (2014) Spotting misbehaviors in location-based social networks using tensors. In: Proceedings of the 23rd international conference on world wide web. ACM, pp 551–552 Papalexakis E, Pelechrinis K, Faloutsos C (2014) Spotting misbehaviors in location-based social networks using tensors. In: Proceedings of the 23rd international conference on world wide web. ACM, pp 551–552
go back to reference Park N, Jeon B, Lee J, Kang U (2016) Bigtensor: mining billion-scale tensor made easy. In: Proceedings of the 25th ACM international on conference on information and knowledge management. ACM, pp 2457–2460 Park N, Jeon B, Lee J, Kang U (2016) Bigtensor: mining billion-scale tensor made easy. In: Proceedings of the 25th ACM international on conference on information and knowledge management. ACM, pp 2457–2460
go back to reference Pasricha R, Gujral E, Papalexakis EE (2018) Identifying and alleviating concept drift in streaming tensor decomposition. arXiv preprint arXiv:180409619 Pasricha R, Gujral E, Papalexakis EE (2018) Identifying and alleviating concept drift in streaming tensor decomposition. arXiv preprint arXiv:​180409619
go back to reference Pavlopoulos GA, Secrier M, Moschopoulos CN, Soldatos TG, Kossida S, Aerts J, Schneider R, Bagos PG (2011) Using graph theory to analyze biological networks. BioData Min 4(1):1–27 Pavlopoulos GA, Secrier M, Moschopoulos CN, Soldatos TG, Kossida S, Aerts J, Schneider R, Bagos PG (2011) Using graph theory to analyze biological networks. BioData Min 4(1):1–27
go back to reference Peng W, Li T (2011) Temporal relation co-clustering on directional social network and author-topic evolution. Knowl Inf Syst 26(3):467–486 Peng W, Li T (2011) Temporal relation co-clustering on directional social network and author-topic evolution. Knowl Inf Syst 26(3):467–486
go back to reference Phan AH, Cichocki A (2011) Parafac algorithms for large-scale problems. Neurocomputing 74(11):1970–1984 Phan AH, Cichocki A (2011) Parafac algorithms for large-scale problems. Neurocomputing 74(11):1970–1984
go back to reference Priebe CE, Conroy JM, Marchette DJ, Park Y (2005) Scan statistics on enron graphs. Comput Math Organ Theory 11(3):229–247MATH Priebe CE, Conroy JM, Marchette DJ, Park Y (2005) Scan statistics on enron graphs. Comput Math Organ Theory 11(3):229–247MATH
go back to reference Ranshous S, Shen S, Koutra D, Harenberg S, Faloutsos C, Samatova NF (2015) Anomaly detection in dynamic networks: a survey. Wiley Interdiscip Rev Comput Stat 7(3):223–247MathSciNet Ranshous S, Shen S, Koutra D, Harenberg S, Faloutsos C, Samatova NF (2015) Anomaly detection in dynamic networks: a survey. Wiley Interdiscip Rev Comput Stat 7(3):223–247MathSciNet
go back to reference Rayana S, Akoglu L (2014) An ensemble approach for event detection and characterization in dynamic graphs. In: Proceedings of the 2nd ACM SIGKDD workshop on outlier detection and description under data diversity (ODD) Rayana S, Akoglu L (2014) An ensemble approach for event detection and characterization in dynamic graphs. In: Proceedings of the 2nd ACM SIGKDD workshop on outlier detection and description under data diversity (ODD)
go back to reference Rossetti G, Cazabet R (2018) Community discovery in dynamic networks: a survey. ACM Comput Surv (CSUR) 51(2):35 Rossetti G, Cazabet R (2018) Community discovery in dynamic networks: a survey. ACM Comput Surv (CSUR) 51(2):35
go back to reference Sapienza A, Panisson A, Wu J, Gauvin L, Cattuto C (2015) Anomaly detection in temporal graph data: an iterative tensor decomposition and masking approach. In: International workshop on advanced analytics and learning on temporal data AALTD, Porto. ECML PKDD, Portugal Sapienza A, Panisson A, Wu J, Gauvin L, Cattuto C (2015) Anomaly detection in temporal graph data: an iterative tensor decomposition and masking approach. In: International workshop on advanced analytics and learning on temporal data AALTD, Porto. ECML PKDD, Portugal
go back to reference Shah N, Koutra D, Zou T, Gallagher B, Faloutsos C (2015) Timecrunch: interpretable dynamic graph summarization. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1055–1064 Shah N, Koutra D, Zou T, Gallagher B, Faloutsos C (2015) Timecrunch: interpretable dynamic graph summarization. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1055–1064
go back to reference Shashua A, Hazan T (2005) Non-negative tensor factorization with applications to statistics and computer vision. In: Proceedings of the 22nd international conference on Machine learning. ACM, pp 792–799 Shashua A, Hazan T (2005) Non-negative tensor factorization with applications to statistics and computer vision. In: Proceedings of the 22nd international conference on Machine learning. ACM, pp 792–799
go back to reference Sheikholeslami F, Giannakis GB (2017) Identification of overlapping communities via constrained egonet tensor decomposition. arXiv preprint arXiv:170704607 Sheikholeslami F, Giannakis GB (2017) Identification of overlapping communities via constrained egonet tensor decomposition. arXiv preprint arXiv:​170704607
go back to reference Shi L, Gangopadhyay A, Janeja VP (2015) Stensr: spatio-temporal tensor streams for anomaly detection and pattern discovery. Knowl Inf Syst 43(2):333–353 Shi L, Gangopadhyay A, Janeja VP (2015) Stensr: spatio-temporal tensor streams for anomaly detection and pattern discovery. Knowl Inf Syst 43(2):333–353
go back to reference Sidiropoulos ND, De Lathauwer L, Fu X, Huang K, Papalexakis EE, Faloutsos C (2017) Tensor decomposition for signal processing and machine learning. IEEE Trans Signal Process 65(13):3551–3582MathSciNetMATH Sidiropoulos ND, De Lathauwer L, Fu X, Huang K, Papalexakis EE, Faloutsos C (2017) Tensor decomposition for signal processing and machine learning. IEEE Trans Signal Process 65(13):3551–3582MathSciNetMATH
go back to reference Spiegel S, Clausen J, Albayrak S, Kunegis J (2011) Link prediction on evolving data using tensor factorization. In: New frontiers in applied data mining. Springer, pp 100–110 Spiegel S, Clausen J, Albayrak S, Kunegis J (2011) Link prediction on evolving data using tensor factorization. In: New frontiers in applied data mining. Springer, pp 100–110
go back to reference Sun J, Tao D, Papadimitriou S, Yu PS, Faloutsos C (2008) Incremental tensor analysis: theory and applications. ACM Trans Knowl Discov Data 2(3):11:1–11:37 Sun J, Tao D, Papadimitriou S, Yu PS, Faloutsos C (2008) Incremental tensor analysis: theory and applications. ACM Trans Knowl Discov Data 2(3):11:1–11:37
go back to reference Sun J, Papadimitriou S, Lin CY, Cao N, Liu S, Qian W (2009) Multivis: content-based social network exploration through multi-way visual analysis. In: Proceedings of the 2009 SIAM international conference on data mining. SIAM, pp 1064–1075 Sun J, Papadimitriou S, Lin CY, Cao N, Liu S, Qian W (2009) Multivis: content-based social network exploration through multi-way visual analysis. In: Proceedings of the 2009 SIAM international conference on data mining. SIAM, pp 1064–1075
go back to reference Sun J, Tao D, Faloutsos C (2006) Beyond streams and graphs: dynamic tensor analysis. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 374–383 Sun J, Tao D, Faloutsos C (2006) Beyond streams and graphs: dynamic tensor analysis. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 374–383
go back to reference Tabassum S, Pereira FSF, Fernandes S, Gama J (2018) Social network analysis: an overview. Wiley Interdiscip Rev Data Min Knowl Discov 8(5):e1256 Tabassum S, Pereira FSF, Fernandes S, Gama J (2018) Social network analysis: an overview. Wiley Interdiscip Rev Data Min Knowl Discov 8(5):e1256
go back to reference Tan H, Feng G, Feng J, Wang W, Zhang YJ, Li F (2013a) A tensor-based method for missing traffic data completion. Transp Res C Emerg Technol 28:15–27 Tan H, Feng G, Feng J, Wang W, Zhang YJ, Li F (2013a) A tensor-based method for missing traffic data completion. Transp Res C Emerg Technol 28:15–27
go back to reference Tang J, Sun J, Wang C, Yang Z (2009) Social influence analysis in large-scale networks. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 807–816 Tang J, Sun J, Wang C, Yang Z (2009) Social influence analysis in large-scale networks. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 807–816
go back to reference Timmerman ME, Kiers HA (2000) Three-mode principal components analysis: choosing the numbers of components and sensitivity to local optima. Br J Math Stat Psychol 53(1):1–16 Timmerman ME, Kiers HA (2000) Three-mode principal components analysis: choosing the numbers of components and sensitivity to local optima. Br J Math Stat Psychol 53(1):1–16
go back to reference Tsalouchidou I, Bonchi F, Morales GDF, Baeza-Yates R (2018) Scalable dynamic graph summarization. IEEE Trans Knowl Data Eng 32(2):360–373 Tsalouchidou I, Bonchi F, Morales GDF, Baeza-Yates R (2018) Scalable dynamic graph summarization. IEEE Trans Knowl Data Eng 32(2):360–373
go back to reference Tucker LR (1966) Some mathematical notes on three-mode factor analysis. Psychometrika 31(3):279–311MathSciNet Tucker LR (1966) Some mathematical notes on three-mode factor analysis. Psychometrika 31(3):279–311MathSciNet
go back to reference Vanhems P, Barrat A, Cattuto C, Pinton JF, Khanafer N, Régis C, Ba K, Comte B, Voirin N (2013) Estimating potential infection transmission routes in hospital wards using wearable proximity sensors. PloS ONE 8(9):e73970 Vanhems P, Barrat A, Cattuto C, Pinton JF, Khanafer N, Régis C, Ba K, Comte B, Voirin N (2013) Estimating potential infection transmission routes in hospital wards using wearable proximity sensors. PloS ONE 8(9):e73970
go back to reference Viswanath B, Mislove A, Cha M, Gummadi KP (2009) On the evolution of user interaction in facebook. In: Proceedings of the 2nd ACM SIGCOMM workshop on social networks (WOSN’09) Viswanath B, Mislove A, Cha M, Gummadi KP (2009) On the evolution of user interaction in facebook. In: Proceedings of the 2nd ACM SIGCOMM workshop on social networks (WOSN’09)
go back to reference Von Luxburg U (2007) A tutorial on spectral clustering. Stat Comput 17(4):395–416MathSciNet Von Luxburg U (2007) A tutorial on spectral clustering. Stat Comput 17(4):395–416MathSciNet
go back to reference Wang P, Xu B, Wu Y, Zhou X (2015) Link prediction in social networks: the state-of-the-art. Sci China Inf Sci 58(1):1–38 Wang P, Xu B, Wu Y, Zhou X (2015) Link prediction in social networks: the state-of-the-art. Sci China Inf Sci 58(1):1–38
go back to reference Xie K, Li X, Wang X, Xie G, Wen J, Cao J, Zhang D (2017) Fast tensor factorization for accurate internet anomaly detection. IEEE/ACM Trans Netw 25(6):3794–3807 Xie K, Li X, Wang X, Xie G, Wen J, Cao J, Zhang D (2017) Fast tensor factorization for accurate internet anomaly detection. IEEE/ACM Trans Netw 25(6):3794–3807
go back to reference Xu J, Chen H (2005) Criminal network analysis and visualization. Commun ACM 48(6):100–107 Xu J, Chen H (2005) Criminal network analysis and visualization. Commun ACM 48(6):100–107
go back to reference Zou B, Li C, Tan L, Chen H (2015) Gputensor: efficient tensor factorization for context-aware recommendations. Inf Sci 299:159–177 Zou B, Li C, Tan L, Chen H (2015) Gputensor: efficient tensor factorization for context-aware recommendations. Inf Sci 299:159–177
Metadata
Title
Tensor decomposition for analysing time-evolving social networks: an overview
Authors
Sofia Fernandes
Hadi Fanaee-T
João Gama
Publication date
30-09-2020
Publisher
Springer Netherlands
Published in
Artificial Intelligence Review / Issue 4/2021
Print ISSN: 0269-2821
Electronic ISSN: 1573-7462
DOI
https://doi.org/10.1007/s10462-020-09916-4

Other articles of this Issue 4/2021

Artificial Intelligence Review 4/2021 Go to the issue

Premium Partner