邻域粗糙化的启发式重叠社区扩张方法  

Detecting Overlapping Communities with Heuristic Expansion Method Based on Rough Neighborhood

作　　者：张泽华[1,2,3] 苗夺谦[1,2] 钱进 

机构地区：[1]同济大学计算机科学与技术系,上海201804 [2]同济大学嵌入式系统与服务计算教育部重点实验室,上海200092 [3]太原理工大学计算机科学与技术学院,太原030024

出　　处：《计算机学报》2013年第10期2078-2086,共9页Chinese Journal of Computers

基　　金：国家自然科学基金(61273304;61202170;61103067;61075056);教育部博士点优先资助项目;中央高校基本科研业务费专项资金资助~~

摘　　要：重叠社区发现研究是当前图挖掘领域的前沿热点.基于结构适应度的局部扩张方法是其中一类可同时探测社区重叠和层次结构的方法.该文首先提出了基于邻域粗糙化的社区局部扩张方法,然后给出了一种反映社区内在结构特征的稳定性度量.针对局部扩张方法计算冗余和社区漂移等不足,采用一种新的种子社区启发策略来降低复杂计算和提高探测能力.在结构适应度最大化的条件下,以极大度节点的团作为种子社区进行局部扩张,通过社区稳定度度量对近邻重复社区进行合并,生成自然重叠的社区.在真实网络上的实验结果表明邻域粗糙化的方法可以有效地发现重叠社区,并具有很好的扩展性.Detecting overlapping communities is a hot topic of graph mining research in recent years. The local expansion methods based on structural fitness function are one kind of over-lapped community,s detection methods, which could simultaneously discover overlapped and hier-archical structures. The paper presents the local expansion method based on rough neighborhood and introduces a kind of stability measure reflecting the inherent structural features of communities. Aimed at community drift and redundant calculation problems of general local expansion methods, a novel heuristic strategy about community seeds is adopted to reduce the computational complexity and improve the detection capability in local expansion process. On the condition of the structural fitness maximization, the cliques with the nodes of great degree are expanded as local seed communities. Then the proposed local expansion method merges the adjacent duplicate communities by community＇ s stability measure and finally generates the natural overlapping communities. In the end, the experimental results on some real networks show that the rough neighborhood-based method could be more effective in detecting overlapping structures, while the algorithm has good scalability on a large scale data.

关 键 词：粗糙集理论 邻域粗糙化 社区发现 重叠社区 局部扩展 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]