基于GPU加速的网络社区检测方法

摘要

本发明公开了一种基于GPU加速的网络社区检测方法，主要解决传统NMF网络社区检测方法的运行时间过长，占用空间过多的问题。其实现过程为：(1)构造网络的邻接矩阵；(2)检查网络类型是否满足要求并对邻接矩阵进行预处理；(3)对预处理之后的邻接矩阵进行稀疏表示；(4)对GPU设备进行初始化；(5)将稀疏表示的邻接矩阵传入到GPU设备中；(6)在GPU中进行网络社区检测；(7)将得到的检测结果从GPU设备传到内存中进行归一化处理，得到网络的重叠划分；(8)由重叠划分得到网络的硬化分。本发明利用GPU对NMF社区检测方法进行并行加速，大幅降低了社区检测的运行时间及存储空间，并可处理更大规模的网络数据。

主权项

1.一种基于GPU加速的网络社区检测方法，包括如下步骤：(1)构造大小为n×n的网络邻接矩阵A，n为网络中节点的数目；(2)检查网络是否满足无方向无权重的条件特征，若满足该条件，则去除网络中的孤立节点，即网络中与其他任何节点都没有联系的节点，否则该网络无法处理，退出程序；(3)对邻接矩阵A采用行格式存储法CSR进行稀疏表示，得到列坐标向量Aj和行首位置向量Ap，同时采用列格式存储法CSC进行稀疏表示，得到行坐标向量Bj和列首位置向量Bp；(4)利用OpenCL编程框架对GPU设备进行初始化：选择OpenCL平台，得到OpenCL设备，创建命令队列，创建内存对象，创建OpenCL程序对象，创建核函数对象；(5)利用0-1之间的随机数分别构造大小为n×k的左分解矩阵W、大小为k×n的右分解矩阵H、大小为1×k的中间向量β，其中k为预设的社区数目，将所述W、H、β、Ap、Aj、Bp和Bj传输到GPU全局内存中；(6)在GPU中进行网络社区结构检测：6a)根据上面得到的W、H矩阵以及β向量，计算第一临时变量：T1＝W/(1_n×nH^T+Wdiag(β))，其中1_n×n代表大小为n×n的单位矩阵，H^T代表H矩阵的转置，diag(β)代表β向量的对角矩阵，/代表矩阵间的点除操作；6b)根据步骤(2)得到的A_p和A_j，计算第二临时变量：T2＝A/(WH)，其中A为网络的邻接矩阵；6c)根据第二临时变量T2，计算第三临时变量：T3＝T2*H^T；6d)根据第一临时变量T1和第三临时变量T3对左分解矩阵W进行更新，即$W\leftarrow T1·T3=\frac{W}{1_{n\times n}{H}^T+\mathrm{Wdiag}\left(\beta \right)}·\left[\left(\frac{A}{\mathrm{WH}}\right)H^T\right],$其中·代表两个矩阵的点乘操作，←表示用计算结果替换掉原W矩阵；6e)计算第四临时变量：T4＝(H·H)1_n×1，其中1_n×1代表大小为n×1的单位向量；6f)根据步骤6d)得到的左邻接矩阵W，计算第五临时变量：T5＝1_1×n(W·W)，其中1_1×n代表大小为1×n的单位向量；6g)根据第四临时变量T4及第五临时变量T5对中间向量β进行更新：β＝(2n+a)/(T4+T5+b)其中，分子参数a固定为8，分母参数b固定为2；6h)根据左分解矩阵W、右分解矩阵H、中间向量β，计算第六临时变量：T6＝H/(W^T1_n×n+diag(β)H)，W^T代表W矩阵的转置；6i)根据步骤(2)得到的B_p、B_j，计算第七临时变量：T7＝A/(WH)；6j)根据第七临时变量T7计算第八临时变量：T8＝W^T*T7；6k)根据第六临时变量T6和第八临时变量T8，对右分解矩阵H进行更新，即：$H\leftarrow T6·T8=\frac{W}{{W^{T}1}_{n\times n}+\mathrm{diag}\left(\beta \right)H}·\left[W^T\left(\frac{A}{\mathrm{WH}}\right)\right],$6l)重复执行步骤6a)到6k)共100次，得到最终的左分解矩阵W'；(7)将最终的左分解矩阵W’通过GPU传到计算机内存中，对该最终的左分解矩阵W'中元素按行进行归一化，得到网络的重叠划分矩阵M：$M=\left[\begin{array}{cccc}{m}_{11}& m_{12}& ...& m_{1k}\\ m_{21}& m_{22}& ...& m_{21}\\ .& .& & .\\ .& .& m_{\mathrm{ij}}& .\\ .& .& & .\\ m_{n1}& m_{n2}& ...& m_{\mathrm{nk}}\end{array}\right]$$m_{\mathrm{ij}}=\frac{{w^{\prime }}_{\mathrm{ij}}}{{\Sigma }_{j=1}^k{w^{\prime }}_{\mathrm{ij}}}$其中，w'_ij表示最终的左分解矩阵W'第i行第j列的元素，m_ij代表重叠划分矩阵M的第i行第j列的元素；(8)根据重叠划分矩阵M得到网络的重叠划分：对于网络中的第i个节点，若M中第i行的任一元素m_ij不等于0，则将该节点划分到第j个社区中且隶属概率为m_ij，否则,该节点不属于第j个社区；(9)根据网络的重叠划分，将节点划分到隶属概率最大的社区，得到网络的硬化分结果。