耦合二分网络识别通信系统流量的时空特征

谭桂敏，汪丽娜,2，臧臣瑞

(1.内蒙古工业大学理学院，呼和浩特 010051；2.内蒙古生命数据统计分析理论与神经网络建模重点实验室，呼和浩特 010051；3.中国联合网络通信有限公司内蒙古分公司，呼和浩特 010050)

0 引言

各个领域都蕴藏了丰富的时空数据。随着传感器和通信技术的快速发展，累积了大量包含地理位置信息的时空数据。越来越多的科学家关注时空数据的信息挖掘。与关系数据不同，时空数据除了具有实体及实体之间的联系属性，还包含了时间属性和空间属性[1]。时空属性的存在为分析数据带来了挑战。

二分网络可以展示两类不同属性群组成员之间的联系，如电影演员网络中，演员演出电影关系由演员群组与电影群组中节点间的连边表示。现实中存在大量不同属性群组之间的交互关系，利用二分网络可以研究不同群组间交互关系的特征。二分网络投影成单分网络能够提取二分网络中的隐含信息，研究同类节点之间直接的联系。在互联网应用领域，恶意域与客户端[2]、用户与应用程序[3]、用户与网页[4]、编码器与接收器[5]等存在联系。根据网络流量日志中存储的网络犯罪信息，Jeng等[2]构造了恶意域与客户端二分网络，分析网络特征发现了其他无法识别的威胁情报系统的新恶意域。Zhang等[3]把用户的偏好关系表达成用户与音乐的二分网络，提出了一种改进的二分图链接预测音乐推荐方法。在医学领域，药物与靶细胞[6]，药物与蛋白质[7]、基因组与连接体[8]等存在关联关系。Manoochehri等[6]构建药物与靶细胞二分网络，研究药物与靶细胞之间的潜在相互作用。Wang等[7]构建药物与蛋白质二分网络，挖掘药物疾病相互作用以理解潜在的生物机制。在学术研究领域，郗强等[9]以领域和关键词、学者和领域、作者和机构3个二分网络分析了焦点、作者、机构与领域之间的关系。

目前，人们主要研究源于现实的两类群组中自然存在的关系，如演员—电影、学者—论文、用户—网页等。针对抽象的不同属性的群组中基元之间联系的研究比较少。比如，时空数据中的时间属性可以抽象为时间节点；空间属性可以抽象为空间节点，时空交互关系抽象为两类节点之间的连边，以构建二分网络。由于考虑了时空数据中包含基元的时间和空间相互作用关系，二分网络可以研究基元的时空演化特征。二分网络投影成单分网络，可以探讨基元时间或空间的直接联系。

上述时空数据建立二分网络可以挖掘时空数据中的信息。除此之外，最近Yang等[10]提出了高斯核密度估计和滑动窗口相结合的方法来挖掘交通流时空数据中的关键道路。Jiang等[11]利用无监督分布学习方法提高了空间和时间相关预测的准确性。Wang等[12]详细挖掘在发生自然灾害时，人类情绪的时空特征。Charakopoulos等[13]利用互相关分析和复杂网络方法，提取隐藏的时空特征。时空聚类也是一种时空数据挖掘方法，可以发现基元之间的相似性。传统的聚类方法并不适用于高维数据。传统的时间序列聚类方法要么只考虑时间，不能保证得到的聚类群组在空间上是连续的[14]；要么只考虑空间，不能确保不同的群组是不同的[15]。时空数据建立二分网络的核心—边缘聚类则可以综合时间和空间信息，得到群组间差异最大的聚类结果。

