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

发布时间：2021-08-14 15:08

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

【文章来源】：计算机科学. 2020,47(10)北大核心CSCD

【文章页数】：8 页

【部分图文】：

OCDRDD算法在Dolphins数据集上的划分结果(电子版为彩色)

距离动态模型的主要思想是:网络中节点间的距离是逐渐变化的,随着时间的推移,距离会存在两种变化方式,属于同一个社区的节点间距离会逐渐变小,属于不同社区间的节点间距离会逐渐变大,最终达到一个稳定的状态,使得社区结构呈现出来。距离动态模型是通过检测节点间距离的变化动态地发现社区结构,如图1(a)所示,节点vi和节点vj间距离d(vi,vj)的变化会受到3种不同邻居节点的影响,如图1中(b)-(d)所示,从而引出3种交互模式。交互模式1:来自直接链接节点的影响。直接链接节点是指直接相连的两个端节点vi和vj之间的影响。两个端节点之间会彼此吸引,使得距离d(vi,vj)减小,如图1(b)所示。直接链接节点的影响DI定义为:

对边界域节点进行迭代处理后,此时识别出来的重叠节点有部分是非重叠节点。产生这种现象的原因是这类节点离所有的核心节点较远,且不满足比值关系。我们称这类节点为“伪”重叠节点。“伪”重叠节点存在两种情况:1)只有一个邻居节点的叶子节点;2)该节点有多个邻居节点,且该节点只有一个邻居节点属于一个社区,大于或等于2个邻居节点属于另外一个社区。具体如图2所示。我们对这类节点的处理分两种情况,分别如图2(a)和图2(b)所示。为此,本文提出了两条对“伪”重叠节点进行处理的规则。规则1 当“伪”重叠节点为只有一个邻居节点的叶子节点时,该类节点被划分到其邻居节点所属的社区中。如图2(a)所示,节点{a,b,c}为社区C,节点{d}为“伪”重叠节点,此时应该将节点{d}划分到社区C。

【参考文献】：
期刊论文
[1]一种新的基于粗糙集K-均值的社区发现方法[J]. 张云雷,吴斌,刘宇.  电子与信息学报. 2017(04)
[2]基于链接密度聚类的重叠社区发现算法[J]. 朱牧,孟凡荣,周勇.  计算机研究与发展. 2013(12)



本文编号：3342691