Priority-based Clustering in Weighted Graph Streams

Nowadays, analyzing social networks is one of interesting research issues. Each network could be modeled by a graph structure. Clustering the vertices of this graph is a proper method to analyze the network. However, huge amount of changes in the graph structure as a result of social network interactions implies the need of an efficient clustering algorithm to process the stream of updates in a real-time manner. In this paper, we propose a novel algorithm for dynamic networks clustering based on the stream model. In our proposed algorithm, called Priority-based Clustering of Weighted Graph Streams (PCWGS), we provide a measure based on the importance of the frequency of recent interactions in the network to have more acceptable clusters. In PCWGS algorithm, a timestamp coupled with the weighted mean of the number of interactions of the network vertices are used to account edge weights. It is worth noting that, we present a data structure, which can keep useful information about the current state of the edges in the network based on update times and their weights while minimizing the required memory space in our proposed algorithm. Our simulations on real data sets reveal that PCWGS algorithm yields clustering with high quality and performance compared to previous state-of-the-art evolution-aware clustering algorithms.