基于近邻传播的进化多目标优化社区检测方法

摘要

本发明涉及基于近邻传播的进化多目标优化社区检测方法，其特征是：包括如下步骤：步骤101：开始基于近邻传播的进化多目标优化社区检测方法；步骤102：读入一个网络的邻接矩阵；步骤103：设定相关参数；步骤104：选择基于信号的相似度测量方法；步骤105：选择近邻传播的聚类方法；步骤106：选择多目标进化算法；步骤107：依据步骤105得到的初步划分结果和步骤106得到的进一步划分结果；步骤108：结束基于近邻传播的进化多目标优化社区检测方法。通过本发明即可以实现对复杂网络的更精确、快速的划分。

说明书

技术领域

本发明属于计算机领域，涉及一种基于近邻传播的进化多目标优化社区检测方法，可用于人工网络和现实世界网络中社区结构的挖掘。 

背景技术

在现实生活中，复杂网络用来表示不同的系统内部或者系统间个体的相互关系。如互联网络、自然种群的生物网和人际社会网等。复杂网络中的社区检测则是指在复杂网络中寻找具有相同特征的节点所构成的子网络。因此，为了更好地分析复杂网络的结构和功能，社区检测近年来已成为一个重要的研究方向。 

目前社区检测的方法主要有基于节点相似度的层次聚类的算法、图划分方法和基于优化的社区检测方法。其中，基于目标函数优化的社区检测方法受到了广泛关注。例如，以优化模块度Q为代表的Newman贪婪算法，模拟退火的方法和极值优化的方法等。为了更好地解决这类离散型的优化问题，结合进化算法的社区检测方法已经成为一种流行趋势。进化算法通过模拟自然界中的生物进化过程，通过选择、重组和变异等操作实现对目标函数解的全局寻优。它具有几个良好特性，如：不受目标函数离散或者连续条件的限制、具有很好的全局寻优性以及与其他算法有较强的结合能力等。 

然而，由于目前采用的进化算法在社区检测问题中采用的初始种 群随机性强、质量较低，并且局部搜索能力差，导致算法收敛速度慢。同时进化算法还存在容易产生早熟和退化的问题，因此最终得到的结果准确度较低。 

发明内容

针对以上问题，本发明的目的是提供了一种基于近邻传播的进化多目标优化社区检测方法。本发明首先读入的网络的邻接矩阵，利用基于信号传递的相似度测量方法，将网络的拓扑信息转化为节点的相似度信息，然后利用近邻传播的方法进行聚类，并对聚类结果进行筛选，选取较优解作为多目标进化算法的初始种群，并在迭代过程中对种群不断进行重组、变异操作以增加种群多样性，并筛选出pareto占优解以更新解集，不断接近到全局最优解，以提高检测结果的准确度和算法收敛速度。其关键步骤就是利用近邻传播的方法对网络进行初步划分，以得到一组高质量的初始种群，从而提高算法收敛速度。同时对初步划分结果采用外部存档的精英保留策略，有效解决了进化算法搜索过程中的退化问题。 

本发明的技术方案是，基于近邻传播的进化多目标优化社区检测方法，其特征是：包括如下步骤： 

步骤101：开始基于近邻传播的进化多目标优化社区检测方法； 

步骤102：读入一个网络的邻接矩阵，标记为A； 

步骤103：设定相关参数； 

步骤104：选择基于信号的相似度测量方法，获取网络的负相似度矩阵，标记为S； 

步骤105：选择近邻传播的聚类方法，依据步骤104的得到的负相似度矩阵S，聚类得到网络的初步划分结果，标记为C_APOP； 

步骤106：选择多目标进化算法，依据步骤105中得到的结果作为初始种群，对网络划分结果进一步搜索，结果标记为C_APOPR； 

步骤107：依据步骤105得到的初步划分结果和步骤106得到的进一步划分结果，筛选出pareto占优解作为最终输出结果，标记为C_OPR； 

步骤108：结束基于近邻传播的进化多目标优化社区检测方法。 

所述的步骤104，包括如下步骤： 

步骤201：开始选择基于信号的相似度测量方法，获取网络的负相似度矩阵； 

步骤202：依据标记为A的邻接矩阵及公式V=(I_n+A)^t求出网络信号传递矩阵，标记为V，其中I_n表示的是n维单位矩阵，A表示的是网络的邻接矩阵，t表示的是传递时间，本发明中取值为3； 

步骤203：对V中所有行向量进行归一化处理，得到归一化矩阵，标记为U； 

步骤204：对U中所有行向量两两之间求负的欧式距离，得到网络的负相似度矩阵，标记为S； 

