DFCD：基于密度的模糊社区检测方法，结合偏置随机游走引导的节点采样

《IEEE Computational Intelligence Magazine》：DFCD: Density-Based Fuzzy Community Detection Approach With Biased Random Walk Guided Node Sampling

针对复杂网络重叠社区检测中长距离节点距离计算不足及重叠隶属度计算困难的问题，提出密度基模糊社区检测方法（DFCD），通过偏置随机游走来捕获网络拓扑，利用节点流确定全局邻居并计算局部密度，构建三种节点-社区关系，设计新型隶属度计算函数，实验表明该方法在准确性和时间复杂度上优于现有方法。

　　

摘要：

由于不同类型复杂网络的快速增长，对重叠社区检测的研究仍然具有重要意义。在社区检测的各种方法中，基于密度的聚类方法在重叠社区检测领域并未受到太多关注。我们发现了基于密度方法的两个主要缺点：1）缺乏计算图数据集中节点之间适当长距离（可达多个跳数）的研究；2）在节点分布多样且形状不规则的图数据集中，难以计算节点的重叠归属系数，因为在这种情况下只有少数节点之间的距离是已知的（甚至节点的位置也不清楚）。在本文中，我们提出了一种新的重叠社区检测方法，称之为“基于密度的模糊社区检测（DFCD）”，该方法基于节点的局部密度。通过使用有偏随机游走，我们将网络拓扑结构以“节点流”的形式捕获。我们提出了一种新的计算节点间长距离的方法，利用节点流为每个节点找到固定数量的全局邻居，从而计算出节点的局部密度。我们提出了三种节点与社区之间的关系，这些关系仅依赖于节点的局部密度和节点间的距离。最后，我们基于这三种关系和局部密度、节点间距离，提出了一种新的归属计算函数。通过对比多个真实生活和合成数据集，以及十种最先进的竞争方法，证明了我们提出方法的优越性。实验分析表明，该方法在准确性和质量评估方面均优于其他方法。此外，对所提方法的详细复杂性分析显示，其时间复杂度随节点数量和平均度的增加而线性增长，这低于大多数重叠社区检测方法的复杂度。

显示更多

引言

在现代科技时代，复杂网络是表示不同类型对象之间多样化关系的常用工具。因此，从这些复杂的网络中提取有用信息已成为一个重要的研究领域[1]。社区检测是从复杂网络中提取信息的最具挑战性和最重要的方面之一。尽管目前还没有被广泛接受的社区定义，但一般来说，社区是指节点之间连接紧密的子图。最初，人们认为社区是不相交的[2]。然而，现代研究指出，在复杂网络（尤其是社交网络）中，检测重叠社区更为重要，因为一个节点可能同时属于多个社区[3]。