WINTENDED: WINdowed TENsor decomposition for densification event detection in time-evolving networks. (English) Zbl 07694492
Summary: Densification events in time-evolving networks refer to instants in which the network density, that is, the number of edges, is substantially larger than in the remaining. These events can occur at a global level, involving the majority of the nodes in the network, or at a local level involving only a subset of nodes. While global densification events affect the overall structure of the network, the same does not hold in local densification events, which may remain undetectable by the existing detection methods. In order to address this issue, we propose WINdowed TENsor decomposition for Densification Event Detection (WINTENDED) for the detection and characterization of both global and local densification events. Our method combines a sliding window decomposition with statistical tools to capture the local dynamics of the network and automatically find the irregular behaviours. According to our experimental evaluation, WINTENDED is able to spot global densification events at least as accurately as its competitors, while also being able to find local densification events, on the contrary to its competitors.
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
Software:
TensorToolboxReferences:
| [1] | Akoglu, L., & Faloutsos, C., (2010). Event detection in time series of mobile communication graphs. In: Army Science Conference, pp. 77-79 |
| [2] | Akoglu, L.; Tong, H.; Koutra, D., Graph based anomaly detection and description: A survey, Data mining and knowledge discovery, 29, 3, 626-688 (2015) · doi:10.1007/s10618-014-0365-y |
| [3] | Bader, BW; Kolda, TG, Efficient MATLAB computations with sparse and factored tensors, SIAM Journal on Scientific Computing, 30, 1, 205-231 (2007) · Zbl 1159.65323 · doi:10.1137/060676489 |
| [4] | Bader, B.W., & Kolda, T.G., et al. (2015). Matlab tensor toolbox version 2.6. Available online . http://www.sandia.gov/ tgkolda/TensorToolbox/ |
| [5] | Berlingerio, M., Koutra, D., Eliassi-Rad, T., & Faloutsos, C., (2013). Network similarity via multiple social theories. In: Advances in Social Networks Analysis and Mining (ASONAM), 2013 IEEE/ACM International Conference on, pp. 1439-1440. IEEE |
| [6] | Berry, M. W., & Browne, M. (2005). Understanding search engines: Mahematical modeling and text retrieval. Siam · Zbl 1075.68591 |
| [7] | Carić, T.; Fosin, J., Using congestion zones for solving the time dependent vehicle routing problem, Promet - Traffic&Transportation, 32, 1, 25-38 (2020) · doi:10.7307/ptt.v32i1.3296 |
| [8] | Chi, EC; Kolda, TG, On tensors, sparsity, and nonnegative factorizations, SIAM Journal on Matrix Analysis and Applications, 33, 4, 1272-1299 (2012) · Zbl 1262.15029 · doi:10.1137/110859063 |
| [9] | Ching, A.; Edunov, S.; Kabiljo, M.; Logothetis, D.; Muthukrishnan, S., One trillion edges: Graph processing at facebook-scale, Proceedings of the VLDB Endowment, 8, 12, 1804-1815 (2015) · doi:10.14778/2824032.2824077 |
| [10] | Costa, P., (2018). Online network analysis of stock markets. Master’s thesis, University of Porto |
| [11] | Dawson, R. (2011). How significant is a boxplot outlier? Journal of Statistics Education,19(2). doi:10.1080/10691898.2011.11889610 |
| [12] | Desmier, E., Plantevit, M., Robardet, C., & Boulicaut, J.F., (2012). Cohesive co-evolution patterns in dynamic attributed graphs. In: International Conference on Discovery Science, pp. 110-124. Springer |
| [13] | Dunlavy, DM; Kolda, TG; Acar, E., Temporal link prediction using matrix and tensor factorizations, ACM Transactions on Knowledge Discovery from Data (TKDD), 5, 2, 1-27 (2011) · doi:10.1145/1921632.1921636 |
| [14] | Eagle, N.; Pentland, AS, Reality mining: Sensing complex social systems, Personal and ubiquitous computing, 10, 4, 255-268 (2006) · doi:10.1007/s00779-005-0046-3 |
| [15] | Fanaee-T, H.; Gama, J., Event detection from traffic tensors: A hybrid model, Neurocomputing, 203, 22-33 (2016) · doi:10.1016/j.neucom.2016.04.006 |
| [16] | 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, pp. 385-395. Springer |
| [17] | Hansen, S.; Plantenga, T.; Kolda, TG, Newton-based optimization for kullback-leibler nonnegative tensor factorizations, Optimization Methods and Software, 30, 5, 1002-1029 (2015) · Zbl 1336.90086 · doi:10.1080/10556788.2015.1009977 |
| [18] | Hosseinimotlagh, S., & Papalexakis, E.E. (2018). Unsupervised content-based identification of fake news articles with tensor decomposition ensembles. In: Proceedings of the Workshop on Misinformation and Misbehavior Mining on the Web (MIS2) |
| [19] | Isella, L., Stehlé, J., Barrat, A., Cattuto, C., Pinton, J.F., & Van den Broeck, W., (2011). What’s in a crowd? analysis of face-to-face behavioral networks. Journal of theoretical biology 271(1), 166-180 http://www.sociopatterns.org/datasets/infectious-sociopatterns-dynamic-contact-networks/ · Zbl 1405.92255 |
| [20] | Jeon, B., Jeon, I., Sael, L., & Kang, U., (2016). Scout: Scalable coupled matrix-tensor factorization-algorithm and discoveries. In: 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pp. 811-822. IEEE |
| [21] | Kapsabelis, KM; Dickinson, PJ; Dogancay, K., Investigation of graph edit distance cost functions for detection of network anomalies, ANZIAM Journal, 48, 436-449 (2007) · doi:10.21914/anziamj.v48i0.47 |
| [22] | Kolda, TG; Bader, BW, Tensor decompositions and applications, SIAM review, 51, 3, 455-500 (2009) · Zbl 1173.65029 · doi:10.1137/07070111X |
| [23] | Kolda, T.G., & Sun, J., (2008). Scalable tensor decompositions for multi-aspect data mining. In: 2008 Eighth IEEE International Conference on Data Mining, pp. 363-372 |
| [24] | Koutra, D., Papalexakis, E.E., & Faloutsos, C. (2012). Tensorsplat: Spotting latent anomalies in time. In: Proceedings of the 2012 16th Panhellenic Conference on Informatics, PCI ’12, pp. 144-149. IEEE Computer Society |
| [25] | Levenshtein, VI, Binary codes capable of correcting deletions, insertions, and reversals, Soviet physics doklady, 10, 707-710 (1966) · Zbl 0149.15905 |
| [26] | 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, pp. 197-206. Springer Berlin Heidelberg |
| [27] | Papadimitriou, S., Sun, J., & Faloutsos, C. (2005). Streaming pattern discovery in multiple time-series |
| [28] | Papalexakis, E., Pelechrinis, K., & Faloutsos, C. (2014). Spotting misbehaviors in location-based social networks using tensors. In: Proceedings of the companion publication of the 23rd international conference on World wide web companion, pp. 551-552. International World Wide Web Conferences Steering Committee |
| [29] | Papalexakis, E.E., (2016). Automatic unsupervised tensor mining with quality assessment. In: Proceedings of the 2016 SIAM International Conference on Data Mining, pp. 711-719. SIAM |
| [30] | Papalexakis, E.E., Faloutsos, C., & Sidiropoulos, N.D., (2012). Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2012, Bristol, UK, September 24-28, 2012. Proceedings, Part I, chap. ParCube: Sparse Parallelizable Tensor Decompositions, pp. 521-536. Springer Berlin Heidelberg, Berlin, Heidelberg |
| [31] | Priebe, CE; Conroy, JM; Marchette, DJ; Park, Y., Scan statistics on enron graphs, Computational & Mathematical Organization Theory, 11, 3, 229-247 (2005) · Zbl 1086.68562 · doi:10.1007/s10588-005-5378-z |
| [32] | Ranshous, S.; Shen, S.; Koutra, D.; Harenberg, S.; Faloutsos, C.; Samatova, NF, Anomaly detection in dynamic networks: A survey, Wiley Interdisciplinary Reviews: Computational Statistics, 7, 3, 223-247 (2015) · Zbl 07912769 · doi:10.1002/wics.1347 |
| [33] | Rayana, S., & Akoglu, L., (2014). An ensemble approach for event detection and characterization in dynamic graphs. In: ACM SIGKDD ODD Workshop |
| [34] | Rayana, S.; Akoglu, L., Less is more: Building selective anomaly ensembles, ACM Transactions on Knowledge Discovery from Data (TKDD), 10, 4, 42 (2016) · doi:10.1145/2890508 |
| [35] | Shin, K., Hooi, B., & Faloutsos, C. (2016). M-zoom: Fast dense-block detection in tensors with quality guarantees. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 264-280. Springer |
| [36] | Shin, K., Hooi, B., Kim, J., & Faloutsos, C., (2017). D-cube: Dense-block detection in terabyte-scale tensors. In: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pp. 681-689. ACM |
| [37] | Shoubridge, P.; Kraetzl, M.; Wallis, W.; Bunke, H., Detection of abnormal change in a time series of graphs, Journal of Interconnection Networks, 3, 1-2, 85-101 (2002) · doi:10.1142/S0219265902000562 |
| [38] | da Silva Fernandes, S., Tork, H.F., & da Gama, J.M.P., (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. IEEE |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
