Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
An Upper Bound on the Burning Number of Graphs Read chapter Read first chapter

2016 | OriginalPaper | Chapter

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

Authors : Konstantin Avrachenkov, Lenar Iskhakov, Maksim Mironov

Published in: Algorithms and Models for the Web Graph

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Modularity of Complex Networks Models
next chapter Subgraphs in Non-uniform Random Hypergraphs
Literature
1.
2.
3.
Avrachenkov, K., Neglia, G., Tuholukova, A.: Subsampling for chain-referral methods. In: Wittevrongel, S., Phung-Duc, T. (eds.) ASMTA 2016. LNCS, vol. 9845, pp. 17–31. Springer, Heidelberg (2016). doi:10.​1007/​978-3-319-43904-4_​2 CrossRef
4.
Basu, S., Bilenko, M., Mooney, R.J.: A probabilistic framework for semi-supervised clustering. In: Proceedings of the 10th ACM SIGKDD, pp. 59–68 (2004)
5.
Boykov, Y., Veksler, O., Zabih, R.: Markov random fields with efficient approximations. In: Proceedings of Computer Vision and Pattern Recognition, pp. 648–655 (1998)
6.
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23(11), 1222–1239 (2001)CrossRef
7.
Brémaud, P.: Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues, Texts in Applied Mathematics, vol. 31. Springer, New York (1998)
8.
Chakrabarti, S., Dom, B., Indyk, P.: Enhanced hypertext categorization using hyperlinks. ACM SIGMOD Rec. 27(2), 307–318 (1998)CrossRef
9.
Ising, E.: Beitrag zur theorie des ferromagnetismus. Z. Phys. A: Hadrons Nucl. 31(1), 253–258 (1925)CrossRef
10.
Kleinberg, J., Tardos, E.: Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields. J. ACM 49(5), 616–639 (2002)MathSciNetCrossRefMATH
11.
Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2009)MATH
12.
Mazel, A.E., Suhov, Y.M.: Random surfaces with two-sided constraints: an application of the theory of dominant ground states. J. Stat. Phys. 64(1–2), 111–134 (1991)MathSciNetCrossRefMATH
13.
14.
Propp, J.G., Wilson, D.B.: Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Struct. Algorithms 9(1–2), 223–252 (1996)MathSciNetCrossRefMATH
15.
Robins, G., Pattison, P., Kalish, Y., Lusher, D.: An introduction to exponential random graph (p*) models for social networks. Soc. Netw. 29(2), 173–191 (2007)CrossRef
16.
Rozikov, U.A., Suhov, Y.M.: Gibbs measures for SOS models on a Cayley tree. Infin. Dimens. Anal. Quantum. Probab. Relat. Top. 9(3), 471–488 (2006)MathSciNetCrossRefMATH
17.
Snijders, T.A.B.: The statistical evaluation of social network dynamics. Sociol. Methodol. 31, 361–395 (2001)CrossRef
18.
Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., Rother, C.: A comparative study of energy minimization methods for Markov random fields with smoothness-based priors. IEEE Trans. Pattern Anal. Mach. Intell. 30(6), 1068–1080 (2008)CrossRef
Metadata
Title
On Mixing in Pairwise Markov Random Fields with Application to Social Networks
Authors
Konstantin Avrachenkov
Lenar Iskhakov
Maksim Mironov
Copyright Year
2016
Book
Algorithms and Models for the Web Graph

Print ISBN: 978-3-319-49786-0

Electronic ISBN: 978-3-319-49787-7

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-49787-7_11

Premium Partner

    Image Credits