Modeling sequences and temporal networks with dynamic community structures

Tiago P. Peixoto, Martin Rosvall

Research output: Contribution to journalArticle

Abstract

Community-detection methods that describe large-scale patterns in the dynamics on and of networks suffer from effects of limited memory and arbitrary time binning. We develop a variable-order Markov chain model that generalizes the stochastic block model for discrete time-series as well as temporal networks. The temporal model does not use time binning but takes full advantage of the time-ordering of the tokens or edges. When the edge ordering is random, we recover the traditional static block model as a special case. Based on statistical evidence and without overfitting, we show how a Bayesian formulation of the model allows us to select the most appropriate Markov order and number of communities.
Original languageEnglish
Number of pages12
JournalPreprint at arxiv
Publication statusPublished - 15 Sep 2015

Fingerprint

Markov processes
Time series
Data storage equipment

Keywords

  • cs.SI
  • cond-mat.stat-mech
  • physics.soc-ph
  • stat.ML

Cite this

Modeling sequences and temporal networks with dynamic community structures. / Peixoto, Tiago P.; Rosvall, Martin.

In: Preprint at arxiv, 15.09.2015.

Research output: Contribution to journalArticle

@article{99237701062c4fae9b1e9c3725ef6e0b,
title = "Modeling sequences and temporal networks with dynamic community structures",
abstract = "Community-detection methods that describe large-scale patterns in the dynamics on and of networks suffer from effects of limited memory and arbitrary time binning. We develop a variable-order Markov chain model that generalizes the stochastic block model for discrete time-series as well as temporal networks. The temporal model does not use time binning but takes full advantage of the time-ordering of the tokens or edges. When the edge ordering is random, we recover the traditional static block model as a special case. Based on statistical evidence and without overfitting, we show how a Bayesian formulation of the model allows us to select the most appropriate Markov order and number of communities.",
keywords = "cs.SI, cond-mat.stat-mech, physics.soc-ph, stat.ML",
author = "Peixoto, {Tiago P.} and Martin Rosvall",
note = "5 Pages, 2 figures, 2 tables + Supplemental material",
year = "2015",
month = "9",
day = "15",
language = "English",
journal = "ArXiv e-prints",
issn = "2331-8422",
publisher = "Cornell University",

}

TY - JOUR

T1 - Modeling sequences and temporal networks with dynamic community structures

AU - Peixoto, Tiago P.

AU - Rosvall, Martin

N1 - 5 Pages, 2 figures, 2 tables + Supplemental material

PY - 2015/9/15

Y1 - 2015/9/15

N2 - Community-detection methods that describe large-scale patterns in the dynamics on and of networks suffer from effects of limited memory and arbitrary time binning. We develop a variable-order Markov chain model that generalizes the stochastic block model for discrete time-series as well as temporal networks. The temporal model does not use time binning but takes full advantage of the time-ordering of the tokens or edges. When the edge ordering is random, we recover the traditional static block model as a special case. Based on statistical evidence and without overfitting, we show how a Bayesian formulation of the model allows us to select the most appropriate Markov order and number of communities.

AB - Community-detection methods that describe large-scale patterns in the dynamics on and of networks suffer from effects of limited memory and arbitrary time binning. We develop a variable-order Markov chain model that generalizes the stochastic block model for discrete time-series as well as temporal networks. The temporal model does not use time binning but takes full advantage of the time-ordering of the tokens or edges. When the edge ordering is random, we recover the traditional static block model as a special case. Based on statistical evidence and without overfitting, we show how a Bayesian formulation of the model allows us to select the most appropriate Markov order and number of communities.

KW - cs.SI

KW - cond-mat.stat-mech

KW - physics.soc-ph

KW - stat.ML

UR - http://opus.bath.ac.uk/52723/

UR - http://www.icms.org.uk/downloads/Dynamical%20networks/Peixoto.pdf

M3 - Article

JO - ArXiv e-prints

JF - ArXiv e-prints

SN - 2331-8422

ER -