Abstract: The research shows that many real networks have hierarchical structure and overlapping structure. Traditional hierarchical clustering algorithms usually use the node as the object to expand and form the hierarchical tree graph to get the network hierarchy. This approach has two problems, one is the stability of the algorithm, mainly reflect in the selection of initial node, different initial nodes will lead to the final results of different algorithms in a few cases, even if the algorithm does not depend on the initial node, but the complexity of the algorithm will change, second is unable to find overlapping structure. To solve the above two problems, this paper proposes a hierarchical overlapping community detection algorithm based on maximum clique. The algorithm uses maximal cliques as the extended object and adopt maximal clique expansion strategy to generate the hierarchical tree diagram. Finally, the overlapping modularity function is used to prune the hierarchical tree and get the result of community division. The experimental results on real network and LFR artificial neural network show that the proposed algorithm can effectively mine the hierarchical structure and overlapping structure.

Key words: hierarchical structure, overlapping structure, maximum clique, community detection

摘要： 研究表明，很多真实网络具有层次结构和重叠结构。传统的层次聚类算法通常以节点为对象进行扩展形成层次树图从而得到网络的层次结构。这种做法存在两个问题，其一是算法的稳定性，主要体现在初始节点的选择上，少数情况下，初始节点的不同会导致算法最终结果的不同，即使算法的结果不依赖于初始节点，但算法的复杂度会随之变化；其二是不能发现网络中的重叠结构。针对以上问题，提出一种基于最大团的层次化重叠社区发现算法。该算法以最大团为扩展对象，然后利用最大团扩展策略生成层次树图，最后采用重叠模块度函数对层次树图进行剪枝得到社区划分结果。在真实网络以及LFR人工网络上的实验结果表明该算法能够有效地挖掘网络中的层次结构和重叠结构。

关键词: 层次结构, 重叠结构, 最大团, 社区发现