Tensor decomposition for analysing time-evolving social networks: an overview
- PDF / 2,041,495 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 178 Views
Tensor decomposition for analysing time‑evolving social networks: an overview Sofia Fernandes1 · Hadi Fanaee‑T2 · João Gama1
© Springer Nature B.V. 2020
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. Keywords Social networks · Tensor decomposition · Time evolution · Network analysis
1 Introduction Evolving networks consist of sets of entities (such as people), interacting with each other over time. These networks are dubbed as social when the interactions exhibit social (non-random) patterns such as the small world effect (Milgram 1967), the skewed degree distribution (Barabási and Albert 1999; Faloutsos et al. 1999), the densification * Sofia Fernandes [email protected] Hadi Fanaee‑T [email protected] João Gama [email protected] 1
LIAAD, INESC TEC, University of Porto, Porto, Portugal
2
Center for Applied Intelligent Systems Research (CAISR), Halmstad University, Halmstad, Sweden
13
Vol.:(0123456789)
S. Fernandes et al.
power law and the shrinking diameters (Leskovec et al. 2005). Briefly, the small world effect states that, on average, only five intermediates are needed to link two random individuals by following an “acquaintance of” sequential path. This is also known as six degree separation. Recent work has provided evidence that this distance is even smaller—4 intermediates (Kwak et al. 2010). Barabási and Albert (1999) and Faloutsos et al. (1999) provided empirical evidence that the node degree distribution in this type of networks was right-skewed, that is, there were several nodes with low degree and few with high degree. Finally, in Leskovec et al. (2005), the authors found that the number of edges grows superlinearly in the number of the nodes over time and, consequently, the average degree grows over time. This property is referred to as densification power law. On the other hand, the authors observed that the distance between vertexes decreased over time. In other words, the number o
Data Loading...