移动通信领域所有基站可看作复杂系统，使用复杂网络方法是研究基站系统的一个新视角。Wang等[16]提出了一种新的时间序列建网方法。此方法可以体现移动通信业务量时间序列中单个值的细节变化。Wang等[17]用基于网络理论的深度学习方法预测蜂窝数据流，预测结果优于传统的时间序列方法。Li等[18]通过将时间序列映射为复杂网络，捕捉时间序列的局部特征。Enami等[19]提出了一种轨迹数据的挖掘和预测算法，在时空上预测用户未来的移动性行为。从而预测流量需求，适当分配网络资源。因此从海量的移动通信时间序列数据中发掘通信数据演化规律，应用于智能通信系统以及时应对突发流量激增的情况，可以提高网络资源的利用率。

为探究移动通信基站流量的时空特征，本文建立了耦合网络模型。利用核心—边缘聚类方法，分析时空尺度上吞吐量和话务量的聚类特征。

1 方法

1.1 二分网络

二分网络可以将时空数据一体化，研究时间与空间的相互作用关系。在本文移动通信基站时空数据的背景下，建网的具体过程为：

1)确定节点。空间节点为所选区域内各个空间位置的基站，代表基站覆盖范围。时间节点为等长的时间序列片段。应用滑动相关法划分时间序列，取时间窗口为24时，步长为1，得到时间序列片段，代表吞吐量和话务量时间序列动态变化特征(耦合过程)。

2)建立相似度矩阵。从时空序列矩阵出发，计算任意一个基站上两列时间序列片段的斯皮尔曼相关系数，得相似度矩阵S

(1)

其中，元素sij≠sji，sij为时间段i内基站j上两列时间序列之间的相似度即耦合程度。相似度矩阵是一个非对称矩阵。

3)构建二分网络。依据相似度和阈值σ确定节点间是否存在连边。一般定义相似度r的绝对值|r|≥0.8为强相似。考虑到强相似代表耦合显著，取阈值σ为0.8。如果某时间段内任意一个基站上两列时间序列的相似度绝对值不小于阈值，则对应的时间节点和空间节点之间存在连边；否则不存在连边。即邻接矩阵A中的元素aij为

(2)

其中，aij=1意味着时间节点i和空间节点j之间存在一条边。此时，认为在时间节点i代表的时间段内空间节点j上的两列时间序列具有高相似性，表明时间段i内基站j上的数据业务吞吐量和话音业务话务量耦合显著。反之，aij=0意味着时间节点i和空间节点j之间不存在边。此时，认为在时间节点i代表的时间段内空间节点j上的两列时间序列不具有高相似性，表明时间段i内基站j上的数据业务吞吐量和话音业务话务量耦合不显著。

1.2 投影

在分析二分网络时，通常将它投影成单分网络，再分析单分网络的拓扑性质。二分网络中有两类属性不同的节点，因此可以投影得到两个单分网络。例如，在本文耦合二分网络中，如果时间节点t1,t2都与某个空间节点s3相连，那么在对应的时间单分网络中，t1,t2之间就存在一条连边。类似地，如果空间节点s1,s2都与某个时间节点t2相连，那么在对应的空间单分网络中，s1,s2之间就存在一条连边。

上述无权的投影方法应用广泛，但是它的构造方式使得原始二分网络的一些信息丢失。比如，投影中并没有保留两个时间节点(空间节点)共同连接的空间节点(时间节点)的数量。通过给连边赋予权重，可以弥补缺陷，在投影中保留这类信息。即如果时间节点t1,t2既与空间节点s3相连又与空间节点s5相连，那么在对应的时间单分网络中t1,t2之间连边的权重为2。本文中，把两个时间节点(空间节点)共同连接的空间节点(时间节点)的个数作为权重，投影得到加权的单分网络。

1.3 核心—边缘结构分析

Borgatti和Everett[20-21]提出二分网络的核心—边缘结构模型，分析二分网络的聚类特征。核心—边缘结构模型是将邻接矩阵的行和列聚类为两类(核心、边缘)的理想模型，聚类结果的主对角线上是两个子块。其中一个是高密度块，称之为核心；另一个是低密度块，称之为边缘。核心—边缘结构模型可以用来识别事件群聚群发的区域。本文的二分网络聚类之后，核心区是时间和空间上频繁发生的事件，边缘区是时间和空间上发生频率低的事件。核心—边缘结构模型的聚类过程如图1所示。

