一种基于邻居信息的最大派系过滤算法

摘要：

最大派系问题(Maximal Clique Problem,MCP)是组合优化中经典而重要的问题之一,在信息抽取、信号传输、计算机视觉、社会网络及生物信息学等众多领域有着重要的应用.学者们根据不同的思想策略,提出了许多方法求解最大派系问题,如分支定界、遗传算法、模拟退火、交叉熵及DNA方法等.现根据派系的邻居信息提出一种基于派系邻接顶点和邻接边的派系过滤算法.算法从一个已知派系(初始为一个单独顶点)出发,每次考察派系的邻接顶点,并以派系的邻接边为基础,扩展已有派系而得到更大的派系.用两个大规模的科学家合作网络对提出的算法进行了分析,并讨论了大规模社会网络中的派系分布情况.实验表明,提出的算法可有效地抽取网络中的最大派系.

关键词：最大派系问题、社会网络、派系过滤算法、邻接顶点、邻接边

所属期刊栏目：38

分类号：G35;TP3

资助基金：国家自然科学基金60973069,90924011,60903073,60973120;中国博士后科学基金项目20080431273

在线出版日期：2011-04-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：203-206