Change-point detection in networks
Here is a demo of our method for
detecting change points in the large-scale structure of evolving networks (code).
The data is from the
MIT Reality Mining experiment in which 97 MIT faculty and graduate students carried smart phones that recorded proximity
data continuously via Bluetooth scans over 35 weeks.
From the raw scan data, we extracted a sequence of weekly networks, in which an edge denotes physical proximity to one of
the 97 subjects at some point that week.
The results using our method are shown below, which includes the identified change points,
the inferred GHRG dendrograms, and highlighted external events.
The GHRG method identifies nearly all of the known external events, along with a few additional change points, e.g., one week before and one week after Sponsor week.
This fact agrees well with the social dynamics of Sponsor week, an event involving 75 of the subjects and which typically shifts work schedules dramatically as they seek to meet
deadlines and project goals.
Additionally, the GHRG method finds more change points in the Fall semester than in the Spring. Examining the dendrograms themselves, we find that the changes in the
inferred structures in the Fall are much more dramatic than in the Spring. This agrees with the fact that 35 of the subjects were new students in the Fall semester and thus still
establishing their social patterns. By the Spring semester, these patterns had largely stabilized, and the large perturbation of Sponsor week was absent.
Overall, the GHRG both recovers known events, highlights additional changes, and provides an interpretable basis for discovering new patterns within this evolving network.