图1 聚类流程图Fig.1 The process diagram of clustering

1.4 简例

以3个基站构成的系统为例说明建立二分网络过程及投影成时间单分网络和空间单分网络过程。数据的时空序列矩阵Ds和Dh为

(3)

Ds中的3列分别对应3个基站上的吞吐量时间序列，Dh中的3列分别对应与Ds中相同的3个基站上的话务量时间序列。根据步骤1)中取时间窗口为24时，步长为1划分得到时间序列片段。每列时间序列经过划分得到3个时间序列片段。分别计算每个基站上的两列时间序列片段(吞吐量，话务量)之间的斯皮尔曼相关系数，得相似度矩阵S为

(4)

根据步骤3选取阈值为0.8。根据公式(2)，得二分网络的邻接矩阵A

(5)

二分网络如图2a所示，二分网络的单模投影得到的时间网络和空间网络如图2b，2c所示，图中边的粗细和权重成正比。二分网络中t1通过s2与t2相连，也通过s3与t2相连，如图2b所示时间网络中t1和t2连边权重为2。同样的s2可以分别通过t1和t2与s3相连，如图2c所示空间网络中s2和s3连边权重为2。

图2 二分网络及投影的单分网络Fig.2 Bipartite network and corresponding unipartite network

对如上二分网络做核心边缘结构分析，聚类后的分块矩阵为

(6)

核心区为时间节点t1和t3和空间节点s3，说明s3基站在t1和t3时刻发生耦合事件次数多。边缘区为时间节点t2和空间节点s1和s2，说明s1和s2基站在t2时刻发生的耦合事件的次数少。密度矩阵如式(7)所示，主对角线上核心区密度为1，边缘区密度为0。

(7)

2 耦合二分网络

本文所选数据为某市运营商提供的基站自动采集的数据。从2017年2月22日0:00至2月26日18:00，近90 000条数据。每条数据是一个具有三维属性(时间属性、空间属性、流量属性)的五维向量(时间，经度，纬度，数据业务吞吐量，话音业务话务量)，表示某时某地理位置处的基站，其覆盖范围内的吞吐量和话务量。预处理后得到116个基站上的吞吐量与话务量时间序列，每个时间序列的长度为139。

首先，将时空数据一体化，建立一个耦合二分网络。其中利用斯皮尔曼相关系数度量吞吐量和话务量时间序列的耦合是否显著，耦合显著则称某基站在某时间段内发生了耦合事件。再将耦合二分网络投影成时间单分网络和空间单分网络，分析拓扑性质。

本文所建的耦合二分网络代表3种情况：1)不同时间段内的耦合事件发生在不同的基站；2)多个耦合事件发生在同一个基站；3)在同一个时期内，耦合事件发生在多个基站。耦合二分网络可以反应耦合事件的动态演化过程，吞吐量与话务量耦合可以反映多种事件的叠加效应。耦合二分网络有116个时间节点，116个空间节点。其中空间节点中存在42个孤立节点，表示其对应的基站上无耦合事件发生，本文不分析孤立节点。称耦合二分网络的最大连通子图为C网络(Coupling Network)，如图3所示，C网络中有116个时间节点，74个空间节点。

图3 C网络Fig.3 C network

蓝色正方形代表空间节点,即基站，红色圆点代表时间节点即不同的时间段。空间节点可以分为两类：图3中外围蓝色空间节点和中心绿色空间节点。绿色空间节点上的连边数均超过50，大于蓝色节点上的连边数。其中，s99与s100空间节点上连边数最多，为115条，这两个空间节点和几乎所有的时间节点(共116个)都存在连边。说明既存在没有耦合事件发生的基站也存在几乎一直发生耦合事件的基站。

