论文研究一个基于中心度的社团结构发现新算法.pdf

针对GN算法在社团结构发现中时间复杂度高等问题，提出一种基于中心度的GN改进算法（DCGN）。该算法根据节点中心度以及节点之间的最短路径首先确定社团结构中心节点集，然后逐步删除社团结构中心节点之间的最大边介数连边，完成社团结构划分。DCGN算法避免了GN算法边介数计算开销大的问题，算法的时间复杂度约为O(cmn)，其中c为常数，n为网络成员数，m为网络连边数。将DCGN和GN算法同时应用到Zachary网络及计算机随机生成网络中并进行了比较。实验结果表明，所提出的DCGN算法在运行效率和效果方面较之GN算法均具有一定的优势。