[1]杨柳,曹玖新,刘波,等.基于无偏Q值反馈的社区划分算法[J].东南大学学报(自然科学版),2011,41(1):31-36.[doi:10.3969/j.issn.1001-0505.2011.01.007]
 Yang Liu,Cao Jiuxin,Liu Bo,et al.Community division algorithm based on feedback of unbiased Q value[J].Journal of Southeast University (Natural Science Edition),2011,41(1):31-36.[doi:10.3969/j.issn.1001-0505.2011.01.007]
点击复制

基于无偏Q值反馈的社区划分算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
41
期数:
2011年第1期
页码:
31-36
栏目:
计算机科学与工程
出版日期:
2011-01-20

文章信息/Info

Title:
Community division algorithm based on feedback of unbiased Q value
作者:
杨柳曹玖新刘波时莉莉
(东南大学计算机科学与工程学院,南京 210096)
Author(s):
Yang LiuCao JiuxinLiu BoShi Lili
(School of Computer Science and Engineering, Southeast University, Nanjing 210096, China)
关键词:
社区划分无偏Q传递权值反馈
Keywords:
community division unbiased Q value transitive weights feedback
分类号:
TP393
DOI:
10.3969/j.issn.1001-0505.2011.01.007
摘要:
在分析现有社区划分算法的基础上,针对当前算法Q值有偏及权值未体现等缺陷,提出了一种基于无偏Q值反馈的社区划分算法. 该算法首先利用传递权值计算出节点间的相似度; 然后,采用随机游走策略确定最优社区数,以解决现有划分算法中Q值有偏的问题; 最后,在最优社区数确定的情况下,利用划分结果评价Q值反馈更新信息素矩阵以驱动后续的划分,从而达到快速收敛的目的.针对计算机构造的数据集以及实际网络的实验分析结果表明,与现有算法相比,该算法在社区划分方面具有更高的准确率及更快的收敛速度,能够达到社区划分以及核心节点发现的目的, 可被推广应用至移动社会网络模型的建立中.
Abstract:
Based on the analysis of the existing community division algorithms, a community division algorithm based on the feedback of unbiased Q value is proposed to avoid the bias of Q value and the ignorance of link weight ignored. Firstly, the similarity of nodes is calculated through the transitive weights. Then, the optimal community number is determined by means of random walk strategy in order to make the Q value unbiased. Finally, with the optimal community number determined, the pheromone matrix is updated by using the feedback of the Q value to drive up the follow-up division, which makes the algorithm converge to the optimal solution quickly and accurately. The experimental analysis results of data set constructed by computer analysis and the actual network show that this algorithm has higher accuracy and faster constringency than the existing community division algorithms in respect of community division and core node detection. It can be used to construct the social mobile network.

参考文献/References:

[1] Newman M E J.Detecting community structure in networks [J].European Physical Journal,2004,38(2):321-330.
[2] Girvan M,Newman M E J.Community structure in social and biological networks [J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[3] Newman M E J.Fast algorithm for detecting community structure in networks [J].Physical Review E,2004,69(6):066133.
[4] Pujol J M,Béjar J,Delgado J.Clustering algorithm for determining community structure in large networks [J].Physical Review E,2006,74(1):016107.
[5] Duch J,Arenas A.Community detection in complex networks using extreme optimization [J].Physical Review E,2005,72(2):027104.
[6] Guimera R,Sales M,Amaral L A N.Modularity from fluctuations in random graphs and complex networks [J].Physical Review E,2004,70(2):025101.
[7] 徐晓华.图上的随机游走学习[D].南京航空航天大学计算机学院,2008.
[8] Meila M,Xu L.Multiway cuts and spectral clustering [R].Washington DC,USA:Dept of Statistics of University of Washington,2003.
[9] 邹远强.蚁群聚类算法及其在电信客户分群中的应用[D].长沙:湖南大学计算机学院,2007.
[10] McCanne S,Floyd S.The NS2 network simulator[EB/OL].(2006-04-28)[2009-02-01].http://www.isi.edu/nsnam/ns/.
[11] Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977(3):3452-3473.
[12] Daly E M,Haahr M.Social network analysis for routing in disconnected delay-tolerant MANETs [C]//Proc of the 8th ACM Symp on Mobile Ad Hoc Networking and Computing.Montreal,Canada,2007:32-40.

备注/Memo

备注/Memo:
作者简介:杨柳(1987—),男,硕士生;曹玖新(联系人),男,博士,副教授,jx.cao@seu.edu.cn.
基金项目:国家自然科学基金资助项目(60903161,61003257,61060161,61070158)、国家重点基础研究发展计划(973计划)资助项目(2009CB320501,2010CB328104)、江苏省网络与信息安全重点实验室课题基金资助项目(BM2003201)、教育部网络与信息集成重点实验室课题基金资助项目(93K).
引文格式: 杨柳,曹玖新,刘波,等.基于无偏Q值反馈的社区划分算法[J].东南大学学报:自然科学版,2011,41(1):31-36.[doi:10.3969/j.issn.1001-0505.2011.01.007]
更新日期/Last Update: 2011-01-20