基于贪婪局部路径重连的随机并行社区检测

发布时间：2021-10-18 16:52

　　为提高社区检测的效率与精度,提出一种随机并行的局部搜索算法。用图模型结构表示复杂系统,将顶点划分成簇。构建贪婪随机自适应搜索过程与路径重连过程,以解决加权图的模块最大化问题。引入一种{0,1}矩阵类特征并定义聚类的距离函数,从而进行顶点的邻域搜索,实现社区的高精度检测识别。实验结果表明,该算法的F₁值与NMI指标值均较高。 

【文章来源】：计算机工程. 2019,45(06)北大核心CSCD

【文章页数】：7 页

【部分图文】：

随机图H的构造过程示例可利用顶点集V(H)=V(G)和如下的边集概

计算机工程2019年6月15日图4所示为4种网络模型，其参数数据分别对应表1中的第1行、第3行，表2中的第1行、第3行。图4人工生成网络模型3．2稳健性实验本节对各社区发现算法的F1值进行对比测试，F1值的取值范围是0～1，其值越大，表明分类模型的稳健性越高。F1评价指标定义为:F1=2PRP+R=2TP+FP+FNTP(31)其中，FP指实际为正但检测为负的样本，FN指实际为负但检测为正的样本，TP指实际为正且检测为正的样本，P为准确率，R为召回率。本次实验选取的对比算法为文献［14］算法和文献［15］算法。前者是一种社会网络中线性时间重叠的社区检测方法，其采用增量式的社区检测算法，具有较强的社区检测能力和较高的社区检测速度;后者是一种基于社区检测质量的算法，具有较高的社区检测精度。在图4所示的4种网络模型中，3种算法的F1值对比结果如图5所示。由图5可以看出，3种算法的F1值都随着社区数量的增加而降低，即模型的稳健性降低。其中，与2种对比算法相比，本文算法的F1值均较大，这体现了其在社区发现稳健性上的优势。图53种算法的F1值对比结果3．3准确性实验本节选取NMI指标度量2个聚类结果的相近程度，以评价社区发现算法的准确性。NMI的值域是0～1，值越高代表算法准确性越高。对于2种社区类型A、B，其NMI指标定义为:NMI=－2∑CAi=1∑CBj=1Cij·lbCijNCiC()j∑CAi=1Ci·lbCi．()N+∑CBj=1Cij·lbC．j(

【参考文献】：
期刊论文
[1]基于KL散度及多尺度融合的显著性区域检测算法[J]. 罗会兰,万成涛,孔繁胜.  电子与信息学报. 2016(07)
[2]基于用户聚类的异构社交网络推荐算法[J]. 陈克寒,韩盼盼,吴健.  计算机学报. 2013(02)
[3]一种改进的加权复杂网络聚类方法[J]. 郭陶,张琨,郭文娟,庄克琛,贺定龙,李配配.  计算机科学. 2012(S1)
[4]一种基于修正的最小生成树及其邻接谱的特征匹配算法[J]. 宣善立,梁栋,朱明,范益政,王年.  电子学报. 2010(02)



本文编号：3443148