关键词: 社区发现方法, 多准则约束, 相对密度, 剪枝, 局部搜索

Abstract: Finding communities on social networks has been studied extensively in recent years. Most existing discovery methods focus on optimization of some objective functions of the communities, for example, edge density. In some cases, taking multiple features into account is needed. For instance, people hope to discover those tightly-knitted and large communities in some certain shapes. Only applying one existing method cannot meet such requirement. Since the communities discovered in different existing ways may have arbitrary sharp, the results are difficult to be merged. This paper proposes a relative density based on community definition and a multi-constraint model based on multi-property dominance. By analyzing the constraints between the size of members and friendship closeness, it designs an efficient algorithm and the pruning strategies. The experimental results on a large real date set show the algorithm is effective and efficient.

Key words: community identification, multi-constraint, relative density, pruning, local search