Role-dynamics: fast mining of large dynamic networks

To understand the structural dynamics of a large-scale so-cial, biological or technological network, it may be useful to discover behavioral roles representing the main connec-tivity patterns present over time. In this paper, we pro-pose a scalable non-parametric approach to automatically learn the structural dynamics of the network and individual nodes. Roles may represent structural or behavioral pat-terns such as the center of a star, peripheral nodes, or bridge nodes that connect different communities. Our novel ap-proach learns the appropriate structural “role ” dynamics for any arbitrary network and tracks the changes over time. In particular, we uncover the specific global network dynamics and the local node dynamics of a technological, communi-cation, and social network. We identify interesting node and network patterns such as stationary and non-stationary roles, spikes/steps in role-memberships (perhaps indicating anomalies), increasing/decreasing role trends, among many others. Our results indicate that the nodes in each of these networks have distinct connectivity patterns that are non-stationary and evolve considerably over time. Overall, the experiments demonstrate the effectiveness of our approach for fast mining and tracking of the dynamics in large net-works. Furthermore, the dynamic structural representation provides a basis for building more sophisticated models and tools that are fast for exploring large dynamic networks