Analysis of Markov influence graphs

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

The research presented in this paper is motivated by the growing interest in the analysis of networks found in the World Wide Web and of social networks. In this paper, we elaborate on the Kemeny constant as a measure of connectivity of the weighted graph associated with a Markov chain. For finite Markov chains, the Kemeny constant can be computed by means of simple algebra via the deviation matrix and the ergodic projector of the chain. Using this fact, we introduce a new decomposition algorithm for Markov chains that splits the graph the Markov chain is defined on into subgraphs, such that the connectivity of the chain measured by the Kemeny constant is maximally decreased. We discuss applications of our decomposition algorithm to influence ranking in social networks, decomposition of a social network into subnetworks, identification of nearly decomposable chains, and cluster analysis.

Original languageEnglish
Pages (from-to)892-904
Number of pages13
JournalOperations Research
Volume67
Issue number3
DOIs
Publication statusPublished - 1 Jan 2019

Fingerprint

Markov processes
Decomposition
Cluster analysis
World Wide Web
Algebra
Markov chain
Graph
Social networks
Connectivity

Keywords

  • Deviation matrix
  • Kemeny decomposition algorithm
  • Markov influence graphs
  • Markov multichains
  • Nearly decomposable Markov chains
  • Social networks

Cite this

@article{ebd46ae011e74380b787e559249770af,
title = "Analysis of Markov influence graphs",
abstract = "The research presented in this paper is motivated by the growing interest in the analysis of networks found in the World Wide Web and of social networks. In this paper, we elaborate on the Kemeny constant as a measure of connectivity of the weighted graph associated with a Markov chain. For finite Markov chains, the Kemeny constant can be computed by means of simple algebra via the deviation matrix and the ergodic projector of the chain. Using this fact, we introduce a new decomposition algorithm for Markov chains that splits the graph the Markov chain is defined on into subgraphs, such that the connectivity of the chain measured by the Kemeny constant is maximally decreased. We discuss applications of our decomposition algorithm to influence ranking in social networks, decomposition of a social network into subnetworks, identification of nearly decomposable chains, and cluster analysis.",
keywords = "Deviation matrix, Kemeny decomposition algorithm, Markov influence graphs, Markov multichains, Nearly decomposable Markov chains, Social networks",
author = "Joost Berkhout and Heidergott, {Bernd F.}",
year = "2019",
month = "1",
day = "1",
doi = "10.1287/opre.2018.1813",
language = "English",
volume = "67",
pages = "892--904",
journal = "Operations Research",
issn = "0030-364X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "3",

}

Analysis of Markov influence graphs. / Berkhout, Joost; Heidergott, Bernd F.

In: Operations Research, Vol. 67, No. 3, 01.01.2019, p. 892-904.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Analysis of Markov influence graphs

AU - Berkhout, Joost

AU - Heidergott, Bernd F.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - The research presented in this paper is motivated by the growing interest in the analysis of networks found in the World Wide Web and of social networks. In this paper, we elaborate on the Kemeny constant as a measure of connectivity of the weighted graph associated with a Markov chain. For finite Markov chains, the Kemeny constant can be computed by means of simple algebra via the deviation matrix and the ergodic projector of the chain. Using this fact, we introduce a new decomposition algorithm for Markov chains that splits the graph the Markov chain is defined on into subgraphs, such that the connectivity of the chain measured by the Kemeny constant is maximally decreased. We discuss applications of our decomposition algorithm to influence ranking in social networks, decomposition of a social network into subnetworks, identification of nearly decomposable chains, and cluster analysis.

AB - The research presented in this paper is motivated by the growing interest in the analysis of networks found in the World Wide Web and of social networks. In this paper, we elaborate on the Kemeny constant as a measure of connectivity of the weighted graph associated with a Markov chain. For finite Markov chains, the Kemeny constant can be computed by means of simple algebra via the deviation matrix and the ergodic projector of the chain. Using this fact, we introduce a new decomposition algorithm for Markov chains that splits the graph the Markov chain is defined on into subgraphs, such that the connectivity of the chain measured by the Kemeny constant is maximally decreased. We discuss applications of our decomposition algorithm to influence ranking in social networks, decomposition of a social network into subnetworks, identification of nearly decomposable chains, and cluster analysis.

KW - Deviation matrix

KW - Kemeny decomposition algorithm

KW - Markov influence graphs

KW - Markov multichains

KW - Nearly decomposable Markov chains

KW - Social networks

UR - http://www.scopus.com/inward/record.url?scp=85068464940&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068464940&partnerID=8YFLogxK

U2 - 10.1287/opre.2018.1813

DO - 10.1287/opre.2018.1813

M3 - Article

VL - 67

SP - 892

EP - 904

JO - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 3

ER -