网络社区检测的一种新型混合算法

路 延

（陕西职业技术学院,710100）

网络社区检测的一种新型混合算法

路 延

（陕西职业技术学院,710100）

本文中介绍结合粒子群优化算法和非负矩阵分解算法，得到了一种新型社区检测的谱聚类算法PNMF-Net。这个算法将模块度作为目标函数。由于PSO算法容易陷入局部最优，对粒子群算法中个体历史最优粒子使用NMF搜索。同时NMF算法可以减小搜索空间，自动找到网络社区数。最后使用人工合成网络和四组真实网络对PNMF-Net进行测试，结果证明提出的谱聚类算法可以有效地检测出网络中固有的社区。

社区检测;谱聚类;粒子群优化

0 引言

社区检测是识别出网络中存在的社区结构或者层次结构，即按照节点之间的连接关系将节点划分为若干群簇，其中群簇内部的边连接稠密，不同群簇之间连接稀疏。目前被用于社会网络分析、蛋白质功能网络分析、及Web网络挖掘、Web文本聚类等领域。本文提出了一种改进的PSO算法用于社区检测，对粒子个体历史最优值使用NMF搜索增强了粒子搜索能力。

1 新型社区检测算法PNMF-Net步骤

新型社区检测算法PNMF-Net通过NMF算法的搜索性能来增强PSO算法搜索能力。

先给出算法的基本框架，算法步骤如下：

输入：网络邻接矩阵V

输出：节点所在的社区向量，社区分类数c，NMI值

步骤（1）根据网络节点数随机产生节点的社区号向量x，作为PSO算法中粒子的位置，并多次产生粒子得到粒子种群，令s=1；

步骤（2）重复以下步骤，直到满足约束条件，①根据节点数随机初始化粒子种群中的粒子初始速度，计算每个粒子的适应度值，并将最优粒子作为个gbest，将当前粒子的位置赋给pbest；②根据标准粒子群算法更新粒子种群的速度和位置；③更新粒子种群的pbest和gbest；

步骤（3）保留上述最优的1/5的pbest的粒子；

步骤（4）对上述保留的粒子使用NMF搜索；

步骤（5）若满足终止条件则输出最优粒子；

步骤（6）减小搜索范围，求出NMF搜索后粒子的最大社区数作为后面社区的数量；

步骤（7）随机产生4/5的粒子种群数的粒子，与上面优化后的1/5个粒子组成新的粒子种群；

步骤（8）令s=s+1，返回步骤（2）。

1.1 粒子表示

本方法中对粒子的编码采用最简单的编码，即随机初始化每个粒子的社区号作为PSO的初始粒子。假设社区数量为k，网络节点为n，则每个粒子的大小为，社区号小于k。

1.2 初始化

对于粒子群初始化，采用1.1中粒子表示方法随机产生一定

数量的粒子得到粒子群。对于粒子速度，随机选取在[1,c/2]之间的整数。鉴于使用的NMF算法具有自适应性，即算法在计算过程中排除无意义的社区划分，得到最佳社区数量。因此不需要事先定义好社区具体的数量。当初始社区定义过大则需要浪费许多无意义的操作，如果小于真实社区数量，结果将不正确。在此，初始社区数设为。

1.3 NMF局部搜索算子

由于PSO算法容易陷入局部最优，对于PSO中较好的pbest使用NMF搜索来改善搜索结果。首先将pbest转换成一个0,1矩阵，为了保证随机性，对上述矩阵加上一个随机产生的相同大小的随机矩阵，然后对其进行归一化作为NMF的初始化。使用的是无方向网络，使用。

当优化完保留的粒子个体最优时，减小粒子的搜索空间。对优化后的粒子，求出每个粒子的社区数c，然后使用[1,c]之间的整数取代每个粒子对应的社区号。最后对整体的社区数k选取优化后粒子最大的c。

下面给出NMF搜索步骤算法：NMF搜索算子

输入：网络的邻接矩阵V，需要优化的粒子pbest，参数：迭代次数iter，a，b

