0 概述

随着移动设备、移动数据流量以及WiFi的普及, 人类的行为与社交网络的关系越来越密切。因此, 对移动社交网络的研究具有重要的实际意义^[1-3]。许多研究者对移动社交网络的推荐系统^[4]、信息保护^[5]等不同领域进行研究, 给出小世界网络^[6-7]和无标度网络^[8-9]2种网络拓扑结构。近几年, 移动社交网络的分形特征被广泛研究, 文献[10]提出盒子覆盖算法计算分形维数, 证明了网络的局部和整体具有相似性, 揭示不规则网络的内在标度不变性。文献[11]提出REMCC盒子覆盖算法, 证明了移动社交网络长时间序列具有单分形性质, 但短时间不具有单分形的性质。尽管单分形维数能够描述移动社交网络的时间序列特征, 从整体上反映集合的不规则形, 但不能展现网络的动态演化性。

现实中的复杂网络与复杂系统一般都具有自相似性, 这种自相似性不仅体现为拓扑结构上的自相似, 也体现为某种质量、测度在网络上分配的自相似性。多重分形便是描述在不规则的分形空间上的质量分布的定量化工具^[12-13]。文献[14]证明了无标度网路存在明显的多重分形特征, 然而在小世界网络和随机网络的多重分形特征并不明显。文献[15]提出BCANw算法证明了加权复杂网络具有多重分形特征。多重分形理论分析已经应用到不同的研究领域中, 在电力系统中, 文献[16]基于多重分形理论提出一种负荷风险预警的阈值确定方法, 降低了其风险性。文献[17]证明了交通时间序列的波动性具有多重分形特征, 并通过多重分形谱特征值的不同, 分析道路交通流量的波动性。文献[18]通过不同的多重分形谱的特征值来识别不同的掌纹。复杂网络中的无标度、小世界等特征和其相关的内部度量指标越来越多地被揭示。因此, 为应用多重分形特征, 需分析移动社交网络多重分形特征及其形成的内在影响因素。

本文基于REMCC盒子覆盖算法, 提出移动社交网络多重分形分析方法。通过分析4个典型的移动社交网络的多重分形特征, 计算网络的度分布、同配系数、连通性和平均路径长度, 并分析网络的多重分形特征受网络节点度分布和同配系数影响的规律。

1 实验数据与相关工作 1.1 实验数据与建模分析 1.1.1 实验数据

本文对典型的移动社交网络时间序列:Camb lab dataset, Inf 05 dataset, Roller dataset和MIT dataset进行实验分析。移动社交网络随着时间的演化, 内部结构越来越复杂, 表 1为4个网络数据集的基本特征。图 1给出在不同时间段节点流量的非线性特征, 可以看出, 随时间的动态演化, 移动社交网络整体的内部结构复杂多样。因此, 本文对网络进行多重分形特征分析, 研究在演化过程中不同层次的特征。

1.1.2 数据建模分析

移动社交网络相较于一般的复杂网络有一些特定的特征, 原因在于移动社交网络的节点连接随时间变化而增加或消失。因此, 将移动社交网络看作是一个动态演变图, 图中的点和边相当于移动社交网络中的节点及节点的连接情况。给出G(N, V, W), 其中, G是加权的移动社交网络, 边的权重定义为d_ij, N=(1, 2, …, n)是节点的集合, V=(1, 2, …, m)是边的集合, w=(1, 2, …, m)是边权重的集合, 如果节点i和j相连, 则表示为w_ij, 否则为0。本文将w_ij表示为两相连节点间的平均连接时长:

$ w_{i j}=\frac{1}{n} \sum\limits_{i=1}^{n}\left(t_{\mathrm{end}}-t_{\mathrm{start}}\right) $

其中, n是节点的相遇次数, t_start表示网络中节点相遇初始时间, t_end为节点相遇完成时间。在MSNs中节点的边附上权值后, 转化为加权网络。加权网络中用最短路径长度来定义节点间的距离。通过进一步计算网络中节点的最短距离, 以便于更好地描述盒子覆盖算法。边的权重值越大, 距离越短, 即网络之中节点的平均相遇时长越长, 代表节点的距离就越近。