步骤205：结束选择基于信号的相似度测量方法，获取网络的负相似度矩阵，标记为S。 

所述步骤105，包括如下步骤： 

步骤301：开始依据选择的近邻传播的聚类方法和步骤104的得 到的负相似度矩阵S，聚类得到网络的初步划分结果； 

步骤302：设定偏向参数取值范围为[-10,0]，并在该范围内随机产生一组实数作为偏向参数的初始种群，标记为C； 

步骤303：根据C中每个实数值和负相似度矩阵S，利用近邻传播方法聚类得到对应划分结果，标记为C_AP， 

步骤304：对C_AP中划分结果进行相应处理，筛选出pareto占优解作为网络初步划分结果，标记为C_APOP。 

步骤305：结束依据步骤104的得到的负相似度矩阵S和选择的近邻传播的聚类方法，聚类得到网络的初步划分结果。 

所述步骤304，包括如下步骤： 

步骤401：开始对步骤303中得到的C_AP进行相应处理，筛选出pareto占优解作为网络初步划分结果； 

步骤402：分别依据连接度目标函数公式和负分割度目标函数公式其中m表示为网络的中社区数目，V_i表示社区i的顶点集合，L(V_i,V_i)表示社区i内节点总连接数，表示社区i内所有节点与社区i外其他节点连接数，|V_i|表示社区i节点数，计算C_AP中每条划分结果的目标函数值，计算结果分别标记为F₁和F₂； 

步骤403：根据步骤402中的得到的F₁和F₂，对C_AP中划分结果进行快速非支配排序，选取处于最高支配等级的非支配解集，标记为C_AP1； 

步骤404：根据步骤403得到的C_AP1所对应的目标函数值，计算种群个体间拥挤距离，选取具有较大拥挤距离前N_max的个体，作为网络初步划分结果，标记为C_APOP； 

步骤405：结束对步骤304中得到的C_AP进行相应处理，筛选出pareto占优解作为网络初步划分结果，标记为C_APOP； 

所述步骤106，包括如下步骤： 

步骤501：开始选择多目标进化算法，依据步骤105中得到的结果作为初始种群，对网络划分结果进行进一步搜索； 

步骤502：设置迭代次数,标记为g=0； 

步骤503：将步骤105得到的C_APOP作为初始种群，标记为C_IN； 

步骤504：对得到的种群C_IN其中的染色体进行交叉操作和变异操作，得到新的种群，标记为C_APOP1； 

步骤505：分别依据步骤402中所介绍的连接度目标函数公式 和负分割度目标函数公式计算步骤504得到的C_APOP1中染色体的目标函数值，分别标记为F₁₁和F₂₂； 

步骤506：根据步骤505中的得到的F₁₁和F₂₂，对C_AP中划分结果进行快速非支配排序，选取处于最高支配等级的非支配解集，标记为C_APOP11； 

步骤507：根据步骤506得到的C_APOP11所对应的目标函数值，计算种群个体间拥挤距离，选取具有较大拥挤距离前N_max的个体，作为本次迭代结果，标记为C_APOPR，同时将步骤507中得到的C_APOPR作为初始种群C_IN； 

步骤508：设置迭代次数g=g+1； 

步骤509：判断迭代次数是否大于或者等于最大迭代次数G_max，若是，则迭代终止，进行步骤510到步骤511；若不是，则进行步骤504到步骤509； 

步骤510：将步骤507中得到的C_APOPR作为输出结果； 

步骤511：结束选择多目标进化算法，依据步骤105中得到的结果作为初始种群，对网络划分结果进行进一步搜索。 

所述步骤504，包括如下步骤： 

步骤601：开始对得到的种群C_IN其中的染色体进行交叉操作和变异操作； 

步骤602：产生一个[0,1]间的随机数，标记为rd₁; 

步骤603：判断rd₁是否大于或者等于交叉概率p_c，若是，则进行步骤604；否则，执行步骤605； 

步骤604：依据双向交叉的方法，随机选取C_IN中两条染色体做父本，进行交叉操作，生成子代染色体，更新种群； 

步骤605：产生一个[0,1]间的随机数，标记为rd₂； 

步骤606：判断rd₂是否大于或者等于变异概率p_m，若是，则进行步骤607；否则，执行步骤609； 

步骤607：依据随机变异的方法，从种群中随机选取一条染色体，标记为r，并获取r中最大的标签数标记为l； 

步骤608：随机选取r染色体中1/5节点，对这些节点进行变异，随机变成不超过l的正整数； 

