Fundamental Research | 彭一杰：随机网络分解与优化问题中的动态学习策略

Fundamental Research 2022-12-31

Fundamental Research 2022年第2卷第3期封面

随机网络分解与优化问题中的动态学习策略

关键词：随机网络，马尔可夫链，仿真优化，贝叶斯学习，动态分解

网络中节点的排序与选择问题（node ranking and selection，nR&S）是许多社会和经济网络中的核心问题，这类问题一般考虑从一个有n个节点的网络中挑选出最重要的m个节点。在万维网中，网页和网页之间的超链接构成了一个网络，谷歌的PageRank对每个关键词都将网页进行排序并列出最重要的一些网页。在体育比赛比如篮球和足球中，队伍之间相互比拼，所得到的胜负关系网络可以帮助赛事组委会决定哪些队伍是种子队伍。在社交网络比如Twitter中，用户之间联系的拓扑结构可以用于用户排序和热度推荐。其他的例子还包括风险投资人选择和学术论文搜索，等等。

在nR&S问题中，网络中的每个节点（网页/队伍/用户）被视为马尔可夫链的一个状态，节点之间以一定的转移概率随机连接在一起。节点的重要程度由马尔可夫链中节点所对应的平稳概率所定义并进行排序。节点的平稳概率表示访问其对应状态的长期时间比例，平稳概率越大意味着相应的节点越重要。此外，马尔可夫链可能存在一些潜在的子类别，这些子类别之间的转移需要间隔很长一段时间。为了促进信息在马尔可夫链节点之间的传播，一个非常明智的做法是对马尔可夫链进行分解并选择每个子类别中最重要的节点（图1）。

在随机网络中，转移概率本质上是节点之间交互参数的函数，是未知的，需要对节点之间的交互进行仿真抽样进而估计转移概率，最终计算和估计平稳概率。一方面，由于仿真抽样有时非常耗时或昂贵，总的抽样预算通常是有限的。另一方面，未知转移概率的数量是随着节点数量平方增长的。因此，对于大规模网络，将每一个转移概率都估计准确在现实中是几乎不可能完成的。样本的随机性不仅会造成交互参数的估计误差，进而导致各个节点平稳概率的估计误差，最终造成节点的错误排序和选择，还可能会造成网络的错误分解或节点的错误分类。

面对这一挑战，本文设计了一个动态学习策略，旨在将马尔可夫链正确分解为若干子链并且综合性地最大化每个子链中最重要节点正确选择概率。该策略在理论上被证明具有统计相合性，并在真实网页数据环境下得到了很好的数值表现。

图1. 问题框架与主要贡献。

以上内容节选自期刊Fundamental Research 2022年第3期发表的文章“H. Li, Y. Peng, X. Xu, et al., Efficient learning for decomposing and optimizing random networks, Fundamental Research 2(3)(2022) 487-495”。

请识别二维码下载PDF原文

主要作者简介

彭一杰 北京大学光华管理学院副教授，博士研究生导师，北京大学人工智能研究院、国家健康医疗大数据研究院兼职研究员。主要研究方向包括仿真建模与优化、金融工程与风险管理、人工智能、健康医疗等。主持国家自然科学基金优秀青年科学基金项目、青年科学基金项目等。

李海东 北京大学工学院在站博士后。主要研究方向包括仿真优化、网络分析和随机控制等。代表性研究成果发表在IEEE Transactions on Automatic Control 等自动控制领域国际顶级期刊。

本期精彩回顾

1. "碳中和"专题 | Fundamental Research 2022年第3期发布

2. Fundamental Research | 江飞：碳卫星监测到的全球前5碳排放国家/地区的碳中和状况

3. Fundamental Research | 耿涌：碳中和背景下中国电力系统转型面临的关键矿产资源约束

4. Fundamental Research | 刘俏：碳本位制——未来的国际货币体系？

5. Fundamental Research | 谭显春：面向碳中和的国家气候治理研究进展

6. Fundamental Research | 陈伟强：实现碳中和目标需要构建“金属-能源协同循环体系”

7. Fundamental Research | 黄刚：碳中和后，地球气候将通往何方？