论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

　　首先分析第1部分:Step1是算法相关参数的设置,为常量复杂度O(1);2072JournalofSoftware软件学报Vol.24,No.9,September2013对于Step2,令网络的节点平均度数为d,又由于真实网络的d往往是一个很小的常量,建立各节点的邻居有序表的复杂度为O(d.n.logd),故有复杂度O(n);Step3是粒子的初始化,则其复杂度为O(n.k).故第1部分的复杂度为O(n.k).

　　然后分析第2部分:Step4计算粒子适应度向量,若令一次迭代产生r个社区,社区的平均大小为[n/r],则社区内链接度的计算复杂度为O(r.(n/r)2)=O(n2/r),社区间链接度的计算复杂度为O(r.(n/r)2.(r.1)).O(n2).故Step4的复杂度约为O(n2).Step5是进行粒子的Pareto支配关系比较,需要耗费时间为O(k2);Step6是调用UpdatePS算法,由于此处ObjNum为常量3,故其时间复杂度为O(n2.ObjNum.MAXP.|CurBestP|)=O(n2.MAXP.|CurBestP|);Step7调用时间复杂度为leaderSelection算法,由第4.3节得知,其时间复杂度为O(N.b.|NonSet|),由于.Nb.k且|NonSet|≤k,故该步骤在最坏情形下的复杂度为O((nk)2);Step8的计算复杂度为O(n.k);Step9是停止条件(迭代次数)判定,为常量复杂度O(1).故算法第2部分的时间复杂度为O(t.n2.max(k2,MAXP.|CurBestP|)).

　　综合上述分析可知,MOCD-PSO算法的复杂度为O(t.n2.max(k2,MAXP.|CurBestP|)).由于MOCD-PSO算法是建立在多目标粒子群优化算法的框架之上,故算法收敛性的相关理论证明见文献.

　　5、实验与分析

　　本文实验的硬件环境是:CPU为3.4GHz的Intel(R)Core(TM)i7-2600,内存4G;软件环境为Windows7+MatlabR2010.

　　5.1数据集

　　我们在3个真实网络与3个人工网络上对MOCD-PSO算法进行实验分析.3个真实网络分别是:第1个是Karate网络,该网络是美国一所大学中的空手道俱乐部成员间的相互社会关系,共有34个节点,78条连接边;第2个是Dolphins网络,共有62个节点、159条边;第3个是HLM网络,该网络包含77个节点,121条边,主要依据名著《红楼梦》中的血缘关系与典型的媒介关系构造5个家族(宁国府、荣国府、王府、史府和薛府)之间的社会关系网络.3个人工网络是由LFR网络数据生成器[35]模拟生成的.

　　5.2收敛性分析

　　为了评价MOCD-PSO算法的收敛性,我们引入世代距离(generationdistance,简称GD)作为评价标准,GD指标定义为公式(15).GD越小,说明求得的Pareto最优解集越逼近全局最优解集,即算法收敛性也越好.

　　5.3最优解分布

　　本节从Pareto最优解的分布均匀性与分散度两个方面对MOCD-PSO算法生成的Pareto最优社区结构集进行分析.首先利用SP指标描述Pareto最优解在目标空间上的分布均匀性,令网络节点数是r,kFi表示第i个粒子的第k维,SP指标可定义为公式(16)~公式(18),SP越小,则意味着Pareto最优解集分布越均匀.可以看出,本文的启发式更新策略能使Pareto最优社区结构集的解分布得更加均匀.然后运用Pareto最优解集的统计量全距(range)(公式(19))进行其分散度分析,可以看出,本文的启发式更新策略能使Pareto最优社区结构集的解分布更加分散,并且最优解的个数与网络节点数、网络模块度相关.

　　5.4有效性分析

