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

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