TY - JOUR
T1 - A mathematical programming approach for sequential clustering of dynamic networks
AU - Silva, Jonathan
AU - Bennett, Laura
AU - Papageorgiou, Lazaros G.
AU - Tsoka, Sophia
PY - 2016/2/16
Y1 - 2016/2/16
N2 - A common analysis performed on dynamic networks is community structure detection, achallenging problem that aims to track the temporal evolution of network modules. Anemerging area in this field is evolutionary clustering, where thecommunity structure of a network snapshot is identified by taking into account both itscurrent state as well as previous time points. Based on this concept, we have developed amixed integer non-linear programming (MINLP) model, SeqMod, that sequentially clusterseach snapshot of a dynamic network. The modularity metric is used to determine the qualityof community structure of the current snapshot and the historical cost is accounted for byoptimising the number of node pairs co-clustered at the previous time point that remain soin the current snapshot partition. Our method is tested on social networks of interactionsamong high school students, college students and members of the Brazilian Congress. Weshow that, for an adequate parameter setting, our algorithm detects the classes that thesestudents belong more accurately than partitioning each time step individually or bypartitioning the aggregated snapshots. Our method also detects drastic discontinuities ininteraction patterns across network snapshots. Finally, we present comparative resultswith similar community detection methods for time-dependent networks from the literature.Overall, we illustrate the applicability of mathematical programming as a flexible,adaptable and systematic approach for these community detection problems.
AB - A common analysis performed on dynamic networks is community structure detection, achallenging problem that aims to track the temporal evolution of network modules. Anemerging area in this field is evolutionary clustering, where thecommunity structure of a network snapshot is identified by taking into account both itscurrent state as well as previous time points. Based on this concept, we have developed amixed integer non-linear programming (MINLP) model, SeqMod, that sequentially clusterseach snapshot of a dynamic network. The modularity metric is used to determine the qualityof community structure of the current snapshot and the historical cost is accounted for byoptimising the number of node pairs co-clustered at the previous time point that remain soin the current snapshot partition. Our method is tested on social networks of interactionsamong high school students, college students and members of the Brazilian Congress. Weshow that, for an adequate parameter setting, our algorithm detects the classes that thesestudents belong more accurately than partitioning each time step individually or bypartitioning the aggregated snapshots. Our method also detects drastic discontinuities ininteraction patterns across network snapshots. Finally, we present comparative resultswith similar community detection methods for time-dependent networks from the literature.Overall, we illustrate the applicability of mathematical programming as a flexible,adaptable and systematic approach for these community detection problems.
UR - http://www.scopus.com/inward/record.url?scp=84958545408&partnerID=8YFLogxK
U2 - 10.1140/epjb/e2015-60656-5
DO - 10.1140/epjb/e2015-60656-5
M3 - Article
AN - SCOPUS:84958545408
SN - 1434-6028
VL - 89
SP - 1
EP - 10
JO - European Physical Journal B
JF - European Physical Journal B
IS - 2
M1 - 39
ER -