On a walk in the hills above our house the other day, I watched two flocks of birds merge, fly around as one flock for a few minutes, and then separate into two again. While I assume that the merging and unmerging started and ended with roughly the same individual birds in their respective flocks, it is practically impossible to verify this as a casual observer.

Such an analysis of social networks in the physical world is frequently very tedious, but the emergence of their counterparts based on online connections has opened up a treasure trove of data. The authors investigate the changes in communities within social networks, in particular for dynamic networks with potentially abrupt changes. In a city neighborhood with a large sports arena, the community of people as defined by their physical presence in the neighborhood will undergo abrupt changes at the beginning and end of a game.

By analyzing features of adjacency matrices for an overall set of individuals, such as the Frobenius, Gram, and Eigen norms, they utilize a classifier to determine the nature of a change. If an abrupt change is detected, an algorithm relying on the most recent snapshot of the observed links determines the underlying community. For gradual change, an incremental algorithm to identify incoming and departing members over successive snapshots is better suited.

Experiments on generated and real-life networks (such as friends on Facebook and citation links on arXiv) confirm efficiency improvements over previous methods, especially when dealing with abrupt changes. For large-scale networks with millions of nodes, such improvements can lead to new avenues of research. Now if we could convince birds to join online networks, we could confirm if those flocks just hang out together for a while and then continue as before, or if there is an abrupt change in their memberships.