基于无偏Q值反馈的社区划分算法
2011-08-16曹玖新时莉莉
东南大学学报(自然科学版) 2011年1期
关键词：信息
杨 柳 曹玖新 刘 波 时莉莉
(东南大学计算机科学与工程学院，南京 210096)
目前，随着数字网络化社会的发展，人类的通信需求急剧增加.处于社会中的个体为了更好地进行信息交流，往往会根据需要，通过自己的通信关系建立起不同的关系网络，这样形成的网络被称为社会网络.网络中的节点通常是个人或者组织，通过各种社会关系(如价值观、理想、友谊、血缘关系、冲突、贸易)把个人或组织串联起来.
社会网络分析法从多个角度对社会网络进行分析，包括中心度分析、社区划分、核心-边缘结构分析及结构对等分析等.目前，在对社会网络的研究中，社区结构已成为社会网络最普遍和最重要的拓扑结构属性之一，相应的社区划分(也称作网络聚类)算法研究也成为当前的热点问题.社区划分算法的研究不仅具有十分重要的理论意义，而且具有广泛的应用前景.
本文在分析现有社区发现算法的基础上，提出了一种基于无偏Q值反馈的社区发现算法.该算法首先采用随机游走策略，快速确定最优社区数，实现Q值无偏，并提出利用传递权值计算节点相似度的方法以及Q值反馈的思想，使得算法可以准确快速收敛到最优解.实验结果表明，该算法在社区划分方面与现有算法相比具有更高的准确率，能够达到社区划分以及核心节点发现的目的.社区划分算法也可应用到基于社区的移动社会模型建立以及路由转化机制中.