Abstract: Overlapping community discovery algorithm based on local expansion can effectively discover overlapping communities. However, the random strategy of algorithm will cause problems such as strong randomness and poor accuracy. Therefore, a local extended class overlapping community discovery algorithm based on K-kernel iteration factor and community membership degree（KIMDOC） is proposed. KIMDOC improves K-kernel decomposition algorithm, derives K-kernel iteration factor, combines with node density, quantifies the influence of nodes, finds out the nodes with the greatest influence, improves the stability and accuracy of seed node selection. These nodes are taken as seed nodes, the membership degree of adjacent nodes are obtained. Adjacent nodes are added according to membership degree for community expansion, which improves the quality of community discovery. The algorithm is tested over benchmark networks and real-world networks. The results verify KIMDOC has high stability and accuracy.

Key words: overlapping communities, complex network, K-kernel iteration factor, node influence, community membership degree

摘要： 基于局部扩展的重叠社区发现算法，利用社区的局部扩展特性可有效扩展出重叠社区，但是现有算法存在划分结果不稳定和准确性较低等问题，因此提出了一种基于[K]-核迭代因子和社区隶属度的重叠社区发现算法。该算法引用[K]-核迭代因子的思想，并且与节点密度值相结合，量化节点的影响力，找出节点影响力最大的节点，提高种子节点选择的稳定性和准确性；同时以影响力大的节点为种子节点，通过节点影响力计算得到邻接节点的社区隶属度，根据社区隶属度选择性地添加邻接节点进行社区扩展，提高社区发现的质量。在人工网络图和真实数据集上进行实验，结果表明所提的算法与现有的算法比较具有较高的稳定性和准确性。

关键词: 重叠社区, 复杂网络, [K]-核迭代因子, 节点影响力, 社区隶属度