Efficient learning for decomposing and optimizing random networks

Haidong Li; Yijie Peng; Xiaoyun Xu; Bernd F. Heidergott; Chun Hung Chen

doi:10.1016/j.fmre.2022.01.018

Efficient learning for decomposing and optimizing random networks

Haidong Li, Yijie Peng^*, Xiaoyun Xu, Bernd F. Heidergott, Chun Hung Chen

^*Corresponding author for this work

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

In this study, we consider the problem of node ranking in a random network. A Markov chain is defined for the network, and its transition probability matrix is unknown but can be learned by sampling random interactions among nodes. Our objective is to decompose the Markov chain into several ergodic classes and select the best node in each ergodic class. We propose a dynamic sampling procedure, which gives a probability guarantee on correct decomposition and maximizes a weighted probability of correct selection of the best node in each ergodic class. Numerical experiment results demonstrate the efficiency of the proposed sampling procedure.

Original language	English
Pages (from-to)	487-495
Number of pages	9
Journal	Fundamental Research
Volume	2
Issue number	3
Early online date	3 Feb 2022
DOIs	https://doi.org/10.1016/j.fmre.2022.01.018
Publication status	Published - May 2022

Bibliographical note

Publisher Copyright:
© 2022

Funding

This work was supported in part by the National Natural Science Foundation of China (NSFC) under Grants 72022001, 92146003, 71901003.

Keywords

Bayesian learning
Dynamic decomposition
Markov chain
Random network
Ranking and selection

Access to Document

10.1016/j.fmre.2022.01.018

Persistent URL (handle)

Persistent link

Cite this

@article{d205081ac0ac4f9da826f4ef2d343725,

title = "Efficient learning for decomposing and optimizing random networks",

abstract = "In this study, we consider the problem of node ranking in a random network. A Markov chain is defined for the network, and its transition probability matrix is unknown but can be learned by sampling random interactions among nodes. Our objective is to decompose the Markov chain into several ergodic classes and select the best node in each ergodic class. We propose a dynamic sampling procedure, which gives a probability guarantee on correct decomposition and maximizes a weighted probability of correct selection of the best node in each ergodic class. Numerical experiment results demonstrate the efficiency of the proposed sampling procedure.",

keywords = "Bayesian learning, Dynamic decomposition, Markov chain, Random network, Ranking and selection",

author = "Haidong Li and Yijie Peng and Xiaoyun Xu and Heidergott, \{Bernd F.\} and Chen, \{Chun Hung\}",

note = "Publisher Copyright: {\textcopyright} 2022",

year = "2022",

month = may,

doi = "10.1016/j.fmre.2022.01.018",

language = "English",

volume = "2",

pages = "487--495",

journal = "Fundamental Research",

issn = "2667-3258",

publisher = "Elsevier BV",

number = "3",

}

TY - JOUR

T1 - Efficient learning for decomposing and optimizing random networks

AU - Li, Haidong

AU - Peng, Yijie

AU - Xu, Xiaoyun

AU - Heidergott, Bernd F.

AU - Chen, Chun Hung

PY - 2022/5

Y1 - 2022/5

N2 - In this study, we consider the problem of node ranking in a random network. A Markov chain is defined for the network, and its transition probability matrix is unknown but can be learned by sampling random interactions among nodes. Our objective is to decompose the Markov chain into several ergodic classes and select the best node in each ergodic class. We propose a dynamic sampling procedure, which gives a probability guarantee on correct decomposition and maximizes a weighted probability of correct selection of the best node in each ergodic class. Numerical experiment results demonstrate the efficiency of the proposed sampling procedure.

AB - In this study, we consider the problem of node ranking in a random network. A Markov chain is defined for the network, and its transition probability matrix is unknown but can be learned by sampling random interactions among nodes. Our objective is to decompose the Markov chain into several ergodic classes and select the best node in each ergodic class. We propose a dynamic sampling procedure, which gives a probability guarantee on correct decomposition and maximizes a weighted probability of correct selection of the best node in each ergodic class. Numerical experiment results demonstrate the efficiency of the proposed sampling procedure.

KW - Bayesian learning

KW - Dynamic decomposition

KW - Markov chain

KW - Random network

KW - Ranking and selection

UR - https://www.scopus.com/pages/publications/85124811931

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

U2 - 10.1016/j.fmre.2022.01.018

DO - 10.1016/j.fmre.2022.01.018

M3 - Article

AN - SCOPUS:85124811931

SN - 2667-3258

VL - 2

SP - 487

EP - 495

JO - Fundamental Research

JF - Fundamental Research

IS - 3

ER -

Efficient learning for decomposing and optimizing random networks

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this