Clustering Dynamic Graphs Using Time and Text Content
摘要
Modern datasets can often be represented as dynamic graphs; for example, email communications, online forums, and network traffic all fall under this umbrella. As these datasets can be large in size, graph clustering techniques are frequently used to organize the data into manageable chunks. Clustering communications is particularly valuable for identifying meaningful interactions, tracking evolving discussions, and detecting behavioral patterns. However, past algorithms have primarily focused on using the graph topology and time dynamics of the data when clustering, organizing the edges into clusters representing coherent spans of activity – a short conversation between individuals, for example. This ignores other features in the graph that may be useful for clustering such as the text content of the messages being sent. A conversation should have a coherent topic of discussion, therefore clustering edges according to topical similarity in the text can lead to clusters more naturally aligned with human conversations. In this paper we introduce a new dynamic clustering algorithm which takes into account additional metadata alongside the topology and time dynamics, and demonstrate how our approach can find clusters that are coherent in terms of both time and text content, leading to performance improvements of up to 0.28 greater AUC on thread prediction tasks.