一种基于图压缩的重叠社区发现算法  

A Graph Compression Based Overlapping Communities Detection Algorithm

作　　者：赵宇海[1] 印莹[1] 王雪[1] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110819

出　　处：《东北大学学报（自然科学版）》2015年第11期1543-1547,共5页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(61272182);国家自然科学基金重点资助项目(61332014);中央高校基本科研业务费专项资金资助项目(N130504001)

摘　　要：为提高单机处理复杂网络规模的能力,提出一种新的重叠社区发现算法.首先,通过基于图压缩的社区结构表示模型(压缩社区图),对网络进行无损压缩;然后,在压缩社区图上基于种子迭代的思想,通过不断优化社区适应度函数将种子扩展成社区;最后,将相似度高的社区进行合并,得到最终的重叠社区结果.由于压缩后的凝聚图大大降低了待处理的网络规模,并能在一定程度上减少重复计算,该方法可以大大提高计算效率和单机处理的网络规模.To improve the capacity of single machine to handle complex network,overlapping communities detection algorithm was proposed. First,a graph compression based social network model,namely agglomerative graph,was introduced,which was a lossless compression to the original network. Then,inspired by the idea of iteration based on seeds,the selected seeds were expanded to the communities by optimizing the proposed community fitness function iteratively.Finally,the communities of high similarity with each other were merged to get the final results.Since the scale of the network to be dealt is significantly reduced, and some redundant computations are avoided,the proposed algorithm is of high efficiency.

关 键 词：重叠社区 社会网络 数据挖掘 聚类 图压缩 

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