On Mixing in Pairwise Markov Random Fields with Application to Social Networks

Citation

Avrachenkov, Konstantin; Iskhakov, Lenar; & Mironov, Maksim (2016). On Mixing in Pairwise Markov Random Fields with Application to Social Networks. Algorithms and Models for the Web Graph: 13th International Workshop, WAW 2016. Montreal, QC, Canada: Springer International Publishing.

Abstract

We consider pairwise Markov random fields which have a number of important applications in statistical physics, image processing and machine learning such as Ising model and labeling problem to name a couple. Our own motivation comes from the need to produce synthetic models for social networks with attributes. First, we give conditions for rapid mixing of the associated Glauber dynamics and consider interesting particular cases. Then, for pairwise Markov random fields with submodular energy functions we construct monotone perfect simulation.

URL

http://dx.doi.org/10.1007/978-3-319-49787-7_11

Reference Type

Conference proceeding

Book Title

Algorithms and Models for the Web Graph: 13th International Workshop, WAW 2016

Author(s)

Avrachenkov, Konstantin
Iskhakov, Lenar
Mironov, Maksim

Editor(s)

Bonato, Anthony Graham Fan Chung Prałat Paweł

Year Published

2016

Pages

127-139

Publisher

Springer International Publishing

City of Publication

Montreal, QC, Canada

ISSN/ISBN

978-3-319-49787-7

DOI

10.1007/978-3-319-49787-7_11

Reference ID

9042