一种网络异质多维标度方法

摘要

一种网络异质多维标度方法，包括如下步骤：步骤1：利用网络节点度值给出网络节点特性向量；步骤2：在网络不等式约束下，结合网络异质最短距离的定义和网络节点特性向量计算节点间相似度矩阵；步骤3：利用该异质距离矩阵和网络节点特性向量定义距离矩阵，其中的距离满足三角不等式；步骤4：基于获得的距离矩阵，步骤5：由各节点在欧氏空间中的坐标计算节点间嵌入异质距离，获得嵌入异质距离矩阵；步骤6：选择与原始网络相同连边数量的排序靠前的节点对，并对它们进行连接，从而构建嵌入网络，该嵌入网络与原始网络具有相同数量的连边，比较两个网络并计算嵌入误差。本发明全面考虑了广义网络距离和异质网络中节点特性的差异。

主权项

一种网络异质多维标度方法，其特征在于：所述标度方法包括如下步骤：步骤1：设模拟阿波罗网络为G＝(V,E)，其节点集和连边集分别为V＝{v₁,v₂,…,v_N}和连边数被简单表示为|E|；该网络也可用一个邻接矩阵A＝[a_ij]_N×N来表示，其满足如果(v_i,v_j)∈E则a_ij＝1，否则a_ij＝0；步骤2：定义节点v_i和v_j间异质最短路径长度为l_ij，表示该两个节点之间任意路径的最小权重和，包括两端节点v_i和v_j；基于此，定义异质距离如下：$h_{ij}=\frac{(1-2\eta )({\theta }_i+{\theta }_j)+2{\mathrm{\eta l}}_{ij}}{{\theta }_i+{\theta }_j}.---\left(1\right)$其中η为距离参数；θ_i和θ_j点分别为节点v_i和v_j的内在属性；由于如果v_i和v_j相连，则$l_{ij}={\theta }_i+{\theta }_j\Rightarrow h_{ij}=1,$而如果它们不相连，则有$l_{ij}>{\theta }_i+{\theta }_j\Rightarrow h_{ij}>1,$故该异质距离满足网络不等式；步骤3：利用获得的异质距离矩阵H＝[h_ij]_N×N，计算距离矩阵D＝[d_ij]_N×N，其中的元素定义如下：d_ij＝h_ij(θ_i+θ_j).                 (2)对任意三个节点v_i，v_j，和v_k，假设d_ik≤d_jk≤d_ij，而根据异质最短路径长度的定义，我们有l_ij≤l_ik+l_jk‑θ_k，结合(1)式和(2)式进而可得：d_ij＝(1‑2η)(θ_i+θ_j)+2ηl_ij≤(1‑2η)(θ_i+θ_j)+2η(l_ik+l_jk‑θ_k)≤(1‑2η)(θ_i+θ_j)+2η(l_ik+l_jk‑θ_k)+2(1‑η)θ_k＝[(1‑2η)(θ_i+θ_k)+2l_ik]+[(1‑2η)(θ_j+θ_k)+2l_jk]＝d_ik+d_jk.                         (3)而(3)式意味着根据以上方法计算获得的节点间距离满足三角不等式；步骤4：基于获得的距离矩阵，按以下方法计算欧氏空间中节点的坐标；定义B＝[b_ij]_N×N为中心化内积矩阵，其元素由如下(4)式计算得到：$b_{ij}=\frac{1}{2}\left(-d_{ij}^2+\frac{1}{N}\underset{j=1}{\overset{N}{\Sigma }}{d}_{ij}^2+\frac{1}{N}\underset{i=1}{\overset{N}{\Sigma }}{d}_{ij}^2-\frac{1}{N^2}\underset{i=1}{\overset{N}{\Sigma }}\underset{j=1}{\overset{N}{\Sigma }}{d}_{ij}^2\right).---\left(4\right)$令λ₁≥λ₂≥…≥λ_r>0是中心化内积矩阵B的前r个最大的正特征值，e₁,e₂,…,e_r是对应的单位特征向量，即||e₁||＝||e₂||＝…＝||e_r||＝1；从而坐标矩阵可通过如下(5)式计算获得：$X=[\sqrt{{\lambda }_1}{e}_1,\sqrt{{\lambda }_2}{e}_2,...,\sqrt{{\lambda }_r}{e}_r],---\left(5\right)$其中，X^T中的第i列表示节点v_i在r维欧氏空间的坐标；步骤5：利用网络节点在r维欧氏空间的坐标，计算嵌入异质距离矩阵其元素由(6)式计算获得：$h_{ij}^{*}=\frac{\left|\right|x_i-x_j\left|\right|}{{\theta }_i+{\theta }_j}.---\left(6\right)$x_i和x_j分别为X^T中的第i列和第j列，表示网络节点v_i和v_j在r维欧氏空间的坐标；步骤6：将节点对按照它们之间的嵌入异质距离从小到大排序，选择最靠前|E|对节点建立连接，从而构建嵌入网络G^*＝(V,E^*)，因而嵌入网络具有与原始网络相同数量的连边数，即|E^*|＝|E|；定义该嵌入网络的邻接矩阵为则相对嵌入误差由如下(7)式定义：$ϵ=\frac{{\Sigma }_{i=1}^N{\Sigma }_{j=i+1}^N|a_{ij}-a_{ij}^{*}|}{2{\Sigma }_{i=1}^N{\Sigma }_{j=i+1}^N{a}_{ij}}.---\left(7\right)$