본문 바로가기
HOME> 논문 > 논문 검색상세

학위논문 상세정보

A Study on Determining the Number of Additional Edges and Their Locations based on Community Detection for the Cluster Merging 원문보기

  • 저자

    전병현

  • 학위수여기관

    경희대학교

  • 학위구분

    국내박사

  • 학과

    전자계산공학과

  • 지도교수

  • 발행년도

    2014

  • 총페이지

    101p.

  • 키워드

    클러스터 통합 클러스터 병합 cluster merging cluster integration community detection big data;

  • 언어

    eng

  • 원문 URL

    http://www.riss.kr/link?id=T13536670&outLink=K  

  • 초록

    사회 관계망 서비스, 공동 태깅 시스템, 또는 여론 조사 데이터 분석 시스템 등에서 시스템을 분석하고, 데이터의 특성, 흐름 등을 파악하는데 그래프를 이용한다. 이런 시스템에서 사용자 또는 데이터 사이에 많은 관계가 형성되고, 관계 설정의 과정이 누적되면서 형성된 그룹을 클러스터 또는 커뮤니티라고 부른다. 최근에는 커뮤니티 분석을 이용하여 인맥, 콘텐츠 관리, 유전자 분석, 질병 통제, 바이러스 확산, 또는 마케팅 등의 빅 데이터 분석에 이용한다. 본 논문에서는 커뮤니티 탐색 방법을 이용하여 그래프를 클러스터로 구분하고, 필요에 의해 클러스터를 병합해야할 때 클러스터 사이에 에지를 추가하여 병합하는 클러스터 통합 문제를 제기하고 그 해법에 대해 다룬다. 클러스터 통합 문제는 방향성이 없는 그래프에서 두 클러스터 사이에 새로운 최소 개수의 에지를 추가하여 하나의 클러스터로 통합하는 문제이다. 클러스터 통합 문제는 이미 분류된 빅 데이터의 클러스터를 통합하여 관리하거나, 유전자나 단백질 구조 분석에서 끊어진 연결(missing link)을 찾아 나누어진 구조를 병합하는 경우, 그리고 질병 통제나 바이러스 확산 등을 위해 여러 지역을 하나의 지역으로 통합하여 관리하는 경우 등 다양한 분야에 적용 가능하다. 클러스터 통합을 위한 기본적인 과정은 통합에 필요한 추가 에지 수를 결정하고, 두 클러스터에 추가할 에지의 위치를 결정하는 것으로 이루어진다. 추가 에지 수를 결정하는 방법은 modularity와 적합도를 이용하여 계산하는 방법을 제안하였다. 그리고 클러스터에서 중요한 위치의 노드를 판단하기 위한 기준으로 노드 중심성과 구조적 등위성을 이용하여 클러스터 연결성 지표를 정의하고, 이를 이용하여 추가 에지의 연결 위치를 결정하는 방법을 제안했다. 그리고 커뮤니티 분석 도구들에서 많이 사용되는 커뮤니티 탐색 방법과 제안한 추가 에지 수 결정 방법, 추가 에지 연결 방법에 따라 Zachary의 가라데 클럽 네트워크와 LFR 모델로 생성된 임의의 그래프에 대해 시뮬레이션하고, 결과를 이용하여 분석, 평가하였다. 실험 결과를 통해 Louvain 방법으로 탐색한 클러스터를 통합하기 위해서는, modularity 방법으로 추가 에지 수를 결정하고 degree 지표로 에지의 위치를 결정하는 경우에 좋은 결과를 얻었다. 그리고 Lancichinetti 방법으로 탐색한 클러스터는 적합도 방법으로 추가 에지 수를 결정하고 closeness 지표로 추가 에지의 위치를 결정하고, Girvan-Newman 방법으로 탐색한 경우는 modularity 방법과 vertex betweenness centrality 지표로 추가 에지 수와 위치를 결정하는 것이 좋은 결과를 얻었다. 마지막으로 커뮤니티 탐색 방법을 모르는 경우는 vertex betweenness나 edge betweenness centrality 지표를 이용하여 추가 에지의 위치를 결정하는 경우 좋은 결과를 얻을 수 있었다.


    In social networks, collaborative tagging systems or poll data analysis systems, graphs are used to grasp flows and characteristics of the data and analyze the systems. In the systems like what are mentioned above, many relationships are formed between users as well as between the systems. For the process of forming relationship we need to form accumulated groups. These groups are called either clusters or communities. Recently, community analysis is used for big data analysis such as personal connections management, contents management, genes or proteins analysis, disease control, virus spread and marketing. In this thesis we classify the graphs as clusters using community detection method and merging the clusters on demand, we are raise the problem of cluster merging, which is adding the minimum number of edges between clusters in order to merge them. And we are also dealing with the solution to the problem. The problem of cluster merging is to add a few edges between two clusters in order to merge the clusters into one graph that does not have the direction. The cluster merging problem can be applied to different fields. For example when managing clusters of pre-classified big data as integrated, merging divided structures by finding the missing links in gene structure analysis or protein structure analysis and integrating many areas into one and managing the area to control diseases and prevent the spread of viruses. The basic process of cluster merging consists of two parts. One is to determine the number of edges which are required for the merging and the other one is to determine the location of the edges. We propose the way to calculate the number of additional edges for the problem using modularity and fitness. Moreover, as a standard to determine the nodes in important position we define the connectivity index using node centrality and structural equivalence and we propose the way to determine the location of additional edges. The proposed model is analyzed and evaluated through intensive simulation on the random graph that is made with the LFR model and the Zachary's karate club network according to the proposed methods and the community detection method that is widely used in community analysis tools. In case of the clusters that are detected by using Louvain method with the results of the experiments, we could get good results through deciding the number of edges to be added with modularity method and the position of the edges with degree index. In case of the clusters detected by Lancuchunetti method, better results were got with the fitness for the decision of the number of edges and the closeness index for the decision of the position of the link. Lastly, In case of clusters detected by Girvan-Newman method, better results were got with the modularity for the decision of the number of edges and vertex betweenness centrality index for the decision of the position of the link.


 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역