CAJ | 학술논문

社团划分是社会网络的一个研究热点。为了快速准确地发现社会网络的社团结构,文中从节点的重要度出发,利用节点之间的相似性,提出了一种基于聚类的社团划分算法—CCDA。其基本思想是每次以节点集合中聚集系数最大的点作为聚类中心,基于最短路径和欧几里得距离计算节点相似度,选择与聚类中心的相似度大于给定阈值的点进行聚类,不断迭代,直至节点集合为空,所产生的各个簇即为不同的社团。对被重复划分的节点,以模块度函数为标准,将节点归属到最合适的社团中。由于该算法每次从重要节点出发,再次选取聚类中心时不需考虑已经被聚类的节点,所以时间复杂度低于GN算法和Newman算法。将该算法应用于经典的社会网络Zachary,结果表明了CCDA算法对社团划分的有效性。
사단화분시사회망락적일개연구열점。위료쾌속준학지발현사회망락적사단결구,문중종절점적중요도출발,이용절점지간적상사성,제출료일충기우취류적사단화분산법—CCDA。기기본사상시매차이절점집합중취집계수최대적점작위취류중심,기우최단로경화구궤리득거리계산절점상사도,선택여취류중심적상사도대우급정역치적점진행취류,불단질대,직지절점집합위공,소산생적각개족즉위불동적사단。대피중복화분적절점,이모괴도함수위표준,장절점귀속도최합괄적사단중。유우해산법매차종중요절점출발,재차선취취류중심시불수고필이경피취류적절점,소이시간복잡도저우GN산법화Newman산법。장해산법응용우경전적사회망락Zachary,결과표명료CCDA산법대사단화분적유효성。
Community division has been a research focus in the social network area. In order to quickly and accurately find community structure in the social network,from the importance of nodes and consulting their similarities,propose a clustering-based community divi-sion algorithm CCDA. The basic idea of this algorithm is selecting the node owning greater clustering coefficient as the clustering center, calculating similarity by the shortest path and Euclidean distance,putting the node with similarity greater than given threshold to cluster, and iterating the process until the node collection is empty. For the repeated division nodes,the algorithm divides each of them into the most appropriate community by using the module function Q. The clusters generated by the algorithm are corresponding with the commu-nities. Since the algorithm starts from the important node and does not consider those clustered nodes when determining new clustering center,the time complexity of it is lower than GN algorithm and Newman algorithm. The results of applying the algorithm to the classical social network,the Zachary network,show that CCDA is valid in community division.