北京
来源：市场资讯
（来源：图灵人工智能）
一张社交网络有多少信息？
这个问题听起来应该有一个干净利落的数学回答——毕竟香农在1948年就告诉我们怎么度量信息了。但如果你真的试着用香农的方法去算，你会撞上一堵墙：要度量结构中的信息，你必须先摧毁结构。
把图拆成一组概率，算熵。数字出来了，但两张结构完全不同的图可以给出同一个数字。结构信息在"拆"的那一步就丢了。
这个矛盾不是小问题。早在1953年，Shannon本人就提出了建立结构信息理论的构想，但没有给出方案。半个世纪后，计算机科学家 Brooks Jr. 把结构信息的量化列为计算机科学三大挑战之首，原话是："我认为这个缺失的度量是信息科学理论理解中最根本的缺口。"
然后这个缺口开了60年。
从1955年到2016年，至少七种不同的方法试图解决这个问题。它们全部失败了——而且失败的原因完全相同。
2016年，李昂生在 IEEE Transactions on Information Theory 上发表了一篇38页的论文，提出了一个全新的方案。这个系列要做的事情，是沿着这篇论文的数学脉络，搞清楚一个问题：他们到底做对了什么，让60年没人解决的问题被解决了？
一、1948年：信息有了数学定义
二、一个数字看不见结构
两张结构完全不同的图，香农熵却完全相同
左边是两个独立的三角形——图甚至不连通，一眼就能看出"两个分离的社区"。右边是一个六边形环——所有节点均匀相连，没有任何社区结构。
三、60年间的所有尝试
接下来60年，一代又一代研究者试图修补这个缺口。
第一次尝试：换一种方式拆图（1955–2008）
按距离拆。 Bonchev 和 Trinajstić（1977）换了个角度：用节点之间的最短路距离来定义局部分布：
第二次尝试：不看单张图，看一整类图
Shannon 系综熵沿着系综的思路更进一步。Gibbs 熵只数了系综里有多少张图，Shannon 系综熵则对每条可能的边建模：对每一对节点 ， 是这条边存在的概率， 是不存在的概率。整个系综的熵是：
七条路，同一堵墙
回头看这60年，一个清晰的模式浮现出来：
每一种度量，无论多么精巧，最终都是对某种分布的香农熵。
前三种方法从图里提取分布，后四种方法从图的系综里提取分布。提取方式越来越复杂——按轨道、按距离、按系综、按拉普拉斯矩阵——但拆完之后都是同一个操作：。
为什么所有人都回到了同一个公式？因为这个公式不是一种选择，而是唯一的答案。 香农证明过一个定理：如果你想用一个函数来度量"一个概率分布有多不确定"，并且要求它满足几个最基本的合理性条件（比如概率微小变化时度量也微小变化、均匀分布时不确定性最大），那么满足条件的函数有且只有一个，就是 。
换句话说：一旦你把数据变成了概率分布，你就只剩这一条路可走。 不是研究者们缺乏想象力，而是数学本身封死了所有其他出口。60年间真正的分歧只在于"怎么从图里提取分布"——但只要"提取分布"这一步存在，终点就注定是同一个公式。
所以问题不在于 有什么缺陷——在度量分布的不确定性这件事上，它是完美的，甚至是唯一正确的。问题在于："拆"这个动作就是错的。 结构是不可拆分的——你不能把一张图拆成一堆独立的概率值还指望保留结构信息。
这就像你想理解一首诗的美感，于是你统计了每个字的出现频率，然后用频率分布的熵来度量"诗的信息量"。数字算出来了，但美感早在你做字频统计的那一步就丢了。
那有没有一条不拆的路？ 下一篇，我们看看2016年那篇论文给出了什么答案。
参考
Li, A. & Pan, Y. "Structural Information and Dynamical Complexity of Networks." IEEE Transactions on Information Theory, vol. 62, no. 6, pp. 3290-3339, June 2016. 本文涉及的内容主要来自该论文 §I（Introduction）和 §II（Existing Measures of Graph Entropy）。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
