一种幂律属性网络几何生成方法

摘要

本发明提出了一种幂律属性网络几何生成方法。本发明拟合数据集的属性分布；拟合网络节点度分布，并确定分布参数；随机生成双曲空间中的候选节点，并计算各候选点之间的双曲距离；计算候选节点之间的连接概率，并依据候选节点之间的连接概率生成连边。本发明保证了生成模型的几何特性，即节点处于高维双曲空间中，基于该特点，该生成模型很好的利用节点空间结构如距离远近、簇关系、位置分布，分析网络演化的成因，形成可视化的全局网络概述，并通过统一的度量构建用于如链路预测、社区检测、节点分类、相似度预测等下游网络挖掘任务的分析模型。

说明书

技术领域

本发明属于复杂网络应用领域，尤其涉及一种幂律属性网络几何生成方法。

背景技术

自然界和人类社会中广泛存在着复杂系统，而复杂系统正好可通过各种各样的复杂网络来描述。近年来，网络科学作为一门融合了拓扑学、统计、随机过程、动力系统等多类理论方法的交叉学科在社交、通信、交通运输等领域有着广泛的应用，如链路预测、社区发现、网络演化、层次分析等等。而伴随着图卷积网络的提出，利用大规模计算的方式可将网络的拓扑连接关系依特征的编码至度量空间以执行相应的图信息挖掘任务。然而，在这种观点下，仅将网络看作一个静态的学习对象，对其连接关系进行表征，缺少对网络宏观统计量如网络的度幂律分布、网络的社区结构等的刻画及生成规律的分析，这些都对网络内蕴性质的研究有着重要的意义。其次，网络中除了节点连接关系外，还有连接属性，如科学家网络除了引用关系外，节点本身还蕴含科学家的研究领域这类固定属性，这些固定属性必然会对网络中的连接关系产生影响，如两个研究领域相似的科学家更有可能存在引用关系。而目前的生成模型网络中的节点以特定约束(如度幂律分布、无差别连接等)构建连接概率，随机形成连边，缺乏对节点内蕴属性在网络生成过程中作用的描述，这就使得节点属性与节点连接之间的关系孤立存在，这与实际规律是不符合的。

发明内容

为了解决上述技术问题，本发明从再现属性网络的结构特征这一需求出发，研究属性分布对幂律度分布网络节点连接关系的影响，建立幂律属性网络的动态生成方法，以实现生成与给定数据具有相同度分布(即幂律分布)的属性网络。该生成模型拟合网络物理规律，反演网络性质，通过对空间曲率和温度这两个模型参数的调节，实现对不同网络结构的生成。本发明的一项重要应用场景在于移动通信网络拓扑结构分析，具体的，基于先前大量的通信研究发现，以用户通信为连边所构成的网络往往具有幂律度分布特征，为了满足这类通信需求，在资源有限的情况下，往往需要考虑基站的动态负载均衡，因而需要一种持续演化的方法来指导建设移动基站。本发明所提出的模型在融合了基站属性信息(网络节点属性)，构建了一种幂律网络的动态生成模型，在每个时刻都能生成特定演化规律的基站间隔(节点双曲距离)。因而应用此模型可以很好的指导移动通信网络拓扑生成。

本发明所采用的技术方案提供一种幂律属性网络几何生成方法，其特征在于，包括以下步骤，

步骤1，拟合数据集的属性分布；

步骤2，拟合网络节点度分布，并确定分布参数；

步骤3：随机生成双曲空间中的候选节点，并计算各候选点之间的双曲距离；

步骤4：计算候选节点之间的连接概率，并依据候选节点之间的连接概率生成连边；

作为优选，所述步骤1具体如下：

定义属性网络G(V,E,K)；

其中，V为节点集，令|V|＝N，N表示节点数量，E为边集，

属性网络中第k个属性分布的概率为：

其中，

作为优选，所述步骤2具体如下：

对于给定网络G(V,E,K)，其度分布符合如下幂律分布形式，拟合其度分布中的参数：

其中P(d)为给定网络的拟合度分布，即度为d的概率分布，实际拟合时d取正整数。α为待求参数，d

使用极大似然估计数据的幂律分布参数α及d

作为优选，所述步骤3具体如下：

在第t次迭代时，通过均匀分布在[0,2π]中生成M个随机数，作为节点在双曲空间中的角坐标记作

r(t)＝ln t

此时，在s时刻出现的节点的径向坐标演化为：

r

其中

作为优选，所述步骤4具体如下：

计算第t次迭代时节点之间的连接概率，并依据连接概率实现对律属性网络连边的生成，具体如下：

基于步骤3生成的候选点坐标计算任意两节点

其中，

