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

Overlapping Community Detection Method Based on Rough Sets and Distance Dynamic Model

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

The real world is considered to be composed of many different complex systems.In order to model and analyze the hidden rules and functions among individuals in complex systems,the complex system may be abstracted as a complex network composed of nodes and edges.Mining community structures in complex networks has important theoretical significance and practical value in content recommendation,behavior prediction and disease spread.With the continuous changes of individuals in complex systems,overlapping nodes appear among multiple communities.How to effectively and accurately mine the overlapping nodes in communities has brought some challenges.In order to effectively detect the overlapping nodes in the community,an overlapping community detection method based on rough sets and distance dynamic model(OCDRDD) is proposed in this paper.First of all,according to the topology of the network,it selects K core nodes by combining node degree centrality and distance,then initializes the approximation sets and the boundary region of the community according to the distance ratio relationship.Combined with the distance dynamic model,the distances between boundary region nodes and the lower approximation set nodes are changed iteratively.During each iteration,boundary region nodes that conform to the defined distance ratio relationship are classified into the lower approximation of the community,and the boundary region nodes are reduced until the optimal overlapping community structure is found.Finally,the "pseudo" overlapping nodes are processed according to the two rules defined in this paper.NMI and overlapping module degree EQ are taken as evaluation indexes on real network datasets and LFR Benchmark artificial network datasets.The OCDRDD method is compared with other typical community detection methods in recent years both on real network datasets and LFR Benchmark artificial network datasets.The experimental results show that OCDRDD method is better than other community detection algorithms on the whole.The results show that the proposed algorithm is effective and feasible.