基于粗糙集和距离动态模型的重叠社区发现方法

摘要

现实世界可被看作由许多不同的复杂系统组成.为了建模分析复杂系统中个体间隐藏的规律及功能,将复杂系统抽象为由节点和边组成的复杂网络.挖掘复杂网络中的社区结构在内容推荐、行为预测和疾病扩散等方面具有重要的理论意义和实际价值.随着复杂系统内个体的不断变化,多个社区间出现了重叠节点,有效且准确地挖掘社区中的重叠节点具有一定的挑战性.为了有效发现社区中的重叠节点,提出了一种基于粗糙集和距离动态模型的重叠社区发现方法(Overlapping Commu-nity Detection based on Rough sets and Distance Dynamics model,OCDRDD).该方法首先根据网络的拓扑结构,结合节点度中心性和距离选出K个核心节点;然后按照定义的距离比率关系初始化社区的近似集和边界域,结合距离动态模型,迭代变化边界域节点与下近似集节点间相连的边的距离,且在每次迭代过程中将符合定义的距离比率关系的边界域节点划分到社区下近似集中,以缩小边界域节点(即缩小边界域的范围),直到找到最佳重叠社区结构;最后根据定义的两条规则处理"伪"重叠节点.在真实网络数据集和LFR Benchmark人工网络数据集上,以NMI和具有重叠性的模块度EQ作为评价指标,将OCDRDD方法与近几年具有代表性的社区发现方法进行实验测试比较,发现OCDRDD方法整体优于其他算法,结果表明该算法具有有效性和可行性.