步骤609：更新交叉和变异后种群，标记为C_APOP1； 

步骤610：结束对C_IN其中的染色体进行交叉操作和变异操作，得到新的种群，标记为C_APOP1。 

所述步骤107，包括如下步骤： 

步骤701：开始依据步骤105得到的初步划分结果和步骤106得到的进一步划分结果，筛选出pareto占优解作为最终输出结果； 

步骤702：依据步骤105得到的结果C_APOP和步骤106得到的结果C_APOPR进行融合，形成新的解集，标记为C_APR； 

步骤703：分别依据步骤402中所介绍的连接度目标函数公式 和负分割度目标函数公式计算步骤702得到的C_APR中染色体的目标函数值，分别标记为Ff₁和Ff₂； 

步骤704：根据步骤703中的得到的Ff₁和Ff₂，对C_APR中划分结果进行快速非支配排序，选取处于最高支配等级的非支配解集，标记为C_OPR，并作为作为最终结果输出； 

步骤705：结束依据步骤105得到的初步划分结果和步骤106得到的进一步划分结果，筛选出pareto占优解作为最终输出结果。 

本发明的优点是：相比于传统的多目标进化算法，该发明实现了1）将AP方法对网络的预划分结果作为进化算法的初始种群，加快算法的收敛速度；2）采用进化多目标算法对初步划分结果进行进一步搜索，以逼近真实的pareto占优前端，促使结果达到全局最优；3）采用了外部存档的精英保留策略，对AP算法预划分结果予以保留，并参与到最终的pareto占优解选取中去，一定程度上防止了进化多目 标算法在搜索过程中结果产生退化的问题。通过本发明即可以实现对复杂网络的更精确、快速的划分。 

附图说明

图1基于近邻传播的进化多目标优化社区检测方法的主流程图； 

图2选择基于信号的相似度测量方法，获取网络的负相似度矩阵的主流程图； 

图3选择的近邻传播的聚类方法和得到的负相似度矩阵S，聚类得到网络的初步划分结果流程图； 

图4开始对步骤303中得到的C_AP进行相应处理，筛选出pareto占优解作为网络初步划分结果的流程图； 

图5选择多目标进化算法，依据步骤105中得到的结果作为初始种群，对网络划分结果进行进一步搜索的流程图； 

图6对得到的种群C_IN其中的染色体进行交叉操作和变异操作的流程图； 

图7依据步骤105得到的初步划分结果和步骤106得到的进一步划分结果，筛选出pareto占优解作为最终输出结果的流程图； 

图8为本发明和现有的遗传算法对海豚网络的划分结果对比图； 

图9为本发明与现有遗传算法分别海豚网络进行划分后的互信息NMI参数的比较图； 

图10为本发明和现有的遗传算法对政治书网络的划分结果对比图； 

图11为本发明与现有遗传算法分别政治书网络进行划分后的互信息NMI参数的比较图。 

具体实施方式

基于近邻传播的进化多目标优化社区检测方法，其关键步骤是利用近邻传播算法获取网络的初步划分结果，作为进化多目标算法的初始种群。这样将数据聚类的方法和多目标进化的方法融合在一起，不仅可以借助近邻传播聚类方法聚类速度快的优势，同时又能利用多目标进化的方法确保结果可以达到全局最优。 

基于近邻传播的进化多目标优化社区检测方法的特征是：首先采用用基于信号传递的相似度度量方法将图聚类问题转化为数据聚类的问题，运用近邻传播方法对网络进行初步划分；其次，将得到的pareto占优解作为初始种群，采用进化多目标算法进行进一步搜索，通过交叉、变异的方式不断更新种群和pareto占优前端；最后，将两部分pareto占优解合并，筛选出最终的pareto占优解集。利用AP算法聚类的准确性，可以快速找到一组较优解，同时利用进化多目标算法的多样性和多点搜索的特点，进一步搜索达到全局最优。 

如图1所示, 

主流程图步骤特征是： 

步骤101：开始基于近邻传播的进化多目标优化社区检测方法； 

步骤102：读入一个网络的邻接矩阵，标记为A； 

步骤103：设定相关参数：偏向参数P的种群大小N_umP为100，最大pareto占优解个数N_max为40，交叉概率p_c为1，变异概率p_m为 0.8，最大迭代次数G_max为50； 

步骤104：选择基于信号的相似度测量方法，获取网络的负相似度矩阵，标记为S； 

步骤105：选择近邻传播的聚类方法，依据步骤104的得到的负相似度矩阵S，聚类得到网络的初步划分结果，标记为C_APOP； 

