一个预测社交网络演化过程和网络性质的方法

摘要

本发明提出了一个预测社交网络演化过程和网络性质的方法，属于计算机技术领域。本方法初始设定完全图的社会网络，对每个新加入的节点，根据优先连接概率从当前网络中选取若干节点与新加入节点连接，然后计算当前网络中的每个节点的聚集力和网络的聚集力总和，并选取若干节点作为中心节点，将每个中心节点的任意两个好友节点连边。节点的聚集力描述在网络中，某一个节点能够使它的两个还没有成为好友关系的好友连边的能力。网络的聚集力总和描述了社交网络中所有节点的凝聚力总和。本发明方法可以较为准确地模拟并预测各种社交网络的演化过程，在一定程度上弱化了BA模型的弊端，生成接近于真实的社交网络。

说明书

技术领域

本发明提出一个用于预测社交网络演化过程和网络性质的模型，属于计算机技术领域和 社交网络技术领域。

背景技术

近年来对于社交网络演化的研究非常热，研究者也提出了一些模型。然而这些模型并不 能适用于预测各种类型的社交网络演化方向，目前，在该领域还没有一个公认的较好的能够 准确预测网络未来演化方向的模型。

现有一个比较经典的社交网络演化模型是BA模型。在BA模型中，初始时刻，假设系 统中已存在少量节点，在之后的每一个时间间隔中都新增一个节点，并将该节点与网络中已 存在的节点进行连接，连接时按优先连接进行。这样，BA网络就演化为标度不变的状态，即 节点度分布为幂指数等于3的幂律分布。但是，BA模型也存在着一定的问题，BA模型的聚 类系数很小，特别当网络规模很大时，网络的聚类系数接近于0，这与真实网络具有较大聚 类系数的特点并不相符合。本发明在充分研究BA模型的优缺点后，发现虽然BA模型生成 网络度分布与实际社交网络度分布相似，但是其聚类系数较小，与实际社交网络特点不符， 进一步深入分析聚类系数关于度的分布之后，发现BA模型生成的网络与真实的社交网络有 很大的差异，可以说根本不存在局部性，而局部性是社交网络中非常重要的一个特性。

发明内容

本发明针对BA模型生成的网络与真实社交网络存在很大差异的问题，提供了一种预测 社交网络演化过程和网络性质的方法，通过分析实际社交网络特点，在BA模型中引入三元 闭包的思想，改进了BA模型。三元闭包即通过在拥有共同好友的两节点间加边，以达到增 加聚类系数，改善模型的局部性的效果。

本发明提供的预测社交网络演化过程和网络性质的方法，包括如下步骤：

步骤1：将社交网络用无向无权图表示，设初始网络中每两个节点都相连，设n表示网 络当前的节点个数；

步骤2：新加入一个节点时，根据优先连接概率从当前网络中选取k个节点与新加入节 点相连接；在连接完成后，更新网络的节点数n'=n+1；

节点i的优先连接概率H(i)为：其中，d_i、d_j分别表示节点i、节点j的度；

步骤3：更新n=n'，计算当前网络中的每个节点的聚集力和网络的聚集力总和；

节点i的聚集力PoA(i)为：$\mathrm{PoA}\left(i\right)=\left(\begin{array}{c}{d}_i^{\alpha },d_i<K\\ K^{\alpha },d_i\ge K\end{array}\right);$其中，α是关于网络特点的参数，K是 节点度的阈值；

网络的聚集力总和SPoA为：

步骤4：从当前网络中选出c个节点作为中心节点，节点i被选取的概率对于每个中心节点，以等概率任取它的两个好友节点连边；

步骤5：检查当前网络的规模是否已经符合设定的要求，若是，结束本方法，否则跳至 步骤2执行。

本发明的预测社交网络演化过程和网络性质的方法，在一定程度上弱化了BA模型的弊 端，生成接近于真实的社交网络，较好地展现并预测网络演化过程。本发明方法在保证节点 度分布为幂指数为3的幂律分布的前提下，实现了增加聚类系数，改善模型局部性的效果， 更加接近实际社交网络的性质。

附图说明

图1是本发明的预测社交网络演化过程和网络性质的方法的流程示意图；

图2为本发明的预测社交网络演化过程和网络性质方法的原理示意图；

图3为本发明的预测社交网络演化过程和网络性质方法的效果图。

具体实施方式

下面将结合附图和实施例来说明本发明的技术方案。

本发明中用无向无权图表示社交网络，定义无向无权图G=(V,E)，图中节点总数为n，边 总数为m。图G中的节点就表示社交网络中的一个个体，一条边就表示两个个体之间有联系， 即一条边连接的两个个体为好友关系。

本发明方法引入了节点的聚集力（Power of Aggregation）和网络的聚集力总和(Sum of  Power of Aggregation)两个概念。

