Online social networks have been provided the new relationship formation to people`s lives. In online social networks, users can build relationships with people whom they cannot meet in the off-line world. They not only interact with each other, but also form communities.
The measurement and analysis of online social networks are important to improve current systems of online social networks. Online social networks have been analyzed from a macroscopic and microscopic view. Especially, we can find how actively users interact with each other in communities and how the evolution of communities affects properties of online social networks from a microscopic view by analyzing communities. Several algorithms have been proposed to detect communities in networks. However, these algorithms using modularity as the measure identify different communities depending on the order of input data.
In this paper, we compare three community identification algorithms: CNM, Wakita, and MAM algorithm. We evaluate scalability, variance in modularity, and consistency in clustering of three algorithms with randomly ordered datasets of various networks. To our best knowledge, this is the first work to compare community identification algorithms from a view of the consistency. We show that the modularity of three algorithms depends on the order of input data and three algorithms have the consistency problem.
온라인 소셜 네트워크는 인간의 삶에 새로운 관계 형성을 제공하고 있다. 서비스를 이용하는 유저들은 온라인 소셜 네트워크를 통해 오프라인 세계에서는 만날 수 없는 사람과도 관계를 형성할 수 있다. 온라인 소셜 네트워크가 급격히 성장함에 따라, 온라인 소셜 네트워크에 대한 많은 연구가 진행되고 있다. 특히, 온라인 소셜 네트워크에 존재하는 커뮤니티를 분석함으로써, 유저들의 행동과 유저 간의 관계를 네트워크에 대한 미시적 관점에서 살펴볼 수 있다. 커뮤니티를 찾기 위해 수많은 알고리즘들이 제안되었는데, 이 알고리즘들은 입력 받는 데이터의 순서에 따라 각각 다른 커뮤니티를 찾는 문제를 가지고 있다. 이 연구에서는 씨엔엠, 와키타, 엠에이엠 알고리즘을 비교해 보았다. 먼저, 실행 속도 면에서는 엠에이엠 알고리즘이 가장 좋은 성능을 보였다. 그리고 각각의 네트워크에서 데이터의 순서를 임의로 변경해서 100개의 데이터 셋을 만들고, 그것을 이용해서 각 알고리즘의 마듈레러티를 측정해 보았다. 같은 데이터 셋에서도 알고리즘에 따라 그 값이 달랐고, 같은 알고리즘에서도 데이터의 순서에 따라 마듈레러티 값이 변하게 된다. 또한, 두 노드가 동일한 커뮤니티에 속하게 되는 횟수를 이용해서 일관성을 측정하기 위한 척도를 제시하고, 이를 이용해서 세 알고리즘을 커뮤니티의 일관성 측면에서 비교해 보았다.
