Efficient Learning for Selecting Important Nodes in Random Network

• 成果类型: Article
• 署名作者: Li, Haidong; Xu, Xiaoyun; Peng, Yijie; Chen, Chun-Hung
• 署名单位: Peking University; Ateneo de Manila University; Peking University; George Mason University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.2989753
• 发表日期: 2021
• 页码: 1321-1328
• 关键词: Nonlinear systems; Stochastic processes; Adaptive systems; uncertainty; stability analysis; Backstepping; Lyapunov methods; Bayesian learning; dynamic sampling; Markov chain; network; ranking and selection (R& S)

摘要

In this article, we consider the problem of selecting important nodes in a random network, where the nodes connect to each other randomly with certain transition probabilities. The node importance is characterized by the stationary probabilities of the corresponding nodes in a Markov chain defined over the network, as in Google's PageRank. Unlike a deterministic network, the transition probabilities in a random network are unknown but can be estimated by sampling. Under a Bayesian learning framework, we apply the first-order Taylor expansion and normal approximation to provide a computationally efficient posterior approximation of the stationary probabilities. In order to maximize the probability of correct selection, we propose a dynamic sampling procedure, which uses not only posterior means and variances of certain interaction parameters between different nodes, but also the sensitivities of the stationary probabilities with respect to each interaction parameter. Numerical experiment results demonstrate the superiority of the proposed sampling procedure.