Group detection in mobility traces
Yung‐Chih Chen, Elisha J. Rosensweig, Jim Kurose, Don Towsley · 2010
In a number of network scenarios (including military settings), mobile nodes are clustered into groups, with nodes within the same group exhibiting significant correlation in their movements. Mobility models for such networks should reflect this group structure. In this paper, we consider the problem of identifying the number of groups, and the membership of mobile nodes within groups, from a trace of mobile nodes. We present two clustering algorithms to determine the number of groups and their identities: k-means chain and spectral clustering. Different from traditional k-means clustering, k-means chain identifies the number of groups in a dynamic graph, using a chaining process to keep track of group trajectories over the entire trace. The second approach uses spectral clustering, which uses similarities between node pairs to cluster nodes into groups. We show that the number of groups and node membership can be accurately extracted from traces, particularly when the number of groups is small.