基于上述双曲距离x(i,j)，计算任意两候选点之间的连接概率。任意两候选点

半径阈值R

其中，m和T为模型预设参数分别表示网络节点度的期望和生成温度，ω

基于上述步骤4所得到的网络连接概率p

具体实现如下：

步骤4.1，应用均匀分布在[0,1]中随机生成一个随机矩阵，记作

Seed＝＝{Se

其中Se

步骤4.2，分别比较连接概率矩阵P＝{p

若p

步骤4.3，重复步骤4.1、步骤4.2，直到计算完所有的a

相对于现有技术，本发明的有益效果是：本发明针对现有网络几何生成方法未考虑属性分布，而造成无法有效表征属性差异对网络结构的影响这一局限性，在网络动态生成的框架下，重新设计了属性网络演化模型。充分加入网络属性信息，利用似然估计拟合网络属性，并将拟合结果加入生成模型中，推导出高维双曲空间的网络链接概率，基于显式的链接表达生成随机种子，以实现对属性网络特性的反演。整个发明保证了生成模型的几何特性，即节点处于高维双曲空间中，基于该特点，该生成模型很好的利用节点空间结构如距离远近、簇关系、位置分布，分析网络演化的成因，形成可视化的全局网络概述，并通过统一的度量构建用于如链路预测、社区检测、节点分类、相似度预测等下游网络挖掘任务的分析模型。该发明在工程上也可用于移动通信网络拓扑结构分析上，具体的，通过该模型指导生成特定需求的移动通信网络，如要生成抗毁性强的网络，需要空间曲率尽可能大，温度参数尽可能小，通信基站可基于该模型的参数设置间隔。

附图说明

图1：是本发明方法流程图。

图2：是本发明实施例的幂律度分布拟合流程图。

具体实施方式

为了便于本领域普通技术人员理解和实施本发明，下面结合附图及实施示例对本发明作进一步的详细描述，应当理解，此处所描述的实施示例仅用于说明和解释本发明，并不用于限定本发明。请见图1，本发明提供的一种幂律属性网络几何生成方法，将属性分布融入网络几何生成模型中，使网络的潜在特征如度分布、邻接关系都可通过双曲空间结构动态的反演出来，通过几何空间实现网络的可视化，以支持网络下游的分析和挖掘任务。在此基础上，提供相应实例，实施例提供的方法包括以下步骤：

一种幂律属性网络几何生成方法，包括以下步骤，

步骤1，拟合数据集的属性分布；

定义属性网络G(V,E,K)；

其中，V为节点集，令|V|＝N，N表示节点数量，其值为N＝1000，E为边集，

属性网络中第k个属性分布的概率为：

其中，

步骤2，拟合网络节点度分布，并确定分布参数；

所述步骤2具体如下：

对于给定网络G(V,E,K)，其度分布符合如下幂律分布形式，拟合其度分布中的参数：

其中P(d)为给定网络的拟合度分布，即度为d的概率分布。实际拟合时d取正整数，即给定数据集中每个节点的连边之和。α为待求参数，d

使用极大似然估计数据的幂律分布参数α及d

步骤3：随机生成双曲空间中的候选节点，并计算各候选点之间的双曲距离；

所述步骤3具体如下：

在第t次迭代时，通过均匀分布在[0,2π]中生成M＝100个随机数，作为节点在双曲空间中的角坐标记作

r(t)＝ln t

此时，在s时刻出现的节点的径向坐标演化为：

r

其中

步骤4：计算候选节点之间的连接概率，并依据候选节点之间的连接概率生成连边；

所述步骤4具体如下：

计算第t次迭代时节点之间的连接概率，并依据连接概率实现对律属性网络连边的生成，具体如下：

基于步骤3生成的候选点坐标计算任意两节点

其中，

基于上述双曲距离x(i,j)，计算任意两候选点之间的连接概率。任意两候选点

半径阈值R

其中，m和T为模型预设参数分别表示网络节点度的期望和生成温度，T∈(0,1]，ω

基于上述步骤4所得到的网络连接概率p

具体实现如下：

步骤4.1，应用均匀分布在[0,1]中随机生成一个随机矩阵，记作

Seed＝{Se

其中Se

步骤4.2，分别比较连接概率矩阵P＝{p

若p

步骤4.3，重复步骤4.1、步骤4.2，直到计算完所有的a

应当理解的是，本说明书未详细阐述的部分均属于现有技术。

应当理解的是，上述针对较佳实施例的描述较为详细，并不能因此而认为是对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不脱离本发明权利要求所保护的范围情况下，还可以做出替换或变形，均落入本发明的保护范围之内，本发明的请求保护范围应以所附权利要求为准。