Community detection in social networks is one of the most active problems. Community detection is useful in lots of real world applications such as finding thematic groups and organizing social events. Most of the existing works on the problem have focused on detecting the community considering only the closeness between community members. In the real world, however, it is also important to consider bad relationships between members. If there are many members who are involved in bad relationships in the community, the community cannot be very friendly, which leads to the fail of the original purpose of the community. In this thesis, we propose a new variant of the community detection problem, called friendly-community search. In the proposed problem, for a given graph, we aim to not only find a densely connected subgraph that contains a given set of query nodes but also minimizes the number of nodes involved in bad relationships in the subgraph. The proposed problem is proved to be NP-hard. To solve the friendly-community search problem, we develop two novel algorithms, called Greedy and SteinerSwap that return the near optimal solutions. The Greedy algorithm removes nodes in a given graph while the SteinerSwap algorithm adds nodes to the Steiner tree built on the query nodes. The Greedy algorithm has an additive error bound. The SteinerSwap algorithm can find a near optimal solution for the proposed problem with a low time complexity. The proposed algorithms are evaluated on real datasets, namely Google+, Epinions, and Twitter. On the average over various experimental parameters for all datasets, SteinerSwap performs 11.1 times better than the comparable method, in terms of the number of nodes involved in bad relationships in the subgraph.
최근 몇 년 동안, 페이스북 (facebook), 트위터 (twitter), 구글 플러스 (google+) 같은 온라인 소셜 네트워크의 출현에 따라, 소셜 네트워크 상에서 커뮤니티 발견 (Community detection)은 많은 방면에서 주목을 받고 있다. 예를 들어 동호회를 구성한다거나 소셜 활동 하는 곳에 사용 될 수 있다. 지금까지의 커뮤니티 발견은 커뮤니티 구성원들간에 선호도만을 고려하였다. 하지만 선호도만을 고려하여서는 의미 있는 커뮤니티를 찾기에는 충분하지 않다.
실 세계에서는 같은 학교, 같은 회사, 같은 동네 등과 같은 이유로 사람들은 주변 사람들과 관계를 쌓으며 살아간다. 이러한 관계들 중에 선호하는 관계만큼이나 비선호하는 관계도 존재한다. 사람들은 그들의 개인적인 이유로 싫어하는 사람이나 소셜 네트워크와 연결이 되어있다고 하여도 공적인 관계로 만난 사람들이랑은 개인적인 활동을 같이 하고 싶지 않을 것이다. 실제로 신경 과학 연구에 따르면, 싫어하는 사람이랑 같이 있을 때, 사람의 뇌의 활동이 저하된다고 하였다. 위와 같은 이유로 커뮤니티를 찾을 때, 선호도를 고려한 만큼이나 비선호도를 고려하는 것이 중요하다.
본 연구에서는 비선호도를 고려한 친밀한 커뮤니티 발견 문제를 제안한다. 이 문제에서, 소셜 네트워크를 표시하는 그래프가 주어지면, 질의 노드를 포함하면서 구성원들간의 비선호도가 있는 구성원의 수가 최소가 되는 밀도가 높은 커뮤니티를 찾는다. 또한 제안한 문제가 NP-hard임을 증명하였고, 이 문제를 해결하기 위해 근사 최적 해법을 찾아주는 두 가지 알고리즘을 제안한다. 결론적으로 실험을 통해, 제안된 알고리즘들은 기존의 방법을 적용한 방법에 비해 좋은 성능을 보임을 검증하였다.