步骤106：选择多目标进化算法，依据步骤105中得到的结果作为初始种群，对网络划分结果进一步搜索，结果标记为C_APOPR； 

步骤107：依据步骤105得到的初步划分结果和步骤106得到的进一步划分结果，筛选出pareto占优解作为最终输出结果，标记为C_OPR； 

步骤108：结束基于近邻传播的进化多目标优化社区检测方法。 

如图2所示， 

所述的步骤104，包括如下步骤： 

步骤201：开始选择基于信号的相似度测量方法，获取网络的负相似度矩阵； 

步骤202：依据标记为A的邻接矩阵及公式V=(I_n+A)^t求出网络信号传递矩阵，标记为V，其中I_n表示的是n维单位矩阵，A表示的是网络的邻接矩阵，t表示的是传递时间，本发明中取值为3； 

步骤203：对V中所有行向量进行归一化处理，得到归一化矩阵，标记为U； 

步骤204：对U中所有行向量两两之间求负的欧式距离，得到网络的负相似度矩阵，标记为S； 

步骤205：结束选择基于信号的相似度测量方法，获取网络的负相似度矩阵，标记为S。 

如图3所示， 

所述步骤105，包括如下步骤： 

步骤301：开始依据选择的近邻传播的聚类方法和步骤104的得到的负相似度矩阵S，聚类得到网络的初步划分结果； 

步骤302：设定偏向参数取值范围为[-10,0]，并在该范围内随机产生N_umP个实数作为偏向参数的初始种群，标记为C； 

步骤303：根据C中每个实数值和负相似度矩阵S，利用近邻传播方法聚类得到对应划分结果，标记为C_AP， 

步骤304：对C_AP中划分结果进行相应处理，筛选出pareto占优解作为网络初步划分结果，标记为C_APOP。 

步骤305：结束依据步骤104的得到的负相似度矩阵S和选择的近邻传播的聚类方法，聚类得到网络的初步划分结果。 

如图4所示， 

所述步骤304，包括如下步骤： 

步骤401：开始对步骤303中得到的C_AP进行相应处理，筛选出pareto占优解作为网络初步划分结果； 

步骤402：分别依据连接度目标函数公式和负分割度目标函数公式其中m表示为网络的中社区数目，V_i表示社区i的顶点集合，L(V_i,V_i)表示社区i内节点总连接数， 表示社区i内所有节点与社区i外其他节点连接数，|V_i|表示社区i节点数，计算C_AP中每条划分结果的目标函数值，计算结果分别标记为F₁和F₂； 

步骤403：根据步骤402中的得到的F₁和F₂，对C_AP中划分结果进行快速非支配排序，选取处于最高支配等级的非支配解集，标记为C_AP1； 

步骤404：根据步骤403得到的C_AP1所对应的目标函数值，计算种群个体间拥挤距离，选取具有较大拥挤距离前N_max的个体，作为网络初步划分结果，标记为C_APOP； 

步骤405：结束对步骤304中得到的C_AP进行相应处理，筛选出pareto占优解作为网络初步划分结果，标记为C_APOP； 

如图5所示， 

所述步骤106，包括如下步骤： 

步骤501：开始选择多目标进化算法，依据步骤105中得到的结果作为初始种群，对网络划分结果进行进一步搜索； 

步骤502：设置迭代次数,标记为g=0； 

步骤503：将步骤105得到的C_APOP作为初始种群，标记为C_IN； 

步骤504：对步骤得到的种群C_IN其中的染色体进行交叉操作和变异操作，得到新的种群，标记为C_APOP1； 

步骤505：分别依据步骤402中所介绍的连接度目标函数公式 和负分割度目标函数公式计算步骤504得到的C_APOP1中染色体的目标函数值，分别标记为F₁₁和F₂₂； 

步骤506：根据步骤505中的得到的F₁₁和F₂₂，对C_AP中划分结果进行快速非支配排序，选取处于最高支配等级的非支配解集，标记为C_APOP11； 

步骤507：根据步骤506得到的C_APOP11所对应的目标函数值，计算种群个体间拥挤距离，选取具有较大拥挤距离前N_max的个体，作为本次迭代结果，标记为C_APOPR，同时将步骤507中得到的C_APOPR作为初始种群C_IN； 

步骤508：设置迭代次数g=g+1； 

步骤509：判断迭代次数是否大于或者等于最大迭代次数G_max，若是，则迭代终止，进行步骤510到步骤511；若不是，则进行步骤504到步骤509； 

步骤510：将步骤507中得到的C_APOPR作为输出结果； 