耦合二分网络中存在两类节点(时间节点和空间节点)，对应地，存在时间节点度和空间节点度。时间节点度指时间节点代表的某时期内有耦合事件发生的基站个数。时间节点度越大，表明此时期，空间上大范围内发生了耦合事件，即吞吐量和话务量动态变化相似。空间节点度指某基站耦合事件发生的次数。空间节点度越大，表明此基站上耦合事件大量发生，即吞吐量话务量动态变化高度相似。图中绿色空间节点度大，说明其代表的基站上耦合事件多次发生。

3 单分网络

3.1 时间单分网络

将耦合二分网络投影得到加权的时间单分网络，可以研究耦合事件发生时间的规律。时间单分网络是一个完全图，网络中节点度均为115，说明任意两个时间段内至少一个基站上发生了耦合事件。边权代表两个时间段内均有耦合事件发生的基站个数。时间单分网络的边权分布为对数正态分布，如图4a所示，拟合函数为p(w)=0.156 4e-3.771 8(lgw-1.717)2，拟合优度[22]R2=0.920 4。强度为边权之和[23]，代表某时间段与其他全部时间段内发生耦合事件基站的总数。时间单分网络的累积强度分布为线性分布，如图4b所示，散点呈直线。拟合函数为P(s)=-0.001 0s+1.496 0，拟合优度R2=0.981 3。

图4 边权分布和累积强度分布Fig.4 Edge weight distribution and cumulative strength distribution

3.2 空间单分网络

耦合二分网络中存在孤立节点42个，投影成空间单分网络后，空间单分网络中也存在孤立节点42个。我们分析空间单分网络的最大连通子图，称空间单分网络的最大连通子图为S网络(Spatial Network)。S网络的集聚系数为0.836，平均路径长度为1.42，S网络属于小世界网络。

节点度为与节点直接相连的边的数量，S网络节点度k表示此节点对应的基站与k个基站在某时间段内吞吐量与话务量发生了耦合。S网络的累积度分布为线性分布，如图5a所示，拟合函数为P(k)=-0.010 6k+0.773 6，拟合优度R2=0.983 3。强度为节点连边权重的和，S网络节点强度表示此节点对应的基站与其他所有基站有耦合事件发生的总数。S网络的累积强度分布为指数分布，如图5b所示，拟合函数为P(s)=0.606 4e-0.001 6s，拟合优度R2=0.992 7。边权为连边的权重，S网络中边权w表示两基站在w个时间段上都有耦合事件发生。S网络的边权分布为幂律分布，如图5c所示，双对数坐标下，散点呈直线。拟合函数为p(w)=0.149 8w-0.794 8，拟合优度R2=0.911 6。表明S网络的边权具有无标度特性。

图5 累积度分布、累积强度分布和边权分布Fig.5 Cumulative degree distribution,cumulative strength distribution and edge weight distribution

3.3 抗攻击性分析

基站可能会遭受突发攻击，出现故障无法正常运行，进而影响整个系统的传输性能，本文对S网络进行抗攻击性分析。突发事件可能是随机的，也可能是蓄意的，如遭受黑客攻击等。依度对S网络做蓄意攻击，从去除网络中度最大的节点开始，有意识地去除网络中一部分度最高的节点。图6a和图6b分别反映了随机和蓄意攻击下S网络最大连通子图相对大小R和最短路径长度L随删除节点比例f的变化情况。

图6 抗攻击性表现Fig.6 Robustness performance

4 时空聚类分析

在复杂的现象中发现有序时空规律是聚类分析的目的。为了识别网络聚类特征，常用核心—边缘结构模型来分析网络[24-25]。核心—边缘结构模型是使核心区与边缘区的差异最大化[26-27]。核心—边缘结构模型能识别出时间与空间聚集的区域。针对耦合二分网络的最大连通子图——C网络做核心—边缘模型结构分析，识别吞吐量与话务量耦合事件发生的时间和空间聚集区域。C网络中时间节点116个，空间节点74个。得聚类后的密度矩阵为

