Combining Information from Multiple Views for Vertex-Based Change Detection in Dynamic Networks: A Comparative Study

Abstract

In the majority of previous network-based change detection methods, entities are often represented as vertices in an undirected graph with weighted edges describing the relationships between entities. However, in most real-world applications, entities share different types of relationships forming multi-view networks that can be well represented by multiple undirected graphs over the same set of vertices. Integrating information across multiple undirected graphs for change detection in noisy dynamic networks is a crucial but challenging issue. In this paper, a multi-view dynamic network is represented as a time sequence of tensors by encoding multi-graph information into the slices of the tensor. We employ spectral embedding together with Procrustes analysis to detect changes due to vertex behavior, that is, vertex-based changes. Through extensive simulation experiments, we demonstrate the performance of several strategies to combine the information from different slices of the tensor, and obtain a single embedding of the multi-view network. In all experiments, we compare the performance of these methods over a variety of changes ranging from easy to difficult for the purpose of detecting vertices that undergo change. We show that two strategies, MCDP-I and MCDP-II, successfully detect all types of vertex-based changes that were considered in the experiments and show better performance compared to the others when the connectivity structure varied considerably across the slices of the tensor. MCDP-I employs a higher-order singular value decomposition to factorize the tensor at each time instant, and MCDP-II, initially embeds each slice of the tensor separately using matrix factorization and then applies generalized Procrustes analysis techniques on the resulting set of embeddings to obtain a combined embedding. Finally, we also illustrate the performance of MCDP-I and MCDP-II for a real-data application.