【伯克利Payam博士论文】大规模稀疏图的问题探究: 图压缩与负载均衡，268页pdf

在本论文中，我们研究了两类涉及大规模稀疏图的问题，即图数据的压缩问题和网络中的负载均衡问题。我们利用局部弱收敛的框架，或所谓的目标方法来实现这一点。这个框架提供了一个观点，使人们能够理解稀疏图的平稳随机过程的概念。

利用局部弱收敛框架，我们引入了有根图上概率分布的熵概念。这是Bordenave和Caputo将熵概念推广到顶点和边带有标记的图上。这样的标记可以表示关于真实数据的信息。这种熵的概念可以看作是稀疏图数据世界中香农熵率的自然对应。我们通过介绍一种用于稀疏标记图的通用压缩方案来说明这一点。此外，我们研究了图数据的分布式压缩。特别地，我们介绍了一个关于稀疏标记图的Slepian-Wolf定理的版本。

除了研究压缩问题外，我们还研究了网络中的负载均衡问题。我们通过将问题建模为超图来实现这一点，其中每个超边表示承载一个单元负载的任务，而每个顶点表示一个服务器。配置是分配此负载的一种方式。我们研究平衡分配，粗略地说，就是没有需求希望改变其分配的分配。将局部弱收敛理论推广到超图，研究了均衡分配的某些渐近行为，如典型服务器上的渐近经验负荷分布，以及最大负荷的渐近性。

本文所研究的问题可以作为实例来说明局部弱收敛理论和上述熵概念的广泛适用性。事实上，这个框架为稀疏标记图提供了平稳随机过程的观点。时间序列理论在控制理论、通信、信息论和信号处理等领域有着广泛的应用。可以预料，平稳随机过程的组合结构理论，特别是图形，将最终有类似广泛的影响。

https://www2.eecs.berkeley.edu/Pubs/TechRpts/2020/EECS-2020-166.html