基于节点拓扑结构和属性的重叠社区检测算法-计算机应用研究.pdfVIP

第３３卷第１２期 计 算 机 应 用 研 究 Ｖｏｌ３３Ｎｏ１２ ２０１６年１２月　 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ｄｅｃ．２０１６ 基于节点拓扑结构和属性的重叠社区检测算法 许加书，韩忠愿，顾惠健 （南京财经大学信息工程学院，南京２１００４６） 摘　要：针对已有重叠社区检测通常只考虑节点的拓扑结构信息，忽略了节点的属性信息，导致数据间的重要 结构遗漏的问题，提出了一种基于节点拓扑结构和属性相似度的重叠社区检测算法。首先，基于余弦相似度计 算候选节点和局部社区之间的相似度，提高局部有哪些信誉好的足球投注网站效率；其次，改进局部模块度增量计算方法，使局部有哪些信誉好的足球投注网站模 型收敛于发现潜在的真实社区；通过融合多个已检测到的局部社区计算隶属矩阵，从而获取全局重叠社区结构； 最后，在真实数据集上，与已有基于拓扑结构的社区检测算法进行实验对比。结论表明，该算法在模块度和Ｆ １ ｍｅａｓｕｒｅ的指标上取得了较好的表现且更适用于稀疏网络。 关键词：社区检测；节点属性；重叠社区；隶属矩阵；模块度 中图分类号：ＴＰ３０１．６　　 文献标志码：Ａ　　 文章编号：１００１３６９５（２０１６）１２３６１５０５ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１６．１２．０２２ Ｏｖｅｒｌａｐｐｉｎｇｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎｗｉｔｈｎｏｄｅｓｔｒｕｃｔｕｒｅａｎｄａｔｔｒｉｂｕｔｅ ＸｕＪｉａｓｈｕ，ＨａｎＺｈｏｎｇｙｕａｎ，ＧｕＨｕｉｊｉａｎ （ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎ＆Ｅｎｇｉｎｅｅｒｉｎｇ，ＮａｎｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＦｉｎａｎｃｅ＆Ｅｃｏｎｏｍｉｃｓ，Ｎａｎｊｉｎｇ２１００４６，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｆｏｒｏｖｅｒｌａｐｐｉｎｇｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎｕｓｕａｌｌｙｏｎｌｙｃｏｎｓｉｄｅｒｉｎｇｔｈｅｔｏｐｏｌｏｇｙｉｎｆｏｒｍａｔｉｏｎｏｆｎｏｄｅｓ，ｉｇｎｏｒｉｎｇｔｈｅｎｏｄｅ ａｔｔｒｉｂｕｔｅｉｎｆｏｒｍａｔｉｏｎ，ｃａｕｓｉｎｇｔｈｅｐｒｏｂｌｅｍｏｆｍｉｓｓｉｎｇｉｍｐｏｒｔａｎｔｄａｔａｓｔｒｕｃｔｕｒｅｓ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄａｎｏｖｅｒｌａｐｐｉｎｇｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍ．Ｔｈｅａｌｇｏｒｉｔｈｍｗａｓｂａｓｅｄｏｎｔｈｅｔｏｐｏｌｏｇｙａｎｄｔｈｅｓｉｍｉｌａｒｉｔｙｏｆｎｏｄｅａｔｔｒｉｂｕｔｅｔｏｆｉｎｄｏｖｅｒｌａｐｐｉｎｇｃｏｍｍｕｎｉ ｔｉｅｓｆｒｏｍａｓｅｅｄｖｅｒｔｅｘ．Ｆｉｒｓｔ，ｉｔｃｏｍｐｕｔｅｄｔｈｅｓｉｍｉｌａｒｉｔｙｂｅｔｗｅｅｎｃａｎｄｉｄａｔｅｎｏｄｅｓａｎｄｔｈｅｌｏｃａｌｃｏｍｍｕｎｉｔｙｂａｓｅｄｏｎｃｏｓｉｎｅ ｓｉｍｉｌａｒｉｔｙ，ｉｍｐｒｏｖｅｄｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｌｏｃａｌｓｅａｒｃｈｉｎｇ．Ｓｅｃｏｎｄ，ｉｔｉｍｐｒｏｖｅｄｔｈｅｃａｌｃｕｌａｔｉｏｎｍｅｔｈｏｄｏｆｌｏｃａｌｍｏｄｕｌｅｄｅｇｒｅｅｉｎ ｃｒｅｍｅｎｔｓ，ｍａｄｅｔｈｅｌｏｃａｌｓｅａｒｃｈｍｏｄｅｌｃｏｎｖｅｒｇｅｔｏｆｉｎｄｐｏｔｅｎｔｉａｌｇｒｏｕｎｄｔｒｕｔｈｃｏｍｍｕｎｉｔｉｅｓ．Ｔｈｉｒｄ，ｉｔｍｅｒｇｅｄｍｕｌｔｉｐｌｅｌｏｃａｌ ｃｏｍｍｕｎｉｔｉｅｓｗｈｉｃｈｈａｖｅｂｅｅｎｄｅｔｅｃｔｅｄａｎｄｃａｌｃｕｌａｔｅａｍｅｍｂｅｒｓｈｉｐｍａｔｒｉｘ，ｗｈｉｃｈｃａｎｂｅｓｅｅｎａｓｔｈｅｇｌｏｂａｌｏｖｅｒｌａｐｐｉｎｇｃｏｍ ｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｏｆａｇｒａｐｈ．Ａｔｔｈｅｅｎｄ，ｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｅｘｉｓｔｉｎｇｃｏｍｍ