输出：自适应得到的社区数k，网络隶属度矩阵W

步骤（2）For i=1:iter do

步骤（3）end for

步骤（4）去掉W全零行，并对W归一化；

步骤（5）求得W非零行数k；

步骤（6）将隶属度矩阵转换成对应的社区号；

2 实验结果及对比

2.1 实验设计与评价指标

使用本算法对合成的数据进行测试来证明提出的新算法在社区检测中的有效性。实验结果表明新算法可以正确的检测出网络的固有结构。

算法是使用matlab程序进行编写，实验平台为core i3，内存为3.05GB，操作系统为windows XP，软件版本为MATLAB2010a的hp计算机。

参数的选取如下：整个程序运行代数s=5,粒子群个体为20，PSO迭代代数为20，惯性系数w=0.729，常数c1=c2=1.49445， NMF迭代次数为10。

给定同一网络的两种不同分割A和B，假设C是一个模糊矩阵，其中元素cij是存在网络划分A中社区i，同时也存在于网络划分B中社区j的中节点数量。评价社区检测结果正确性的函数NMI值定义为

2.2 人工合成网络测试

使用benchmark网络，这个benchmark网络有128个节点，分为4个社区，每个社区有32个节点，节点的平均度为16。为了测试结果的正确性，使用NMI值（Normalized Mutual Information）作为标准。

选取GN算法、PSO算法、NMF算法和Meme-Net作为对比算法。NMF算法使用贝叶斯非负矩阵分解算法，PSO算法中使用带惯性常数的更新规则，粒子数设为200，迭代次数为100，其余参数使用PNMF-Net中相同的参数。Meme-Net在此使用。对每种算法运行30次求的平均值作为结果。图1是不同的算法在测试这个网络得到的NMI值折线图。从图上可以看到随着k-out的增大，所有算法的NMI值都会减小，即随着k-out的增加，算法正确检测出社区结构越困难。因此可以看出新算法检测这个数据网络社区的效果是可靠的。

图1 不同的算法在处理GNbenchmark数据得到的NMI值比较图。

3 结论

本文利用了PSO算法全局搜索能力和NMF在结果上可解释性、可自适应决定分解后特征矩阵的维数等优势。算法的创新点

可概括为以下两点：

（1）认为PSO算法容易陷入局部最优和初始化有着密不可分的关系。基于此对第二次开始的迭代使用的粒子为NMF搜索得到的粒子和随机初始化得到的粒子，丰富了粒子的多样性。

（2）分析表明PSO算法虽然是全搜索算法，但其搜索范围往往不能再全局进行搜索。对PSO搜索得到的个体历史最优进行NMF搜索得到较好的粒子，一定程度上增大了PSO在整个搜索范围搜索的概率。

[1] Girvan M,Newman MEJ.Community structure in social and biological networks.Proc.Natl.Acad. Sci.USA . 2002,99(12).7821-7826.

[2] 雷德明，严新平.多目标智能优化算法及其应用.北京:科学出版社.2009年3月. 10-12

[3] Pizzuti C.A multi-objective genetic algorithm for community detection in networks,in:Proceedings of the 21st IEEE International Conference on Tools with Artificial Intelligence,Newark,New Jersey, USA.2009.397-386

路延，（1985-），女，陕西职业技术学院助教，主要研究方向为计算机应用、图像识别。

A network of community testing new hybrid algorithm

Lu Yan
(shaanxi vocational & technical college,710100)

In this paper,a novel spectral algorithm(PNMF-Net)to detect communities by combining the algorithms of Particle Swarm Optimization(PSO)and Nonnegative Matrix Factorization(NMF)is proposed.The proposed method optimizes a quality function known as modularity.As PSO may prematurely converge on local optimal solutions,NMF is applied for exploitation by locally modified some better particles resulted by PSO.Meanwhile,NMF narrow the searching space and automatically detect the number of communities of networks.Finally experiments on artificial and real world networks are presented to show the effectiveness of the proposed method.

Community detection;spectral clustering;particle swarm optimization