复杂网络中的链路预测（四）——极大似然法
本节介绍两种基于极大似然估计的算法。这些算法根据网络结构的产生和组织方式以及目前已经观察到的链路计算网络的似然值，并认为真实的网络使得网络似然值最大，然后再根据网络似然最大化来获得详细的规则和具体的参数。然后，根据这些规则和参数，计算每一对未连接的节点产生连边的可能性。
从实际应用的角度来看，极大似然法的一个明显缺点是它非常耗时。一个设计良好的算法能够在合理的时间内处理多达几千个节点的网络，但肯定无法处理通常由数百万个节点组成的巨大在线网络。此外，极大似然法可能不是最准确的方法之一。然而，极大似然方法为网络组织提供了不能从基于相似性的算法或概率模型中获得的非常有价值的见解。
（1）层次结构模型（Hierarchical Structure Model，HSM）
经验证据表明，许多真实的网络是分层组织的，节点可以被划分为组，每组中数据还可以被再次分组。关注社会和生物网络中固有的层次结构可能会提供一个很聪明的方法来找到缺失的链接。
如上图所示，一个N个节点的网络可以用一个包含N个叶子节点的族谱树表示，这N个叶子节点将由N-1个非叶子节点连接起来。Clauset，Moore和Newman引入了一个简单的模型，其中每个内部节点r与一个概率 相关联，一对节点（叶子）相连的概率等于 ，其中r'是这两个节点的最近共同祖先。
给定一个真实网络G和一个树状图D，设 是G中端点在D中以r为最近共同祖先的边的数量， 和 分别是以r为根的左右子树中叶子节点的数量。那么，树状图D和一组的似然为：
对于固定的D，当 时使得该似然最大化。因此根据最大似然法，有了固定的D，就很容易确定最适合网络G的一组非叶子节点的概率值 。
1.一个N个节点的网络可以用一个包含N个叶子节点的族谱树表示，这N个叶子节点将由N-1个非叶子节点连接起来，其中每个非叶子节点都有一个概率值，则两个叶子节点连接的概率就等于他们最近共同祖先节点的概率值。给定一个族谱树，将网络的似然值最大化，就可以得到非叶子节点的概率值，并由此计算出这一个族谱树所对应的网络最大的似然值。
2.使用马尔科夫链蒙特卡洛方法对网络不同的族谱树进行抽样，使得每个族谱树出现的频次正比于该树对应的最大的网络似然值。两个节点连边的概率就等于所有抽样出来的族谱树中两个节点连边概率的平均值。注意：似然高的族谱树会出现多次，因此对这个平均概率的贡献也大。
3.把平均连边概率看做是相似性框架中的相似性指标 ，按照这个值从大到小排序，排名最高的就是预测的连边。
需要指出的是，层次结构模型在处理具有明显层次结构的网络（如恐怖袭击网络和草原食物链）时具有较高的精确度，但在处理一般性网络时效果并不一定突出。
（2）随机分块模型（Stochastic Block Model，SBM）
随机块模型是最普遍的网络模型之一，其中节点被划分为组，两个节点连接的概率完全取决于它们所属的组，也就是说，同一个组中所有节点的地位是相同的。随机分块模型可以捕获社区结构、role-to-role connections以及其他建立连接的因素。
给定一个划分M，其中每个节点属于一个组，两个分别属于组 和组 的节点相连的概率定义为 （表示组中两个节点连接的概率），则观察到的网络结构的似然为：
其中， 为组和组中节点之间的边数， 表示节点对的数量，其中一个节点在 中，另一个节点在 中。使似然最大化的最优为： 。
根据上图给定一个分区 ，根据公式可得 ， , ，因此，极大似然为：
用 表示所有可能的分区集，根据贝叶斯定理，单个链接的可靠性为
其中 p（M）是一个常数，假设没有关于模型的先验知识。
随机分块模型的效果要好于层次结构模型，同时，该方法还可以剔除网络的错误连边。