[科普中国]-Kronecher模型

在基于网络属性模拟的生成模型中，有一些模型使用矩阵的乘积模拟网络的邻接矩阵的扩展和演化12。其中，Jure Leskovec等研究人员发现可以用矩阵的Kronecker乘积操作来生成网络。

定义在基于网络属性模拟的生成模型中，有一些模型使用矩阵的乘积模拟网络的邻接矩阵的扩展和演化。其中，Jure Leskovec等研究人员发现可以用矩阵的Kronecker乘积操作来生成网络，并且通过实验验证了Kronecker图模型生成的网络可以很好地模拟静态网络的度分布、特征值分布以及动态网络的直径、密度变化的幂律分布等特性。Kronecker积的数学特性使得Kronecker图模型所生成的网络具有良好的可分析性。

Kronecker积是一种矩阵乘积运算。给定大小为 的矩阵 和大小为 的矩阵 ，那么矩阵 和 的Kronecker积表示一个大小为 的矩阵 ，并且

应用由上式可以看到，不同于矩阵的其他乘法，矩阵的Kronecker积是矩阵的扩展操作。那么，将两个图之间的Kronecker积定义为它们的邻接矩阵的Kronecker积，就可以进行图的扩展操作，并且扩展生成的图具有自相似的特性，如下图所示：

1）具有三个节点的链图。

2）Kronecker积的中间状态，表示节点扩展后的结果。

3）的自Kronecker积结果。用表示个的Kronecker积。特别地，表示两个的Kronecker积。

4）的邻接矩阵。

5）的邻接矩阵。

Kronecker图模型的网络生成过程就是对一个初始图，进行多次Kronecker积操作，最终形成。易知的规模为规模的次幂。根据Kronecker积的作用过程可以得知，即使的规模非常小，如的矩阵，最后生成的网络也会具有很好的可变性。为了使模型能够更好地模拟真实世界网络，作者提出了Kronecker图模型的改进模型，即随机Kronecker图模型。在该模型中邻接矩阵中的元素被替换为概率值，这为Kronecker图模型带来了更大的灵活性，使其不仅能够通过改变参数生成具有一定特性的网络，还可以通过参数估计来模拟真实世界中存在的网络。

本词条内容贡献者为:

边凯归 - 北京大学副教授 - 国家973计划“社交网络分析与网络信息传播的基础研究”项目组