（1）节点的聚集力；节点的聚集力描述在网络中，某一个节点能够使它的两个还没有成 为好友关系的好友连边的能力。节点的聚集力在真实的社交过程中体现为一个人的凝聚力， 即某个人可以让他的两个不相识的朋友相互成为好友的能力。

本发明对于节点i的聚集力，用聚集力函数PoA(i)表示：$\mathrm{PoA}\left(i\right)=\left(\begin{array}{c}{d}_i^{\alpha },d_i<K\\ K^{\alpha },d_i\ge K\end{array}\right).$

其中，d_i表示节点i的度，α是关于网络特点的参数，K是节点度的阈值。

节点i的度d_i是指和节点i相关联的边的条数。

参数α的值可以通过已有的网络数据来确定，将目前已有的网络数据作为输入数据代入 本发明改进的BA模型，调整α和K，使模型模拟出来的网络性质与已知网络性质相符，然 后利用得到的α和K来预测网络的未来演化。K是度的阈值，根据网络特点确定阈值大小， 例如对于人人网的数据，设置阈值K为100。当度高于阈值K时，随着度的增加，节点的聚 集力不再增大。

（2）网络的聚集力总和；网络的聚集力总和描述了社交网络中所有节点的凝聚力总和。

网络的聚集力总和用SPoA表示：

$\mathrm{SPoA}=\underset{i=1}{\overset{n}{\Sigma }}\mathrm{PoA}\left(i\right)$

由以上定义，引入三元闭包思想后，从网络中以概率选取中心节点a，在与 节点a相连的边中以相等概率随机取两个节点，在其之间连边，构成三元闭包，该方案可以 有效将生成网络的聚类系数分布曲线向实际网络聚类系数分布曲线靠近。

由于部分社交网络还存在度较大节点聚类系数较小的问题，因此在形成三元闭包过程中 需要引入一个阈值K，根据具体网络特点，当某节点i的度大于阈值K时，凝聚力统一采用K^α， 以降低其应有节点凝聚力，达到降低度较大节点聚类系数较小的问题。

本发明方法以BA模型为基础，利用BA模型的增长机制，并以生成三元闭包作为模型 中部分边生成的动力。本发明方法可以在一定程度上弱化BA模型的弊端，可以生成接近于 真实的社交网络，较好地展现并预测网络演化过程。如图1所示，为本发明提供的预测社交 网络演化过程和网络性质的方法的流程图。

步骤1：将社交网络用无向无权图表示，设初始网络当前包含的节点数为m₀，每两个节 点都相连，即网络初始为一个m₀阶的完全图。初始网络可标记为

步骤2：取新加入的一个节点v，根据优先连接概率H(i)，从当前网络中选取节点i与新 加入节点v连边。本步骤共选出k个节点与新加入节点v相连接。k为正整数，具体值依据网 络特点来设定，利用已知的网络数据来模拟确定，一般在1～20范围内。

节点i的优先连接概率H(i)为：

$H\left(i\right)=\frac{d_i}{\underset{j=1}{\overset{n}{\Sigma }}{d}_j}$

其中，d_i、d_j分别表示节点i、节点j的度。优先连接概率表示新加入节点v与节点i连边 的概率与节点i的度d_i成正比。

对同一个网络，参数k、α和K是固定的，都是利用已知的网络数据进行模拟后确定。

在连接完成后，更新网络的节点数n'=n+1，生成网络N_n'。

步骤3：更新n=n'，计算当前网络N_n中每一个节点i的聚集力PoA(i)和网络的聚集力总 和SPoA。

步骤4：建立三元闭包。根据概率P(i)从当前网络中选出c个节点作为中心节点。

节点i被选取的概率P(i)为：$P\left(i\right)=\frac{\mathrm{PoA}\left(i\right)}{\mathrm{SPoA}},i=\mathrm{1,2},...,n.$

对于每一个中心节点，以等概率任取它的两个好友节点连边。

c为正整数，同样依据网络特点来设定，利用已知的网络数据来模拟确定。

步骤5：检查当前网络的规模是否已经符合设定的要求，若是，则结束本方法，否则， 跳至步骤2执行。网络的规模即指网络中的节点数量。

例如设定的网络规模要求为Q，当网络当前的节点数目n达到Q时，则停止增加节点。

如图2所示，节点B和节点C有共同好友A，因此B和C成为好友的几率要远大于与B 没有共同好友的D成为好友的概率，因此本发明的三元闭包的思想更加符合实际。

如图3所示，横坐标为节点的度数，纵坐标为所有节点的聚类系数的平均值。用现有BA 模型和本发明方法分别对人人网的数据进行模拟，本发明方法中设置α为1，K为100，k为 5。从图中可以看出，利用本发明方法相对于利用BA模型所模拟的社交网络的聚类系数更接 近于真实的社交网络。