Clustering for Dynamic Neworks

Fig. 1: Shematic of dynamic clustering task (image credit: reference [1])


Project overview

The discovery of evolving communities in dynamic networks is an important topic in the study of complex network that poses challenging tasks. In the past decade extensive research has been done on incremental community tracing which focusses mostly on the evolution of communities in di erent time slots. In these works, the general assumption is that as new data arrives, the older data are forgotten. The main concerns regarding with this theme of analysis are detecting, tracing, and exploring insights about the evolution of same communities across time. However, in most recent years another approach is getting popular and some learning models assuring Temporal Smoothness of communities has been proposed. This perspective infers communities evolution during learning and adapting sequence of dynamic probabilistic models with considering that the evolution is a smooth process which means that the more drastic changes in the communities occurs with less probability. In this project we propose a new probilistic model, considering temporal smoothness, and without typical drawbacks of previous models such as unability to handle variable number of clustering over time, having several parameters to set beforhand, and high error and variance results. Our aim is to overcome these challenges using a probablistic Bayesian models and analyze detected communities on real and synthetic datasets.

Project Description and Evaluation

In our model, we assigned each community a latent variable and each node is described by all communities and consequently we have enough variables to be able to measure participation degree of a node in each community and identify overlapping communities in dynamic network. This tool is useful in many practical situations where dynamic overlapping community detection is desired. We introduced a method for dynamic clustering by employing a factorization probabilistic generative model which can handles directed and undirected communities. In Fig 2. results of our algorithm called DNMF is compared to other baseline algorithms for synthetic datasets with different noise levels. As it is depicted, our algorithm performs better  in terms of normalized mutual information than others in less noisy datasets. 



Fig 2. The average NMI over all timesteps

MATLAB code ]


Prof. Mark Coates
Niloufar Afsariardchi


[1] Y. Lin, Y. Chi, S. Zhu, H. Sundaram, and B. L. Tseng, “Facetnet: a framework for analyzing communities and their evolutions in dynamic networks,” in Proc. of int. conf. on World Wide Web, 2008, pp. 685–694.

[2] Y. Park, C. Moore, and J. S. Bader, “Dynamic networks from hierarchical bayesian graph clustering,” PLoS ONE, vol. 5, January 2010.

[3] D. Chakrabarti, R. Kumar, and A. Tomkins, “Evolutionary clustering,” in Proc. of the ACM SIGKDD int. conf. on Knowledge discovery and data mining, 2006, pp. 554–560.