2012 SeqiBlocMiningMultiTimeSpanning

Subject Headings:

Notes

Blockmodelling is an important technique for decomposing graphs into sets of roles. Vertices playing the same role have similar patterns of interactions with vertices in other roles. These roles, along with the role to role interactions, can succinctly summarise the underlying structure of the studied graphs. As the underlying graphs evolve with time, it is important to study how their blockmodels evolve too. This will enable us to detect role changes across time, detect different patterns of interactions, for example, weekday and weekend behaviour, and allow us to study how the structure in the underlying dynamic graph evolves. To date, there has been limited research on studying dynamic blockmodels. They focus on smoothing role changes between adjacent time instances. However, this approach can overfit during stationary periods where the underling structure does not change but there is random noise in the graph. Therefore, an approach to a) find blockmodels across spans of time and b) to find the stationary periods is needed. In this paper, we propose an information theoretic framework, SeqiBloc, combined with a change point detection approach to achieve a) and b). In addition, we propose new vertex equivalence definitions that include time, and show how they relate back to our information theoretic approach. We demonstrate their usefulness and superior accuracy over existing work on synthetic and real datasets.

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 SeqiBlocMiningMultiTimeSpanning	Wei Liu James Bailey Jeffrey Chan Christopher Leckie Kotagiri Ramamohanarao			SeqiBloc: Mining Multi-time Spanning Blockmodels in Dynamic Graphs				10.1145/2339530.2339635		2012