基于核节点和社区融合策略的网络社区划分方法

摘要

本发明公开了一种基于核节点和社区融合策略的网络社区划分方法，主要解决现有社区融合算法中目标函数本身存在的分辨率问题。其实现步骤是：1)读入一幅网络图S，并生成网络图S对应的邻接矩阵A；2)根据邻接矩阵A计算网络中每个节点的节点度，并查找网络核节点集合C；3)根据相似度函数值F更新网络节点标签集合f′；4)根据网络节点标签集合f′得到网络社区标签集合f；5)基于改进模块密度增量ΔD对当前网络中的社区进行迭代社区融合，输出最终网络节点标签集合f_z。本发明具有节点信息利用率高和社区分辨率高的优点，可用于社区检测。

主权项

一种基于核节点和社区融合策略的网络社区划分方法，包括如下步骤：(1)读入一幅网络图S，并生成网络图S对应的邻接矩阵A；(2)根据邻接矩阵A计算网络中每个节点的节点度，并根据网络中每个节点的节点度查找网络核节点集合C；(3)赋给网络中第i个节点一个唯一的标签i，i∈{1,2,...,n}，n表示网络中节点的数目，计算网络核节点集合C中每个核节点与其所有邻居节点的相似度函数值F，选出该函数值F大于等于给定阈值F_t＝1所对应的邻居节点，并将选出的邻居节点的标签更新为与其连接的核节点的标签，得到更新的网络节点标签集合f′＝{f₁′,f₂′,...,f_i′,...,f_n′}，其中f_i′表示网络中第i个节点的标签；(4)将网络节点标签集合f′＝{f₁′,f₂′,...,f_i′,...,f_n′}中相同标签对应的节点组成一个社区，得到当前网络社区标签集合f(1,1)＝{f₁(1,1),f₂(1,1),...,f_u(1,1),...,f_h(1)(1,1)}，并记录每个社区中包含的节点，其中，f_u(1,1)表示当前网络中第u个社区的标签，u∈{1,2,...,h(1)}，h(1)表示当前网络中的社区数目；(5)基于改进模块密度增量ΔD对当前网络中的社区进行迭代融合：5a)初始化循环次数g＝1；5b)统计当前网络社区标签集合f(g,1)＝{f₁(g,1),f₂(g,1),...,f_u(g,1),...,f_h(g)(g,1)}中每个社区与外界的连接数目l_o(g,1)＝{l_o1(g,1),l_o2(g,1),...,l_ou(g,1),...,l_oh(g)(g,1)}，其中f_u(g,1)表示网络中第u个社区在第g次循环时的标签，l_ou(g,1)表示网络中第u个社区在第g次循环时与外界的连接数目，u∈{1,2,...,h(g)}，h(g)表示网络中第g次循环时的社区数目；5c)将当前网络社区标签集合f(g,1)中的社区按与外界的连接数目l_o(g,1)降序排列，得到一个h(g)行2列的矩阵M(g)；5d)初始化社区融合迭代次数t＝1；5e)分别统计当前网络社区标签集合f(g,t)中每个社区的节点度之和d(g,t)、社区内节点间的连接数目l_i(g,t)、社区与外界的连接数目l_o(g,t)、社区u与其邻居社区v之间的连接数目l_uv(g,t)，其中：f(g,t)＝{f₁(g,t),f₂(g,t),...,f_u(g,t),...,f_h(g)(g,t)}，f_u(g,t)表示网络中第u个社区在第g次循环第t次迭代时的标签，d(g,t)＝{d₁(g,t),d₂(g,t),...,d_u(g,t),...,d_h(g)(g,t)}，d_u(g,t)表示网络中第u个社区在第g次循环第t次迭代时的节点度之和，l_i(g,t)＝{l_i1(g,t),l_i2(g,t),...,l_iu(g,t),...,l_ih(g)(g,t)}，l_iu(g,t)表示网络中第u个社区在第g次循环第t次迭代时社区内节点间的连接数目，l_o(g,t)＝{l_o1(g,t),l_o2(g,t),...,l_ou(g,t),...,l_oh(g)(g,t)}，l_ou(g,t)表示网络中第u个社区在第g次循环第t次迭代时与外界的连接数目，l_uv(g,t)＝{l_uv1(g,t),l_uv2(g,t),...,l_uvk(g,t)(g,t)}，l_uv(g,t)表示网络中第u个社区与其邻居社区v之间在第g次循环第t次迭代时的连接数目，k(g,t)表示网络中第g次循环第t次迭代时相互连接的社区对的数目；5f)计算当前网络中的社区u与其邻居社区v融合后所得的改进模块密度增量ΔD_uv：${\mathrm{\Delta D}}_{uv}=\frac{[l_{iu}-l_{ou}-l_{ov}+3l_{uv}]}{d_u+d_v}-[\frac{l_{iu}-l_{ou}}{d_u}+\frac{l_{iv}-l_{ov}}{d_v}],$其中，l_iu表示社区u内节点间的连接数目，l_ou表示社区u与外界的连接数目，l_ov表示社区v与外界的连接数目，l_uv表示社区u与v之间的连接数目，d_u表示社区u内节点的节点度之和，d_v表示社区v内节点的节点度之和，l_iv表示社区v内节点间的连接数目；5g)根据改进模块密度增量ΔD_uv得到矩阵M(g)中第t个社区p与其所有邻居社区融合所得的p社区融合增量集合ΔD_p，并找到集合ΔD_p中的最大值对应的邻居社区q；5h)根据改进模块密度增量ΔD_uv得到社区q与其所有邻居社区融合所得的q社区融合增量集合ΔD_q；5i)将p社区融合增量集合ΔD_p与q社区融合增量集合ΔD_q进行比较：若ΔD_p中的最大值大于等于ΔD_q中的最大值，则将社区p与社区q融合，即将当前网络社区标签集合f(g,t)中社区p的标签改为邻居社区q的标签，否则，不融合；5j)给定最大的社区融合迭代次数t_max＝h(g)，判断当前社区融合迭代次数t是否达到最大的社区融合迭代次数t_max，若达到，则终止迭代，并执行5k)，否则，t＝t+1，返回到5e)进行下一次迭代；5k)给定最大循环次数g_max＝100，判断当前循环次数g是否达到最大循环次数g_max，若达到，则终止循环，并将最终网络社区标签集合f(g_max,t_max)中的社区展开成最终网络节点标签集合f_z＝{f_z1,f_z2,...,f_zi,...,f_zn}输出，其中：f(g_max,t_max)＝{f₁(g_max,t_max),f₂(g_max,t_max),...,f_u(g_max,t_max),...,f_h(gmax)(g_max,t_max)}，f_u(g_max,t_max)表示达到最大循环次数g_max和最大的社区融合迭代次数t_max时网络社区标签集合中第u个社区的标签，u∈{1,2,...,h(g_max)}，h(g_max)表示网络中达到最大循环次数g_max时的社区数目，f_zi表示达到最大循环次数g_max时网络节点标签集合中第i个节点的标签，i∈{1,2,...,n}，n表示网络中的节点数目，否则，g＝g+1，返回到5b)进行下一次循环。