1.2 相关参数的定义与扩展 1.2.1 度分布

度^[17]是描述网络局部特性的基本参数。网络中节点的度的分布情况可用分布函数P(k)表示, 其含义为从网络中随机选取一个节点, 该节点具有k条边的概率。度分布函数反映了网络的宏观统计特征。

1.2.2 同配系数

网络的同配性(或异配性)的程度可用同配系数r来刻画^[18]。r>0表示整个网络呈现同配性, 表现为正相关性, 度大的节点倾向于和度大的节点相连; r < 0表示整个网络呈现异配性, 度大的节点趋向于连接度小的节点, 表现为负相关性; r=0时表示整个网络结构不存在相关性。

$ r=\frac{M^{-1} \Sigma k_{i} k_{j}-\left[M^{-1} \Sigma \frac{1}{2}\left(k_{i}+k_{j}\right)\right]^{2}}{M^{-1} \Sigma \frac{1}{2}\left(k_{i}^{2}+k_{j}^{2}\right)-\left[M^{-1} \Sigma \frac{1}{2}\left(k_{i}+k_{j}\right)\right]^{2}} $

其中, k_i、k_j分别为e_ij的2个节点i、j的度, M为网络的总变数。

1.2.3 网路的连通度

连通图G的连通程度通常叫做连通度^[19-20]。一个网络的连通度越高, 代表网络越稳定, 稳定性越好。

$ \kappa (G) = \mathop {\min }\limits_{S \subset V} \left\{ {|S|, \omega (G - S) \ge 2或G - S为平凡图} \right\} $

其中, V为图G的节点集合, S为V的真子集, ω(G－S)为从图中删除点集S后得到的子图G－S的联通分支数。这里G－S是指删除S中每一个节点以及图G中与之关联的所有边。由此可见, 点连通度就是使G不连通或称为平凡图(只有一个节点没有边的图)所必须删除的最少节点个数。对于不连通图或平凡图, 定义κ(G)=0;若G为N个节点的完全图, 则κ(G)=N－1。

1.2.4 平均路径长度

定义任意2个节点之间的距离的平均值^[21]为:

$ L = \frac{1}{{C_N^2}}\sum\limits_{1 \le i \le j \le N} {} {d_{ij}} $

网络中任意2个节点之间的距离的最大值称为网络的直径D, 即:

$ D = \mathop {\max }\limits_{1 \le i \le j \le N} {d_{ij}} $

网络中2个节点i和j之间的距离d_ij定义为连接这2个节点的最短路径。

1.3 多重分形分析方法

划分盒子数后, 定义概率函数为:

$ P_{i}(\varepsilon)=\frac{N_{i}(\varepsilon)}{N} $

其中, N为网络质量, 即网络总节点个数, N_i即盒子内部节点的总数, ε为观察尺度, 其值等于盒子半径, 大小为从0至网络直径, P的总和为1。在对概率进行计算后, 定义配分函数计算公式如下:

$ {Z_q}(\varepsilon ) = \sum\limits_i^{{n_i}(\varepsilon )} {P_i^q} $

其中, n为在盒半径ε下所求得的盒子的总个数, q为阶数, 取值范围为(－∞, +∞), 反映了结构不均匀程度的大小。如果所观察对象具有多重分形特征, 则配分函数Z与观察尺度ε之间存在幂律分布:

$ Z_{q}(\varepsilon) \sim \varepsilon^{\tau_{q}} $

其中, 幂指数τ被定义为质量指数, 通过最小二乘法对进行拟合, 可以得到τ的取值:

$ \tau(q)=\frac{\log _{a}\left(Z_{q}(\varepsilon)\right)}{\log _{a}(\varepsilon)} $

根据勒朗德变换, 质量函数与多重分形谱之间存在如下关系^[22]:

$ \begin{array}{l}{\alpha_{q}=\frac{\mathrm{d} \tau_{q}}{\mathrm{d} q}} \\ {f\left(\alpha_{q}\right)=q \alpha_{q}-\tau_{q}}\end{array} $

