CAJ | 학술논문

针对GN算法在社团结构发现中时间复杂度高等问题,提出一种基于中心度的GN改进算法(DCGN).该算法根据节点中心度以及节点之间的最短路径首先确定社团结构中心节点集,然后逐步删除社团结构中心节点之间的最大边介数连边,完成社团结构划分.DCGN算法避免了GN算法边介数计算开销大的问题,算法的时间复杂度约为D(cmn),其中c为常数,n为网络成员数,m为网络连边数.将DCGN和GN算法同时应用到Za-chary网络及计算机随机生成网络中并进行了比较.实验结果表明,所提出的DCGN算法在运行效率和效果方面较之GN算法均具有一定的优势.
침대GN산법재사단결구발현중시간복잡도고등문제,제출일충기우중심도적GN개진산법(DCGN).해산법근거절점중심도이급절점지간적최단로경수선학정사단결구중심절점집,연후축보산제사단결구중심절점지간적최대변개수련변,완성사단결구화분.DCGN산법피면료GN산법변개수계산개소대적문제,산법적시간복잡도약위D(cmn),기중c위상수,n위망락성원수,m위망락련변수.장DCGN화GN산법동시응용도Za-chary망락급계산궤수궤생성망락중병진행료비교.실험결과표명,소제출적DCGN산법재운행효솔화효과방면교지GN산법균구유일정적우세.