Discovering Communication Pattern Shifts in Large-Scale Labeled Networks using Encoder Embedding and Vertex Dynamics

Abstract

Analyzing large-scale time-series network data, such as social media and email communications, poses a significant challenge in understanding social dynamics, detecting anomalies, and predicting trends. In particular, the scalability of graph analysis is a critical hurdle impeding progress in large-scale downstream inference. To address this challenge, we introduce a temporal encoder embedding method. This approach leverages ground-truth or estimated vertex labels, enabling an efficient embedding of large-scale graph data and the processing of billions of edges within minutes. Furthermore, this embedding unveils a temporal dynamic statistic capable of detecting communication pattern shifts across all levels, ranging from individual vertices to vertex communities and the overall graph structure. We provide theoretical support to confirm its soundness under random graph models, and demonstrate its numerical advantages in capturing evolving communities and identifying outliers. Finally, we showcase the practical application of our approach by analyzing an anonymized time-series communication network from a large organization spanning 2019-2020, enabling us to assess the impact of Covid-19 on workplace communication patterns.

arXiv comment10 pages + 2 pages appendix, 8 figures

References in corpus (20)

• Fast unfolding of communities in large networks
• The structure and function of complex networks
• Community structure in social and biological networks
• A Comprehensive Survey on Graph Neural Networks
• DeepWalk: Online Learning of Social Representations
• From Louvain to Leiden: guaranteeing well-connected communities
• Near linear time algorithm to detect community structures in large-scale networks
• Stochastic blockmodels and community structure in networks
• Structural Properties of the Caenorhabditis elegans Neuronal Network
• The Anatomy of the Facebook Social Graph
• Spectral clustering and the high-dimensional stochastic blockmodel
• Narrow scope for resolution-limit-free community detection
• Consistency of community detection in networks under degree-corrected stochastic block models
• Community detection in networks: Structural communities versus ground truth
• Universally consistent vertex classification for latent positions graphs
• One-Hot Graph Encoder Embedding
• Community detection in networks using graph embeddings
• Graph Encoder Ensemble for Simultaneous Vertex Embedding and Community Detection
• Multiple Network Embedding for Anomaly Detection in Time Series of Graphs
• Spectral Network Embedding: A Fast and Scalable Method via Sparsity

Cited by in corpus (6)

• Synergistic Graph Fusion via Encoder Embedding
• Universally Consistent K-Sample Tests via Dependence Measures
• Encoder Embedding for General Graph and Node Classification
• Fast and Scalable Multi-Kernel Encoder Classifier
• Refined Graph Encoder Embedding via Self-Training and Latent Community Recovery
• Efficient Graph Encoder Embedding for Large Sparse Graphs in Python