网络的结构可预测性与网络结构的最短压缩比特串长度呈线性关系
在本研究工作中,该团队利用信息论和统计物理两个领域中熵的相关理论,对网络结构预测极限进行了研究。直观地说,一个可以仅用几个词描述的网络结构意味着它很简单,其边也很容易预测。例如二维晶格或一维链状结构。相反,如果一个网络需要很长的语言才能描述清楚,那么它应该具有非常复杂的结构,其结构很难预测。在计算机领域,任何网络的结构都可以被编码成二进制字符串。这启发了团队探寻最短二进制编码字符串长度,也就是熵,和可预测性之间的关系。 通过研究,该团队发现来自不同领域,很多大小不一的网络,其结构的最短压缩长度和可预测性之间存在一个普遍的线性关系。基于香农信源编码定理,该团队在随机网络上证明了这种线性关系。 进一步,利用这一线性关系,该团队推导出网络结构预测算法的性能上界,揭示出包括机器学习在内的预测算法性能尚存在多大的提升空间。因此,该性能界可用于指导未来在线商业推荐系统、蛋白质相互作用探测等场景中的算法设计。另外,该理论的一个有趣的用途是,可以实现在无需任何预测算法的情况下,通过网络结构压缩数据大小来估计一个网络数据集的商业价值。
中山大学
2021-04-13