基于自动相转换聚类的重叠社区网络检测方法

摘要

本发明提出了一种基于自动相转换聚类的重叠社区网络检测方法，克服现有技术中处理较慢，复杂性较高且在检测重叠社区时必须事先已知社区结构和社区个数的问题。其实现步骤是：(1)生成网络邻接矩阵；(2)初始化；(3)更新节点相位；(4)处理更新后节点的相位；(5)判断更新后节点的相位是否稳定；(6)统计子区间节点个数；(7)输出网络社区划分结果。本发明提出的方法更新节点的相位是一个离散迭代的过程，加快了相位求解过程，提高了并行处理能力，不需要事先设定各个节点的固有频率和已知社区结构，降低了网络社区检测的复杂性，可以有效地检测出网络的各个社区和重叠节点。

主权项

基于自动相转换聚类的重叠社区网络检测方法，具体步骤如下：(1)将待检测重叠社区网络生成与该网络对应的邻接矩阵；(2)初始化在[‑a，a]相位值范围内随机产生与网络节点数相同个数的随机数，将每个随机数作为每个节点的初始相位；(3)更新节点相位将每个节点更新前的相位代入下列方程，得到该节点更新后的一个新的相位：y＝x+C1×(M‑x)+C2×(x‑N)其中，y为节点更新后的相位；x为节点更新前的相位；C1为衡量控制相同社区内节点相位的接近速度的控制参数，C2为衡量控制不同社区间节点相位的远离速度的控制参数，C1、C2在(0，1]范围内选取；M代表与节点有连接边的所有节点在更新前的平均相位；N代表与节点没有连接边的所有节点在更新前的平均相位；(4)处理更新后节点相位如果更新后的所有节点相位中存在相位值大于a的相位时，选取更新后节点相位值中为正的相位，将相位值为正的每一个节点相位分别与压缩比r1相乘，使相位值为正的每一个节点相位都分布在[‑a，a]相位值之间；如果更新后的所有节点相位中存在相位值小于‑a的相位时，选取更新后节点相位值中为负的相位，将相位值为负的每一个节点相位分别与压缩比r2相乘，使相位值为负的每一个节点相位都分布在[‑a，a]相位值之间；(5)判断更新后节点的相位是否稳定将每个节点更新后的相位与更新前的相位相减，得到一个差值，若该差值小于0，对该差值求绝对值，在所有节点的差值中选取其中差值最大的一个差值，若该最大差值小于阈值ε，0＜ε＜1，则认为所有节点的相位趋于稳定，进入下一步骤，否则，将每个节点更新后的相位作为该节点下一次更新前的相位，返回步骤(3)；(6)统计子区间节点个数当所有节点的相位稳定时，将[‑a，a]相位值均匀划分为若干个长度为len的子区 间，统计每个子区间内节点的相位处于该子区间范围内节点的个数；(7)输出网络社区划分结果将子区间内节点个数大于0的相邻子区间划分为一组，在该组内的所有子区间中搜索子区间节点个数的最大值，若该最大值大于阈值T，1≤T≤5，则该组内所有子区间对应的节点为网络的一个社区，否则，该组内所有子区间对应的节点为网络的重叠节点。