earticle

영어

Given an undirected simple graph, k -club is one of the proposed structures to model social groups that exist in various types in Social Network Analysis (SNA). Maximum k -Club Problem (Mk CP) is to find a k -club of maximum cardinality in a graph. This paper introduces a Genetic Algorithm called HGA+DROP which can be used to approximate maximum k -club in graphs. Our algorithm modifies the existing k -CLIQUE & DROP algorithm and utilizes Heuristic Genetic Algorithms (HGA) to obtain multiple k-clubs. We experiment on DIMACS graphs for k = 2, 3, 4 and 5 to compare the performance of the proposed algorithm with existing algorithms.

한국어

k -club은 소셜 네트워크 분석에서 다양한 형태의 소셜 그룹을 설명하기 위해 제안된 그래프 모델 중 하나로, 단순 그래프에서 부분 정점 집합 S 에 의한 유도 부분그래프(Induced subgraph)의 지름이 k보다 작거나 같은 경우 S 를 k -club이라 한다. 본 논문에서는 유전알고리즘을 이용하여 그래프에서 크기가 최대인 k -club을 찾는 문제인 Mk CP(Maximum k -Club Problem)을 계산하는 HGA+DROP 알고리즘을 제안한다. 본 알고리즘은 k -club을 위한 휴리스틱 알고리즘 k -CLIQUE & DROP을 변형하고 휴리스틱 유전 알고리즘(HGA)을 사용해 한 번의 수행으로 복수 개의 k -club을 구하였다. 기존 알고리즘의 결과와 비교하기 위해 DIMACS 그래프들에 대하여 k 가 2, 3, 4 그리고 5일 때 MkCP를 계산하였다.