在基于网路属性模拟的生成模型中,有一些模型使用矩阵的乘积模拟网路的邻接矩阵的扩展和演化。其中,Jure Leskovec等研究人员发现可以用矩阵的Kronecker乘积操作来生成网路。
基本介绍
- 中文名:Kronecker图模型
- 外文名:Kronecker Graph Model
定义
在基于网路属性模拟的生成模型中,有一些模型使用矩阵的乘积模拟网路的邻接矩阵的扩展和演化。其中,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图模型带来了更大的灵活性,使其不仅能够通过改变参数生成具有一定特性的网路,还可以通过参数估计来模拟真实世界中存在的网路。







