We look into the community evolution in the Cyworld guestbook data. We use the hierarchical link clustering (HLC) approach to identify communities. HLC allows nodes to belong to multiple communities in contrast to other community identification algorithms that are node-based and allow no overlap.
We define the following six key events in community evolution: birth, death, merge, split, growth, and shrink. We present our analysis results in terms of the six events. We then investigate how community evolves in the evolving networks. Our work reveals the life cycle of communities in online social network. Wefirst shows that the life expectancy of large communities is much longer than that of small communities, and large proportion of community members change over time. Then we find that the distributions of new-born and died communities are close. We discover that the larger communities split into a larger number of pieces and the pieces are similar sized. We show that higher relative node overlap leads to Merge of two communities.
본 논문에서 우리는 싸이월드 방명록 로그에서 추출한 온라인 소셜 네트워크에서 커뮤니티 구조의 변화 양상을 분석했다. 결과의 신뢰성 향상을 위해서 우선 싸이월드 방명록 로그에 존재하는 스팸 메시지들을 필터링한 후, 사용자간 메시지 교환에 기반한 네트워크를 구성했다. 이로부터 가장 최근 소개된 계층적 링크 클러스터링(HLC) 알고리즘을 적용하여 커뮤니티 구조를 추출했다. 이 알고리즘은 종전에 소개된 모듈성 기반의 커뮤니티 추출 알고리즘과 다르게 한 사용자가 여러 커뮤니티에 속할 수 있다는 장점을 가진다. 이 후 우리는 커뮤니티의 변화 과정에서 존재할 수 있는 6 가지 다른 변화 양상을 탄생, 소멸, 성장, 축소, 분리, 병합으로 정의하고, 커뮤니티 구조의 변화 양상을 분석했다.
본 연구의 결과로 우리는 온라인 소셜 네트워크에서 대형 커뮤니티 구조는 소형 커뮤니티 구조에 비해서 더 높은 평균 여명을 가지고 있음을 밝혔고, 그 과정에서 대형 커뮤니티 구조의 멤버쉽에는 상대적으로 많은 변화가 있음을 보였다. 우리는 네트워크 크기에 큰 변화가 없는 시점에도 내부에서 커뮤니티 구조의 탄생과 소멸이 끊임없이 일어나고 있음을 발견했다. 또한, 대형 커뮤니티 구조는 상대적으로 더 많은 숫자의 소형 커뮤니티 구조들로 분리되는 것을 발견했고, 또 이렇게 분리된 소형 커뮤니티 구조들은 비슷한 크기를 가지고 있었다. 마지막으로, 우리는 두 커뮤니티 구조에서 동시에 활동하고 있는 사용자의 비율이 클수록 높은 확률로 두 커뮤니티가 병합되는 것을 확인했다.
