Tsung Chen-Kun, Ho Hann-Jang, Chen Chien-Yu, Chang Tien-Wei, Lee Sing-Ling
Department of Computer Science and Information Engineering, National Chin-Yi University of Technology, Taichung 41170, Taiwan.
Department of Applied Digital Media, WuFeng University, Chiayi County 62153, Taiwan.
Entropy (Basel). 2020 Jul 27;22(8):819. doi: 10.3390/e22080819.
On the purpose of detecting communities, many algorithms have been proposed for the disjointed community sets. The major challenge of detecting communities from the real-world problems is to determine the overlapped communities. The overlapped vertices belong to some communities, so it is difficult to be detected using the modularity maximization approach. The major problem is that the overlapping structure barely be found by maximizing the fuzzy modularity function. In this paper, we firstly introduce a node weight allocation problem to formulate the overlapping property in the community detection. We propose an extension of modularity, which is a better measure for overlapping communities based on reweighting nodes, to design the proposed algorithm. We use the genetic algorithm for solving the node weight allocation problem and detecting the overlapping communities. To fit the properties of various instances, we introduce three refinement strategies to increase the solution quality. In the experiments, the proposed method is applied on both synthetic and real networks, and the results show that the proposed solution can detect the nontrivial valuable overlapping nodes which might be ignored by other algorithms.
为了检测社区，已经提出了许多用于不相交社区集的算法。从现实世界问题中检测社区的主要挑战是确定重叠社区。重叠顶点属于某些社区，因此使用模块化最大化方法很难检测到。主要问题是通过最大化模糊模块化函数几乎找不到重叠结构。在本文中，我们首先引入一个节点权重分配问题来描述社区检测中的重叠属性。我们提出了模块化的扩展，这是一种基于重新加权节点对重叠社区更好的度量，以设计所提出的算法。我们使用遗传算法来解决节点权重分配问题并检测重叠社区。为了适应各种实例的特性，我们引入了三种细化策略来提高解决方案的质量。在实验中，将所提出的方法应用于合成网络和真实网络，结果表明所提出的解决方案可以检测到其他算法可能忽略的有价值的非平凡重叠节点。
