网络投影法分析：基准点选取与精度提升

网络投影法分析的原理［1］是：假定需要分析的网络结构未知，首先将待分析的网络中的所有节点投影到一个高维测量空间，并把原网络对应到高维空间的一个点分布；接着引入数据分析中的主分量分析法（Principal Component Analysis，PCA）［2］对点分布数据进行降维度处理，以便挖掘生成的点分布的结构；然后用K-means聚类方法对点分布数据进行聚类分析，得到网络的社团结构，再依据分析得到的社团结构特征反推原网络结构属性，如图6-1所示。

图6-1 网络投影法示意图［3］

一、网络投影法的改进

已知的网络投影法在处理网络数据时，首先要把网络中的节点投影到一个高维的测量空间，这一步的关键是选取原网络中的一部分点作为基准点，以便于测量其他节点的影响力。随机选取基准点的方式具有很大的不确定性，这导致的直接后果就是每次计算出的结果差异性较大，可能会出现以下几种情况，本文对这几种情况都做了具体的尝试，得到如下的结果：

（1）选取的基准点都是在原网络中度值非常小的节点，这些节点在原网络中的影响力非常小，把它们作为基准点在测量其他节点影响力的时候精度非常低，这就导致整个网络投影法的精度大幅度下降，甚至失效。

（2）选取的基准点既有在原网络中度值很小的节点，也有在原网络中度值比较大的节点。这种情况又可以细分为两种情况：一种就是选取的基准点中度值小的节点的数量≥度值大的节点的数量；另一种就是选取的基准点中度值小的节点的数量≤度值大的节点的数量。这种情况导致网络投影法的精度有所提高，但还是不能达到预期。

（3）选取的基准点都是在原网络中度值很大的节点，这些节点在原网络中都有很多的连接，有非常大的影响力，把这些节点作为基准点，能够非常有效地提高网络投影法的精度，得到比较符合预期的结果。

综合以上，我们可以看出，网络投影法的精度与基准点的选择有着密不可分的关系，选取的基准点在原网络中度值大的节点的数量越多，网络投影法的精度就越高。对此本章将基准点的选取方式改进为直接选取原网络中度值最大的部分节点，以这些基准点作为测量其他节点影响力的依据。

二、改进后的网络投影法流程

这里对本章第三章所建立的模型的数据分析进行处理，详细流程如下：

（1）把原网络节点投影到高维测量空间。首先测量节点对网络的影响力度，然后根据节点对网络的影响力度将节点投影到测量空间。具体步骤如下：(www.xing528.com)

第一步：选取K个度值最大的点作为测量的基准点，然后计算当前节点i到k个度值较大的测量基准点的图论距离dij，其中j=1，2，3，…，k。

第二步：节点间的影响力大小与当前节点i到k个度量基准点的距离大小成反比，计算距离的倒数1/dij作为节点间影响力的度量。

第三步：节点i对k个基准点的影响力向量为li=｛1/di1，1/di2，1/di3，…，1/dip｝。由于测量基准点是从原网络所有的节点中选出来的度值最大的k个节点，基准点j可以看作其所在网络的局部的代表节点，数值1/dij可以看作节点i对网络局部的影响力，因此向量li就可以看作节点i对整个网络影响力的近似度量值。我们这里把向量li叫作节点i的网络影响力。

第四步：对原网络中所有N个节点逐个做上述影响力测量，可以得到N个节点测量值，将这N个影响力向量即网络的N个节点投影到一个k维测量空间，使原网络对应到k维测量空间中的一个点分布。

（2）用主分量分析法（PCA）对点分布数据降维。在节点投影的第四步中，我们得到了与原网络对应的测量空间的点分布，由于选取的k个基准点是从原网络中挑选出来并关联在一起的，因此测量出来的值也是关联的。用主分量分析法对相关数据去做相关处理，抽取点分布的主结构信息。具体步骤如下：

第一步，在得到N个网络节点的影响力向量li后，构建k×N的测量矩阵L=［l1，l2，l3，…，ln］。矩阵中每行对应一个网络的基准点，每列对应网络中的一个节点。

第二步，对矩阵L在k维测量空间RK做归一化处理，可以得到L的标准化矩阵X=［x1，x2，x3，…xN］，矩阵中每行的均值为0，方差为1。

第三步，计算X的协方差矩阵，C=XXT，对C做奇异值分解，根据奇异值分解定理，X=UΣVT，其中U和V是正交矩阵。

C=XXT=（UΣVT）（VΣUT）=UAUT

第四步，选择正交矩阵U的前p列记为Up，计算Up的列对应于X的协方差矩阵C的最大的p个特征值对应的特征向量，然后将标准化矩阵X向矩阵Up上投影，得到结果R=UpX=［r1，r2，r3，…，rN］即为X的p维投影。

通过以上四步我们得到了原网络生成的点分布的低维主结构分布，并且对标准化矩阵X进行了去相关处理。

（3）用K-means聚类方法对所得到的低维数据进行聚类分析，将同一类的点所对应的原网络的节点划分为一个社团，根据聚类结果来决定网络的社团结构。K聚类方法的思想为：对一组要聚成K类的数据点，随机地选择K个数据点作为类中心，按照最近邻准则对数据点聚类。在得到K类数据点后，重新计算类中心，然后再聚类，如此迭代，直至类中心不再变化为止。