计算机科学 ›› 2011, Vol. 38 ›› Issue (1): 203-206.

• 数据库与数据挖掘 • 上一篇    下一篇

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

陈端兵,周玉林,傅彦   

  1. (电子科技大学计算机科学与工程学院 成都611731);(陕西工程勘察研究院 西安710068)
  • 出版日期:2018-11-16 发布日期:2018-11-16
  • 基金资助:
    本文受国家自然科学基金(编号:60973069,90924011,60903073,60973120),中国博士后科学基金项目(编号:20080431273)资助。

Maximal Clique Percolation Algorithm Based on Neighboring Information

CHEN Duan-bing,ZHOU Yu-lin,FU Yan   

  • Online:2018-11-16 Published:2018-11-16

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

关键词: 最大派系问题,社会网络,派系过滤算法,部接顶点,部接边

Abstract: Maximal clique problem(MCP) is a classical and important combinational optimization problem with many prominent applications, for example, information retrieval, signal transmission, computer vision, social network and bioinformatics, etc. Researchers presented many algorithms to solve it by using various strategics, such as branch-and-bound, genetic algorithm, simulation annealing, cross entropy and DNA method. In this paper, a new clique percolation algorithm was presented based on neighboring vertices and edges of clique. From a given clique( it's a vertex at initial) at each step, investigated its all neighboring vertices and expanded it to a larger clique through a neighboring edge of clique. Two large scale author collaboration networks were used to test the performance of proposed algorithm and the clique distribution in large scale social network was also discussed. Experimental results demonstrate that the presented algorithm is efficient to percolation the maximal clique in network.

Key words: Maximal clique problem, Social network, Clique percolation, Neighboring vertex, Neighboring edge

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!