　　为了测评MOCD-PSO算法的有效性,我们采用规范化互信息(normalizedmutualinformation,简称NMI)的评价标准来衡量MOCD-PSO算法的计算结果社区与网络真实社区相一致的程度(公式(20)),该值越大,意味着计算结果社区与网络真实社区相吻合的程度越高.将MOCD-PSO算法与4个代表性社区发现算法(GN,2074JournalofSoftware软件学报Vol.24,No.9,September2013GA-Net,MOGA-Net与SCAH-MOHSA)进行比较分析,其中,前二者为单目标优化算法,后二者为多目标优化算法.给出了各种算法在6个实验网络上分别运行50次所得的NMI的均值与方差.与单目标算法GN与GA-Net相比较,MOCD-PSO算法发现的社区结构质量要远远高于这二者的结果社区结构质量,在诸如Karate与Dophins之类的社区结构模块性较强的网络中,能够准确发现网络的真实社区结构.与多目标优化算法MOGA-Net与SCAH-MOHSA相比较,不仅从均值Min_Avg(公式(21))意义上看,MOCD-PSO算法展现出明显的优势,而且从方差Max_Std(公式(22))意义上看,MOCD-PSO算法的最佳结果社区结构的NMI的分布更加均匀,因而,我们的方法具有更强的鲁棒性.

　　5.5时间效率分析

　　为了评价MOCD-PSO算法的时间性能,我们将MOCD-PSO算法与上述两种基于多目标优化的社区发现算法(MOGA-Net与SCAH-MOHSA)进行比较分析.为了更好地对这3种超启发式的随机搜索算法进行时间性能比较,我们将最大迭代次数的循环终止条件修改为网络社区结构的Max_Avg大于某个指定阈值.值得指出的是,我们没有选择GN算法与GA-Net作为比较对象,主要出于这样的考虑:一般来说,基于单目标优化的社区发现算法在时间性能上要优于基于多目标优化的社区发现算法,由于基于多目标优化的社区发现算法需要多个目标函数值,而且目标函数估值是优化算法中的重要耗时部件.图5给出了3种算法在6个实验网络上分别运黄发良等:基于多目标优化的网络社区发现方法2075行50次所得的耗费时间的均值.从图5可以看出:在小规模的真实网络Karate与Dolphins中,MOCD-PSO的耗时与其他两种算法的耗时相当;在网络HLM与SynNet_1上,MOCD-PSO逐步体现出时间效率优势,但优势相对微弱;而在规模更大的网络SynNet_2与SynNet_3上,这种时间效率优势就变得显著.由此不难得出这样的结论:

　　与其他两个基于多目标优化的社区发现算法(MOGA-Net与SCAH-MOHSA)相比较,随着网络规模的增加,3种算法的耗时都会增加,但MOCD-PSO耗时增长速度要远低于其他两种算法,即MOCD-PSO具有更好的可扩展性.

　　6、结束语

　　复杂网络社区发现研究对互联网文化安全与信息个性化服务等多个方面都有着重要的意义,当前,绝大多数基于生物启发优化的复杂网络社区发现算法都是以某种单一的社区结构质量测度目标来驱动的,而社区质量评判指标的多样性使得网络社区结构分析的实践人员在面对众多的评判指标难以决策,并且现实的复杂网络隐含的真实社区结构不是通过单一测度指标能完全反映出来的.本文通过大量的实验发现了社区质量评判指标的数据依赖性与耦合关联性,分析了这两种性质导致基于单一评判指标优化的网络社区发现算法所具有的局限性.因此,本文进一步将复杂网络社区发现问题形式化为多目标优化问题,同时提出了基于多目标粒子群优化的网络社区发现算法MOCD-PSO,在此算法中,我们提出了新的Pareto最优网络社区结构集更新策略并予以巧妙地实现,选取模块度指标Q、最小最大割指标MinMaxCut与轮廓(silhouette)指标来构建MOCD-PSO的优化.实验结果表明,MOCD-PSO算法具有较好的收敛性,能发现分布均匀且分散度较高的Pareto最优网络社区结构集,并且无论与单目标优化方法(GN与GA-Net)相比较,还是与多目标优化算法(MOGA-Net与SCAHMOHSA)相比较,MOCD-PSO算法所发现的Pareto最优网络社区结构与网络内在社区结构更相吻合.

　　参考文献: