시간에 따라 진화하는 네트워크에서 커뮤니티 식별 알고리즘
김바울, 배준현, Sang‐Uk Kim · 한국정보과학회 학술발표논문집 · 2011
다양한 네트워크에서 커뮤니티를 분석하고 그 구조를 발견하는 것은 복잡한 네트워크의 복잡도를 낮추어 다양한 시스템들을 이해하고 시각화하는데 중요하다. Link Community Detection(LCD) 기법은 노드 간 간선의 유사도(Similarity)와 분할 밀도(Partition Density)를 이용하여 커뮤니티 구조를 발견하는 기법이다. 이 기법은 노드의 중복을 허용하고, 커뮤니티의 생성, 소멸, 또는 커뮤니티간의 병합이 빈번히 발생하는 다이나믹 네트워크에 적용하여 커뮤니티 구조를 발견할 수 있다. 하지만 시간에 따라 진화하는 네트워크에서 이전 시간에 발견한 커뮤니티가 현재 발견 된 커뮤니티인지 알지 못하면 분석 및 응용이 어렵다. 또한 단 시간에 네트워크가 많이 변화하면 전 시간에 발견한 커뮤니티 집합에서 현 시간에 발견한 커뮤니티 집합의 연관성을 찾을 수 없는 문제점이 있다. 따라서 본 연구에서는 시간에 따라 진화하는 네트워크에서 커뮤니티의 발견 과정에서부터 커뮤니티를 추적하고, 각 시간에 발견한 커뮤니티 집합들을 식별하는 알고리즘을 제안한다. 제안하는 알고리즘은 커뮤니티의 창립 원소와 두 커뮤니티간의 유사도를 비교함으로써 각 커뮤니티를 식별한다.
Cited by 0 works.