中山大学数据科学与计算机学院研究人员首次发现网络的结构可预测性与网络结构的最短压缩比特串长度呈线性关系。该理论可在不依赖于任何结构预测算法的情况下，给出网络结构可预测性的极限。相关研究近日发表于《自然—通讯》。
复杂网络作为一种通用的数据表示形式，广泛存在于生物学、推荐系统、社交媒体等各个领域。复杂网络结构预测技术也应用广泛。而学术界始终缺乏对于网络本身可预测性（最大可预测极限）的基本理解。
研究团队利用信息论和统计物理两个领域中熵的相关理论，对网络结构预测极限进行了研究。通过研究，该团队发现来自不同领域很多大小不一的网络，其结构的最短压缩长度和可预测性之间存在一个普遍的线性关系。基于香农信源编码定理，该团队在随机网络上证明了这种关系，并利用其推导出网络结构预测算法的性能上界，揭示出包括机器学习在内的预测算法性能尚存在多大的提升空间。
因此，该性能界可用于指导未来在线商业推荐系统、蛋白质相互作用探测等场景中的算法设计。
相关论文信息：https://doi.org/10.1038/s41467-020-14418-6
原文链接：http://paper.sciencenet.cn/sbhtmlnews/2020/3/353811.shtm?id=353811
