Significant Substructure Discovery in Dynamic Networks

Guimin      Qin; Lin      Gao; Jianye      Yang

Abstract

Most complex networks, such as biological networks, social networks, and information networks, are dynamic in nature. Therefore, analysis of these networks provides a better understanding of complex systems compared with analysis of static networks. In this paper, we define a new problem to find the substructures that are significant during the evolving periods, including conserved, appearing and disappearing substructures, and so on. We propose a novel framework for discovering such significant substructures. By using the representation of the summary graph and the approach of densitybased clustering algorithm, we just need to execute the core process in one network without the loss of the temporal information. Experiments on artificially generated PPI (protein-protein interaction) networks and real-world data show that our method can lead to the discovery of the significant substructures that reveal the dynamic local properties of dynamic networks. Also, our method can be used to analyze large scale networks.

Keywords: Biological networks conserved substructures, dynamic networks, significant dynamic substructures, complex networks, protein-protein interaction, clustering algorithm, noise, consensus string, computation complexity, disease