一个具有N个节点的无向图G可以用一个实对称的邻接矩阵A(G)=(Aij)N×N表示,其中Aij=1代表节点i与节点j相连,Aij=0代表节点i与节点j之间没有连接。由于A矩阵是实对称矩阵,因此A矩阵具有N个实特征值λ1……λN。图G的谱密度定义为:
同样可以定义邻接矩阵的谱密度k阶矩:
谱密度和网络的拓扑结构密切相关,根据实对称矩阵的性质,,其中Ak是邻接矩阵自乘k次的矩阵,tr(A)表示邻接矩阵的迹,
表示一条长为k的从节点i1出发经过k-1个节点后返回自身的回路。因此,谱密度k阶矩与节点数N的乘积
表示该网络中存在长为k的闭合回路的总数。由于不同的网络有不同的拓扑结构,因此谱密度及谱密度的k阶矩是衡量网络拓扑结构的一个重要的特征参数。
参考文献
[1] Newman M E. The Structure and Function of Complex Networks[J]. Siam Review, 2003, 45(2): 167-256.