We use cookies to improve your experience with our site.
石川, 闫震宇, 潘欣, 蔡亚男, 吴斌. 一种基于事后决策的社团发现算法[J]. 计算机科学技术学报, 2011, 26(5): 792-805. DOI: 10.1007/s11390-011-0178-z
引用本文: 石川, 闫震宇, 潘欣, 蔡亚男, 吴斌. 一种基于事后决策的社团发现算法[J]. 计算机科学技术学报, 2011, 26(5): 792-805. DOI: 10.1007/s11390-011-0178-z
Chuan Shi, Zhen-Yu Yan, Xin Pan, Ya-Nan Cai, Bin Wu. A Posteriori Approach for Community Detection[J]. Journal of Computer Science and Technology, 2011, 26(5): 792-805. DOI: 10.1007/s11390-011-0178-z
Citation: Chuan Shi, Zhen-Yu Yan, Xin Pan, Ya-Nan Cai, Bin Wu. A Posteriori Approach for Community Detection[J]. Journal of Computer Science and Technology, 2011, 26(5): 792-805. DOI: 10.1007/s11390-011-0178-z

一种基于事后决策的社团发现算法

A Posteriori Approach for Community Detection

  • 摘要: 1.本文的创新点
    复杂网络在现实世界中无处不在。例如,人际交往构成的社会网络,网页互联构成的WWW网络。近些年复杂网络分析吸引了很多领域的学者的广泛关注。复杂网络分析中的一个重要问题是社团发现。大量研究发现社团结构揭示了网络功能,因此社团发现是研究网络的功能和结构的重要手段。当前的社团发现方法往往是基于先验决策的优化。即根据先验知识定义一个描述社团结构的评价函数,然后优化这个函数得到社团结构。虽然基于先验决策的社团发现算法广泛应用于理论分析和实际应用,但是这类方法存在一些不足:优化单个评价函数往往会将社团划分偏向于特定的结构;很多方法需要事先知道社团个数;这些方法只得到一个社团划分结果,这样无法揭示复杂的网络结构,例如重叠和层次结构。
    本文提出了基于事后决策的社团发现算法。即首先同时优化多个评价函数,得到一组最优解。然后决策者根据领域知识和实际需要选择最合适的解。由于实际网络的复杂性和社团结构的主观性,社团结构很难用一个评价函数准确定义。因此本文提出用多个评价函数从不同角度描述社团结构,这样得到的社团结构更加全面均衡。本文利用进化多目标优化方法同时优化多个评价函数。精巧的基因表示方法能够在进化过程中自动确定社团个数。本文提出的算法能够一次运行返回一组最优解,这些解有不同的目标偏好,这样能够从不同层次和角度发现复杂的社团结构。 2.实现方法
    本文提出了进化多目标社团发现算法(简称MOCD)。该算法包含两个阶段:社团发现和模型选择。在社团发现阶段,我们设计了进化多目标优化算法同时优化多个评价函数,并返回一组最优解。NSGA-II 作为 MOCD的多目标优化机制;模块度Q的两部分作为优化目标;局部链接方法作为基因表示;并设计了相应的杂交变异算子。为了帮助决策者从最优解集中选择合适的社团划分,模型选择阶段提出了三个评价标准和一个概率矩阵方法。本文用五个人工和实际网络验证了MOCD的有效性。层次和重叠网络实验表明MOCD能够有效地发现复杂社团结构。已知结构的随机网络实验表明MOCD相比现有算法能够更加准确的划分社团。两个实际网络实验进一步证实了MOCD不仅发现了独立紧密的社团结构,还揭露了有价值的隐含的社团信息。 3.结论及未来待解决的问题
    针对目前广泛使用的基于先验信息的社团发现方法,本文提出了基于后验信息的社团发现方法。实验证明该方法能够发现更加准确的复杂的网络结构。未来研究包括:设计更加有效的目标函数和的社团选择方法。

     

    Abstract: Conventional community detection approaches in complex network are based on the optimization of a priori decision, i.e., a single quality function designed beforehand. This paper proposes a posteriori decision approach for community detection. The approach includes two phases: in the search phase, a special multi-objective evolutionary algorithm is designed to search for a set of tradeoff partitions that reveal the community structure at different scales in one run; in the decision phase, three model selection criteria and the Possibility Matrix method are proposed to aid decision makers to select the preferable solutions through differentiating the set of optimal solutions according to their qualities. The experiments in five synthetic and real social networks illustrate that, in one run, our method is able to obtain many candidate solutions, which effectively avoids the resolution limit existing in priori decision approaches. In addition, our method can discover more authentic and comprehensive community structures than those priori decision approaches.

     

/

返回文章
返回