Semi-Data-Driven Network Coarsening

Abstract

Network coarsening refers to a new class of graph `zoom-out' operations by grouping similar nodes and edges together so that a smaller equivalent representation of the graph can be obtained for big network analysis. Existing network coarsening methods consider that network structures are static and thus cannot handle dynamic networks. On the other hand, data-driven approaches can infer dynamic network structures by using network information spreading data. However, existing data-driven approaches neglect static network structures that are potentially useful for inferring big networks. In this paper, we present a new semi-data-driven network coarsening model to learn coarsened networks by embedding both static network structure data and dynamic network information spreading data. We prove that the learning model is convex and the Accelerated Proximal Gradient algorithm is adapted to achieve the global optima. Experiments on both synthetic and real-world data sets demonstrate the quality and effectiveness of the proposed method.