步骤511：结束选择多目标进化算法，依据步骤105中得到的结果作为初始种群，对网络划分结果进行进一步搜索。 

如图6所示， 

所述步骤504，包括如下步骤： 

步骤601：开始对得到的种群C_IN其中的染色体进行交叉操作和变异操作； 

步骤602：产生一个[0,1]间的随机数，标记为rd₁; 

步骤603：判断rd₁是否大于或者等于交叉概率p_c，若是，则进行步骤604；否则，执行步骤605； 

步骤604：依据双向交叉的方法，随机选取C_IN中两条染色体做 父本，进行交叉操作，生成子代染色体，更新种群； 

步骤605：产生一个[0,1]间的随机数，标记为rd₂； 

步骤606：判断rd₂是否大于或者等于变异概率p_m，若是，则进行步骤607；否则，执行步骤609； 

步骤607：依据随机变异的方法，从种群中随机选取一条染色体，标记为r，并获取r中最大的标签数标记为l； 

步骤608：随机选取r染色体中1/5节点，对这些节点进行变异，随机变成不超过l的正整数； 

步骤609：更新交叉和变异后种群，标记为C_APOP1； 

步骤610：结束对C_IN其中的染色体进行交叉操作和变异操作，得到新的种群，标记为C_APOP1。 

如图7所示， 

所述步骤107，包括如下步骤： 

步骤701：开始依据步骤105得到的初步划分结果和步骤106得到的进一步划分结果，筛选出pareto占优解作为最终输出结果； 

步骤702：依据步骤105得到的结果C_APOP和步骤106得到的结果C_APOPR进行融合，形成新的解集，标记为C_APR； 

步骤703：分别依据步骤402中所介绍的连接度目标函数公式 和负分割度目标函数公式计算步骤702得到的C_APR中染色体的目标函数值，分别标记为Ff₁和Ff₂； 

步骤704：根据步骤703中的得到的Ff₁和Ff₂，对C_APR中划分结果进行快速非支配排序，选取处于最高支配等级的非支配解集，标记 为C_OPR，并作为作为最终结果输出； 

步骤705：结束依据步骤105得到的初步划分结果和步骤106得到的进一步划分结果，筛选出pareto占优解作为最终输出结果。 

本实施例没有详细叙述的部分属本行业的公知的常用手段，这里不一一叙述。 

本发明的效果可以通过以下仿真实验进一步说明： 

1.实验条件： 

在CPU为core22.26GHZ、内存2G、WINDOWS7系统上使用MATLAB2010进行仿真。 

2.实验内容： 

实验1，利用本发明和现存遗传算法对图8(a)所示的海豚网络进行社区的划分。海豚网络共有62个节点，159条边，其中1到62分别表示节点的编号，三角形和正方形分别为自然划分的两类社区。图8(b)为现有遗传算法对图8(a)所示的海豚网络进行社区的划分结果；图8(c)为本发明对图8(a)所示的海豚网络进行社区的划分结果。 

实验2，利用本发明和现存遗传算法对图10(a)所示的政治书网络进行社区的划分。海豚网络共有105个节点，其中1到115分别表示节点的编号，三种不同的圆形表示该网络三种不同社区的划分。图10(b)为现有遗传算法对图10(a)所示的政治书网络进行社区的划分结果；图10(c)为本发明对图10(a)所示的政治书网络进行社区的划分结果。 

3.实验结果： 

由图8(b)可知，现有遗传算法将海豚网络错误的划分为4个社区，而对比图8(b)和图8(c)，本发明的划分结果完全正确，与网络的真实划分结果一致。 

图9为本发明和现有遗传算法在海豚网络50次迭代中所得到的互信息NMI指标的值的变化情况。其中NMI反映的是社区划分结果与实际划分结果相比的准确率。由图3可以看出，现有遗传算法则一直运行到50代，其划分结果的NMI值也没有达到1，而本发明在运行到第5代左右即获得对海豚网络的完全正确的划分结果。说明本发明在对海豚网络的划分上，收敛速度快，划分结果更加准确。 

由图10(b)可知，虽然现有遗传算法将政治书网络正确的划分为3个社区，但是误分点较多，有21个节点被误分，而对比图10(b)和图10(c)，本发明的划分结果具有更少的误分点，仅误分13个节点，划分结果更加接近真实网络。 

图11为本发明和现有遗传算法在政治书网络50次迭代中所得到的互信息NMI指标的值的变化情况。由图11可以看出，本发明最终得到的NMI值要高于现有遗传算法划分结果的NMI值，说明本发明在政治书网络的划分上具有更高的准确性。