近日，jbo竞博电竞官方网站数据科学与jbo竞博电竞官方网站胡延庆副教授、马啸教授与孙嘉辰博士生、谢家荣博士后等在世界顶级杂志《自然·通讯》（Nature Communications）上发表了题为“Revealing the predictability of intrinsic structure in complex networks”的研究论文。该研究首次发现网络的结构可预测性与网络结构的最短压缩比特串长度呈线性关系，该理论可以在不依赖于任何结构预测算法的情况下，给出网络结构可预测性的极限。
复杂网络作为一种通用的数据表示形式，广泛存在于生物学、推荐系统、社交媒体等各个领域。它主要用以表示复杂系统内，元素之间不能用简单的数学来很好地描述的相互作用关系。复杂网络结构预测技术在很多领域有广泛的应用。例如，预测细胞内的蛋白质之间或者蛋白质与药物的相互作用关系可以指导更精确的生物学实验，减少实验成本和时间。由于自然界的复杂网络形成过程非常复杂，其结构的预测极具挑战性。近年来学术界提出了许多机器学习方法等相关的预测算法，并致力于提高算法的性能。然而，始终缺乏对于网络本身可预测性（最大可预测极限）的基本理解。其难点在于：网络在形成过程中存在着十分复杂、未知的内外部因素。同时，网络形成后的结构极其复杂，体积庞大，短程反馈回路众多，导致一直没有合适的数学理论来理解网络结构可预测性的内在本质。
在本工作中，该团队利用信息论和统计物理两个领域中熵的相关理论，对网络结构预测极限进行了研究。直观地说，一个可以仅用几个词描述的网络结构意味着它很简单，其边也很容易预测。例如二维晶格或一维链状结构。相反，如果一个网络需要很长的语言才能描述清楚，那么它应该具有非常复杂的结构，其结构很难预测。在计算机领域，任何网络的结构都可以被编码成二进制字符串。这启发了团队探寻最短二进制编码字符串长度，也就是熵，和可预测性之间的关系。
通过研究，该团队发现来自不同领域，很多大小不一的网络，其结构的最短压缩长度和可预测性之间存在一个普遍的线性关系。基于香农信源编码定理，该团队在随机网络上证明了这种线性关系。
进一步，利用这一线性关系，该团队推导出网络结构预测算法的性能上界，揭示出包括机器学习在内的预测算法性能尚存在多大的提升空间。因此，该性能界可用于指导未来在线商业推荐系统、蛋白质相互作用探测等场景中的算法设计。另外，该理论的一个有趣的用途是，可以实现在无需任何预测算法的情况下，通过网络结构压缩数据大小来估计一个网络数据集的商业价值。
该研究受国家自然科学基金面上项目No. 61773412, U1911201等项目支持。
论文下载：https://www.nature.com/articles/s41467-020-14418-6
通讯作者主页：http://www.huyanqing.com
来源：孙嘉辰、胡延庆
编辑：徐瑛
初审：顾颖能
审核：陈凌
审核发布：马啸