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)

**Abstract**

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.