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

摘要： 社会网络上的社区发现技术是近年来的研究热点之一, 通常的社区发现方法往往立足于最优化社区的某个特征, 从而达到识别社区的目的, 例如最优化节点群的链接密度。在实际需求中, 人们往往期待能够识别满足多种特征约束的社区, 例如既连接紧密又在满足某种形状约束的条件下, 规模越大越好。在某些情况下, 单一条件约束的社区发现方法通常无法满足用户对于多准则的要求, 而由于网络社区形式的任意性, 不同发现方法的结果又难以合并。针对这一需求, 给出了一种社区发现的多准则约束模型, 以及能够同时满足结构约束、社区规模要求和紧密度要求的典型社区多准则约束规则; 提出了一种高效的算法和剪枝策略, 并在一个大规模的真实数据集上验证了该算法的有效性和高效率。

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