本文研究用配分法定义的非均匀多重分形集广义维数D_q、质量指数τ(q)、奇异性指数α(q)和奇异谱函数f(α(q))的单调性和极限等几何特性, 给出极限的解析算法, 为确定合理的多重分形谱给出判定准则。

多重分形谱用最小二次拟合法, 拟合的二次函数设为:

$ f(\alpha)=A\left(\alpha-\alpha_{0}\right)^{2}+B\left(\alpha-\alpha_{0}\right)+C $

其中, 参数B表示多重分形谱的不对称性。当f(α)的最大值越大, 多重分形谱的宽度W越大及其谱曲线的对称性越好时, 对象呈现的多重分形性就越强^[23]。

2 实验结果与分析

通过对数据进行建模分析, 从图 2中可以看出, 4个网络的广义维数D_q和奇异性指数α(q)是关于q的严格单调递减函数, 表明网络具有多重分形的特征。图 3显示了q=-20, -15, -10, 10, 15, 20时的双对数关系。可以看出, 无论q取正负值, log_aZ(q, ε)与log_aε之间都表现为线性关系, 即网络具有分形的特性。图 4显示了质量函数τ(q)是关于q的严格的一个上凸函数, 存在着非线性关系, 表明移动社交网络具有多重分形的特征。

本文通过使用统计矩的多重分形分析法, 得到f(α)是关于α的凸函数, 在q>0时单调递增, 在q < 0时单调递减, 且在q=0时取得极大值, 此时f(α(0))=D(q), 多重分形谱如图 5所示。通过分析配分函数、质量指数函数、多重分形谱函数, 进而求取多重分形谱所对应的3个特征参数:谱曲线的极大值f(α(0)), 宽度W和谱曲线所对应的不对称性程度B。如表 2和图 5所示, 4个移动社交网络均表现出多重分形的特征, MIT相对于其他3个网络, 多重分形谱越窄越不对称, MIT网络的多重分形特征表现的越不明显。以上证明了4个网络具有多重分形的性质, 但是本文发现网络中多重分形特征表现程度并不同。因此, 需要通过计算网络的指标来揭示影响多重分形的内在因素。

通过以上对移动社交网络进行建模分析与网络基础理论知识, 分别计算不同网络的度, 度分布情况如图 6所示, 同配系数、连通度以及平均路径长度如表 3所示。从图 6中可以看出, MIT网络节点的度分布并没有表现出幂律分布, 度大的节点趋向于连接度大的节点, 度小的节点趋向于连接度小的节点, 表现为相似性, 然而Camb lab、Inf 05和Roller度分布符合幂律分布。从图 6中发现MIT网络中节点的度分布明显与其他3个网络不同。

在表 3中, 通过计算比较4个网络的内在指标。可以看出, 在同配系数值中只有MIT网络的r>0, 表现为度相关性, 具有同配性, 其他3个网络均表现为异配性, 为无标度网络, 具有标度不变性的特征。4个网络的平均路径长度并没有表现出相互太大的差异性, 说明在移动社交网络中, 人与人之间的交流比较密切, 而且遵循小世界的性质。当度分布符合幂律分布, 同配系数r < 0时, 表明网络内部结构分布越不规则, 网络的多重分形特征越明显, 因此, 得到网络的多重分形特征受节点度分布和节点之间关联程度的影响。同时, 在移动社交网络中无标度、小世界与多重分形所表现的特征是共存的。网络的连通度大小与平均路径长度的大小, 并不能作为判断影响多重分形特征内在因素的条件。

3 结束语

本文基于多重分形相关理论, 提出移动社交网络的多重分形分析方法。证明4个典型的移动社交网络时间序列具有一定的多重分形特征, 并对多重分形谱的3个特征参数进行对比。实验结果表明, 相对于异配性网络, 具有同配性的网络多重分形表现越不明显, 则移动社交网络随着时间演化表现越不规则。当前对移动社交网络多重分形的性质研究多为基础性工作, 下一步将在现有移动社交网络动态演化建模的基础上, 将网络某种质量、测度以及在网络上分配的相似性作为研究对象, 预测网络结构的演化和人类的行为。