一种新型的层次化动态社区并行计算方法  

Hierarchical Dynamic Community Detection by Parallel Computing

作　　者：林旺群[1] 邓镭[1] 丁兆云[1] 吴泉源[1] 贾焰[1] 周斌[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073

出　　处：《计算机学报》2012年第8期1712-1725,共14页Chinese Journal of Computers

基　　金：国家自然科学基金(60933005;60873204);国家"八六三"高技术研究发展计划项目基金(2010AA012505)资助~~

摘　　要：文中提出了一种可并行分解的层次化动态社区发现算法D-SNCD(Dynamic Social Network CommunityDiscovery).D-SNCD算法充分利用复杂动态社会网络变化的局部性,对算法生成的层次化社区树HOT(Hierar-chical cOmmunity Tree)的分枝进行选择性更新.与传统的对动态社会网络直接采用快照方式进行社区发现相比,D-SNCD算法在效率上取得了明显的提高.由于D-SNCD是对已有的静态社区并行计算方法P-SNCD(ParallelSocial Network Community Discovery)的进一步扩展,因而D-SNCD保持着P-SNCD算法的高扩展性和高分辨率等优点.另外,D-SNCD算法对用户参数输入要求简单.严格的数学证明和充分的实验数据保证了整个算法的正确性和有效性.We propose a parallel computing approach, namely Dynamic Social Network Community Discovery （D-SNCD）, for detecting hierarchical community structures in dynamic social networks. Usually, in most of the dynamic social networks, the network structures change and evolve partially and dynamically in a unit time. By making use of this characteristic of the dynamic social network, D-SNCD updates the Hierarchical cOmmunity Tree （HOT） in a timely and choicely way. Compared to the existing community detection algorithms, which take advantage of the snapshots of the social network directly, the efficiency of D-SNCD is greatly improved. Since D-SNCD is an improved version of Parallel Social Network Community Discovery （P-SNCD）, D-SNCD have the advantages of highly scalability and resolution. Moreover, the inputs of D-SNCD is simple and easy to control for users. The strictly mathematical proofs and experimental results further guarantee the correctness and effectiveness of our proposed algorithm.

关 键 词：社区发现 层次化社区结构 动态社会网络 并行计算 动态更新 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]