基于社团密度的社团发现算法  

Community detection algorithm based on community density

作　　者：王玉英[1] 何汶坤 史加荣[1] 

机构地区：[1]西安建筑科技大学理学院,西安710055 [2]西安建筑科技大学信息与控制工程学院,西安710055

出　　处：《计算机应用研究》2017年第7期1975-1979,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61403298)

摘　　要：发现社团结构是研究复杂网络的重要前提,目前社团发现算法研究存在两个较为严峻的问题:评价函数单一和经典算法时间复杂度过大并且无法发现小粒度的社团。针对上述问题,提出了一种合理的发现算法评价函数,即社团完整度F。实验证明,与经典的模块度函数Q相比,社团完整度函数F能够更合理地评价社团划分质量且社团完整度函数F的灵敏度高于模块度函数Q;提出了基于社团密度的社团发现算法(BDA算法)。实验证明,该算法不仅可以发现小粒度的社团结构,随着网络节点数和边数的增加,BDA算法在时间复杂度方面也具有明显的优势。尝试将BDA算法应用在科学合作者网络并得到了合理的社团结构。It is important for researching of complex networks to finding the community structure, the lack of evaluation function and defective algorithms which can’t find small community structure and have bad time complexity are two serious problem. Regarding the issues above, this paper presented a new evaluation function F based on the concept of community integrity firstly, the results show that evaluation function F can evaluate the detection quality of community reasonably and the sensitivity of evaluation function F is better than modularity Q. Then this paper presented a new non overlapping community detection algorithm based on community density （BDA）, the results show that BDA algorithm can find the reasonable community structure of small particle size, and new algorithm is better than FN algorithm in the aspect of time complexity with the increase of number of node and edge. Finally, it applied BDA and EOA in the scientific partner network and got better community structure.

关 键 词：社团结构 社团发现 社团完整度 社团密度 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]