Abstract
Temporal communities result from a consistent partitioning of nodes across
multiple snapshots of an evolving complex network that can help uncover how
dense clusters in a network emerge, combine, split and decay with time. Current
methods for finding communities in a single snapshot are not straightforwardly
generalizable to finding temporal communities since the quality functions used
for finding static communities have highly degenerate landscapes, and the
eventual partition chosen among the many partitions of similar quality is
highly sensitive to small changes in the network. To reliably detect temporal
communities we need not only to find a good community partition in a given
snapshot but also ensure that it bears some similarity to the partition(s)
found in immediately preceding snapshots. We present a new measure of partition
distance called "estrangement" motivated by the inertia of inter-node
relationships which, when incorporated into the measurement of partition
quality, facilitates the detection of meaningful temporal communities.
Specifically, we propose the estrangement confinement method, which postulates
that neighboring nodes in a community prefer to continue to share community
affiliation as the network evolves. Constraining estrangement enables us to
find meaningful temporal communities at various degrees of temporal smoothness
in diverse real-world datasets. Specifically, we study the evolution of voting
behavior of senators in the United States Congress, the evolution of proximity
in human mobility datasets, and the detection of evolving communities in
synthetic networks that are otherwise hard to find. Estrangement confinement
thus provides a principled approach to uncovering temporal communities in
evolving networks.
Users
Please
log in to take part in the discussion (add own reviews or comments).