Intrinsically dynamic communities from evolving, directed network data

By

Bivas Mitra, Lionel Tabourier and Camille Roth

Computer Networks, Vol. 56(3), 2012.

Abstract

Community finding algorithms for networks have recently been extended to dynamic data.
Most of these recent methods aim at exhibiting community partitions from successive
graph snapshots and thereafter connecting or smoothing these partitions using clever
time-dependent features and sampling techniques. These approaches are nonetheless
achieving longitudinal rather than dynamic community detection. We assume that commu-
nities are fundamentally defined by the repetition of interactions among a set of nodes over
time. According to this definition, analyzing the data by considering successive snapshots
induces a significant loss of information: we suggest that it blurs essentially dynamic phe-
nomena—such as communities based on repeated inter-temporal interactions, nodes
switching from a community to another across time, or the possibility that a community
survives while its members are being integrally replaced over a longer time period. We
propose a formalism which aims at tackling this issue in the context of time-directed data-
sets (such as citation networks), and present several illustrations on both empirical and
synthetic dynamic networks. We eventually introduce intrinsically dynamic metrics to
qualify temporal community structure and emphasize their possible role as an estimator
of the quality of the community detection—taking into account the fact that various empir-
ical contexts may call for distinct ‘community’ definitions and detection criteria.

This entry was posted in Papers