A mathematical programming approach for sequential clustering of dynamic networks

Jonathan C. Silva, Laura Bennett, Lazaros G. Papageorgiou and Sophia Tsoka ()
Additional contact information
Jonathan C. Silva: Department of Informatics
Laura Bennett: Centre for Process Systems Engineering, Department of Chemical Engineering, University College London
Lazaros G. Papageorgiou: Centre for Process Systems Engineering, Department of Chemical Engineering, University College London
Sophia Tsoka: Department of Informatics

The European Physical Journal B: Condensed Matter and Complex Systems, 2016, vol. 89, issue 2, 1-10

Abstract: Abstract A common analysis performed on dynamic networks is community structure detection, a challenging problem that aims to track the temporal evolution of network modules. An emerging area in this field is evolutionary clustering, where the community structure of a network snapshot is identified by taking into account both its current state as well as previous time points. Based on this concept, we have developed a mixed integer non-linear programming (MINLP) model, SeqMod, that sequentially clusters each snapshot of a dynamic network. The modularity metric is used to determine the quality of community structure of the current snapshot and the historical cost is accounted for by optimising the number of node pairs co-clustered at the previous time point that remain so in the current snapshot partition. Our method is tested on social networks of interactions among high school students, college students and members of the Brazilian Congress. We show that, for an adequate parameter setting, our algorithm detects the classes that these students belong more accurately than partitioning each time step individually or by partitioning the aggregated snapshots. Our method also detects drastic discontinuities in interaction patterns across network snapshots. Finally, we present comparative results with 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.

Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1140/epjb/e2015-60656-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurphb:v:89:y:2016:i:2:d:10.1140_epjb_e2015-60656-5

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/10051

DOI: 10.1140/epjb/e2015-60656-5

Access Statistics for this article

The European Physical Journal B: Condensed Matter and Complex Systems is currently edited by P. Hänggi and Angel Rubio

More articles in The European Physical Journal B: Condensed Matter and Complex Systems from Springer, EDP Sciences
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().