Multi-Step Community Detection and Hierarchical Time Segmentation in Evolving Networks


Thomas Aynaud and Jean-Loup Guillaume

proceedings of the Fifth SNA-KDD Workshop Social Network Mining and
Analysis, in conjunction with the 17th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining (KDD 2011)


Many complex systems composed of interacting objects  like social
networks or the web can be modeled as graphs. They can usually be
divided in dense sub-graphs with few links between them, called
communities and detecting this underlying community structure
may have a major impact in the understanding of these systems. We
focus here on evolving graphs, for which the usual approach is to
represent the state of the system at different time steps and to
compute communities independently on the graph obtained at each time
step. We propose in this paper to use a different framework: instead of

detecting communities on each time step, we detect a unique
decomposition in communities that is relevant for (almost) every time
step during a given period called the time window.  We propose a
definition of this new decomposition and two algorithms to detect it
quickly. We validate both the approach and the algorithms on three
evolving networks of different kinds showing that the quality loss at
each time step is very low despite the constraint of maximization on
several time steps. Since the time window length is a crucial parameter of our technique,

we also propose an unsupervised hierarchical clustering algorithm to
build automatically a hierarchical time segmentation into time
windows. This clustering relies on a new similarity measure based on
community structure. We show that it is very efficient in detecting
meaningful windows.

This entry was posted in Papers and tagged ,