表1 耦合比重划分Tab.1 Division of coupling proportion

(8)

密度矩阵为两行两列，其中，第1行第1列的0.521为聚类后核心区的密度，第2行第2列的0.091为聚类后的边缘区的密度。核心区与边缘区的密度存在差异表示聚类后的核心区的两类节点与边缘区的两类存在差异。聚类后得到核心空间节点(基站)30个、核心时间节点49个，边缘空间节点44个、边缘时间节点67个。核心—边缘模型划分出了耦合事件的发生时期与空间聚集区域。

为直观表示核心区与边缘区的差异，根据基站在特定时间段内吞吐量与话务量耦合事件发生的多少，定义耦合比重

(9)

其中，hi为基站耦合事件发生的频数，即耦合单元数；n为核心区或者边缘区时间节点的个数。fi取值为0到1，越接近于1表明基站上耦合事件发生的越多。确定如表l所示耦合比重划分。

依据聚类结果，分别画出在核心区与边缘区时间节点代表的时间段内的基站在地理位置上的分布。如图7a和图7b所示。图7a为核心区时间段内基站在地理位置上的分布；图7b为边缘区时间段内基站在地理位置上的分布。其中，节点颜色是根据对耦合比重的划分确定的，弱耦合为蓝色，中弱耦合为绿色，中强耦合为黄色，强耦合为红色。

图7 核心区与边缘区的基站在地理上的离散分布Fig.7 The geographical discrete distribution of base stations in the core area and the periphery area

总体来看，图7a中红色和黄色节点多，图7b中除3个节点为绿色外，其余节点均为蓝色。表明核心时间段内的耦合比重高于边缘时间段内的耦合比重，核心区耦合事件的发生频率高于边缘区耦合事件的发生频率。无论是时间上还是空间上，核心—边缘模型有效识别了不同时间段内的群聚群发区域。对于核心区域的节点，尤其是核心区红色节点代表的基站值得重点关注，考虑新增基站或基站扩容以预防流量激增导致的网络拥塞等问题。

5 结论

基于吞吐量与话务量时空数据，利用时间序列相似性度量与滑动时间窗口等数理统计方法，本文分析了某地区近6天的吞吐量与话务量数据时空变化特征。基于相似关系建立耦合二分网络，将时空数据一体化。投影得到加权的时间单分网络与空间单分网络，分析单分网络拓扑特征，展示耦合事件在时间和空间上的差异。对空间单分网络做抗攻击性分析，探讨基站遭破坏后系统的稳定性。利用核心边缘模型分析吞吐量与话务量耦合的时空聚类特征。

耦合二分网络中，空间节点间差异性比时间节点间差异性明显，既存在没有耦合事件发生的基站也存在几乎一直发生耦合事件的基站。时间单分网络为完全图，边权分布为对数正态分布。S网络为小世界网络，边权分布为幂律分布。S网络边权具有无标度特性。此外S网络的抗攻击性强，网络具有鲁棒性。核心—边缘模型时空聚类可以有效划分核心空间节点和核心时间节点，核心区节点上吞吐量与话务量耦合事件发生频率比边缘区节点上的耦合事件发生频率高。表明在核心区基站上，吞吐量与话务量动态变化十分相似。会出现基站吞吐量与话务量同时增大或同时减少的情况，值得进一步关注以预防流量激增导致的网络拥塞等问题。

本文综合了时间和空间维度信息以及时间与空间的相互关联关系，构建时空耦合网络。利用核心—边缘模型对耦合二分网络做聚类，聚类结果是既考虑时间又考虑空间的一个划分。得到基站上吞吐量与话务量的群聚群发特征，为基站建设和管理提供了一些建议。本文的研究方法也为探索多事件耦合研究提供了新思路。