[논문]외부 커뮤니티 연관도를 이용한 소셜 네트워크 분석

이현진; 지태창

doi:10.9728/dcs.2011.12.1.069

초록
AI-Helper

소셜 네트워크로부터 커뮤니티를 발견하기 위해서는 네트워크의 노드들에 대한 군집화 과정이 필요하다. 일반적인 군집화 알고리즘은 커뮤니티의 개수를 미리 설정해 주어야 한다는 약점을 가지고 있다. 커뮤니티의 개수에 의해서 군집화의 결과가 달라질 수 있기 때문에 커뮤니티의 개수 선정은 매우 중요하다. 본 논문에서는 커뮤니티 간의 구별을 위한 외부 커뮤니티 연관도를 정의하고, 이를 기존의 군집화 알고리즘과 결합하여 커뮤니티의 개수를 동적으로 발견하는 방법을 제안한다. 제안하는 방법은 커뮤니티 개수의 정확도와 커뮤니티 평균 순도를 기준으로 기존의 방법들과 비교하였다. 실험 결과 기존의 방법들에 비하여 제안하는 방법의 우수한 성능 확인할 수 있었다.

Abstract ▼ AI-Helper

A clustering process for nodes in a network is required to find communities from social networks. General clustering algorithm needs to be configured the number of communities in advance. The number of communities is a very important element because the result of clustering can be different, dependi...

A clustering process for nodes in a network is required to find communities from social networks. General clustering algorithm needs to be configured the number of communities in advance. The number of communities is a very important element because the result of clustering can be different, depending on it. In this paper, we define the external community relationship which is distinguished between communities. Using the external community relationship as an evaluation metric of clustering result, we propose a method to determine the number of communities dynamically. We compare the proposed method to existing methods based on the accuracy of the number of communities and the average purity of communities. Our results show favorable performance for these criteria compared to the existing methods that were evaluated.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

하지만, 외부 커뮤니티에 대한 유사도도 존재하고, 동일 커뮤니티에 속하는 노드들도 외부 커뮤니티에 대한 유사도는 서로 다른 경향을 보일 수 있기 때문에 커뮤니티의 충실도를 결정하는데 있어서 외부 커뮤니티 연관도를 고려해야 한다. 따라서 본 논문에서는 외부 커뮤니티 연관도를 정의하고 이를 군집화 알고리즘의 척도로 이용하여 커뮤니티를 찾는 방법을 제안하였다.

가설 설정

(a)의 외부 커뮤니티 연관도의 값은 (b)의 외부 커뮤니티 연관도 값보다 더 작은 값을 보인다. (a)와 (b)를 비교 하였을 때 (a)가 (b)보다 노드들이 더 밀집되어 있다. 이는 (a)는 외부의 커뮤니티의 영향을 (b) 에 비해 덜 받기 때문에 커뮤니티에 노드들이 유사한 연관도를 가지게 되어 밀집되어 있는 것이다.
하지만 그림 3과 같이 커뮤니티 개수를 효과적으로 설정한 경우 a) 커뮤니티의 노드들이 b) 커뮤니티와 가까운 노드들이 거의 존재하지 않게 된다. 즉, a) 커뮤니티는 외부 커뮤니티와의 관계에서 모두 유사한 속성을 가진 노드들로 구성되는 것이다.
즉, a) 커뮤니티는 외부 커뮤니티와의 관계에서 서로 다른 속성을 가진 노드들로 구성되는 것이다. 하지만 그림 3과 같이 커뮤니티 개수를 효과적으로 설정한 경우 a) 커뮤니티의 노드들이 b) 커뮤니티와 가까운 노드들이 거의 존재하지 않게 된다. 즉, a) 커뮤니티는 외부 커뮤니티와의 관계에서 모두 유사한 속성을 가진 노드들로 구성되는 것이다.
커뮤니티 개수 추정은 성능에 있어서 매우 중요하다 그림 2와 같이 커뮤니티 개수를 효과적으로 추정하지 못한 경우 a) 커뮤니티의 노드들이 b) 커뮤니티와 가까운 노드들과 c) 커뮤니티와 가까운 노드들이 혼재된다. 즉, a) 커뮤니티는 외부 커뮤니티와의 관계에서 서로 다른 속성을 가진 노드들로 구성되는 것이다.

제안 방법

커뮤니티의 개수가 2개이면, 무조건 외부 커뮤니티 연관도는 0이 되서 최적으로 인식 된다. 따라서 커뮤니티의 개수를 3부터 1씩 증가시키면서, 외부 커뮤니티 연관도와 커뮤니티 평균 순도를 측정하였다.
본 논문에서는 소셜 네트워크에서 커뮤니티를 찾기 위하여 군집화 방법을 적용하였다. 이때 커뮤니티의 개수에 따라 결과가 달라질 수 있기 때문에 커뮤니티의 개수 선정은 매우 중요하다.
외부 커뮤니티 연관도가 커뮤니티를 발견하는데 영향을 끼치는 것을 확인하기 위하여 커뮤니티 개수를 변화시키면서 외부 커뮤니티 연관도를 계산하였다.
일반적인 유사도는 노드가 속한 커뮤니티를 결정하는데 사용한 척도이다. 이 척도와 커뮤니티 간의 방향을 이용하여 새로운 노드와 외부 커뮤니티와의 유사도를 계산한다. 새로운 유사도는 방향을 계산하기 쉬운 2차원 평면에서 구하게 된다.
Political blogs의 경우 기본 커뮤니티의 개수가 3이고, 외부 커뮤니티 연관도는 지속적으로 증가하였다. 제안하는 알고리즘으로는 커뮤니티 개수가 5일 때 종료하지만, 그 후에 최소값이 존재하는지 확인하기 위하여 12개까지 실험을 계속하였다. 실험결과 외부 커뮤니티 연관도는 지속적으로 증가하는 것을 확인 할 수 있었다.
따라서 이러한 개수 선정에 있어서 커뮤니티 간의 구별을 위한 외부 커뮤니티 연관도를 정의하고, 이를 기존의 군집화 알고리즘과 결합하여 커뮤니티의 개수를 동적으로 발견하였다. 최적의 커뮤니티를 찾기 위하여 군집화를 수행하는데 있어서 커뮤니티의 개수를 증가시키면서 최적의 커뮤니티를 찾도록 하였다. 따라서 최적의 커뮤니티의 개수를 찾는 시간을 단축하기 위하여 외부 커뮤니티 연관도가 높은 커뮤니티에 대해서만 분할/결합 등의 작업을 수행하는 유연한 군집화에 대해서 연구가 필요하다.

대상 데이터

비교를 한 기존의 방법들은 Newman의 leading eigenvector 방법[12]과 Ghosh 등이 제안한 확장된 modularity-maximization 방법[13]이다. 실험에 사용한 데이터는 앞에서 사용한 데이터와 같은 College football과 Political blogs의 2개의 데이터 세트를 사용하였다. 실험 결과는 <표 3>과 같다.
실험에는 College football[10], Political blogs[11] 데이터 세트를 사용했다. 이 데이터 세트들은 각 데이터 점이 속한 커뮤니티 정보까지 포함하고 있다.

데이터처리

본 논문에서 제안한 외부 커뮤니티 연관도 방법의 성능을 기존 알고리즘과 비교하였다. 비교를 한 기존의 방법들은 Newman의 leading eigenvector 방법[12]과 Ghosh 등이 제안한 확장된 modularity-maximization 방법[13]이다.

이론/모형

K-Means 알고리즘의 단점은 커뮤니티의 개수인 K를 미리 선정해야 한다는 것이다. 본 논문에서는 외부 커뮤니티 연관도를 사용하여 K-Means 군집화 알고리즘을 적용하여 커뮤니티의 개수를 자동으로 결정한다.
본 논문에서는 커뮤니티를 구성할 때 K-means 군집화 알고리즘을 사용하였으며, 유사성 척도는 코사인 상관계수를 사용하였다. 초기 커뮤니티 형성을 위한 K-menas 알고리즘은 표 1과 같다.
커뮤니티 발견 알고리즘의 정확도 기준으로는 발견한 커뮤니티의 평균 순도 (average purity)를 사용했다[9]. 그 정의는 다음과 같다.
새로운 유사도는 방향을 계산하기 쉬운 2차원 평면에서 구하게 된다. 커뮤니티 중심만을 2차원 평면으로 사상하고, 사상하는 방법은 다차원 척도법을 적용한다[6].

성능/효과

커뮤니티 개수를 살펴보면, 외부 커뮤니티 연관도를 이용한 방법과 Newman의 방법이 거의 유사한 정확도로 커뮤니티 개수를 찾아내는 것을 확인할 수 있다. 각각을 살펴보면, 제안하는 방법이 기존 방법들을 압도하는 성능을 보이지는 않는다. 하지만, 커뮤니티 개수와 커뮤니티 평균 순도를 같이 생각해보면, 외부 커뮤니티 연관도를 이용한 방법은 정확한 커뮤니티 개수를 발견하면서, 높은 커뮤니티 평균 순도를 보이는 것을 확인할 수 있다.
제안하는 알고리즘으로는 커뮤니티 개수가 5일 때 종료하지만, 그 후에 최소값이 존재하는지 확인하기 위하여 12개까지 실험을 계속하였다. 실험결과 외부 커뮤니티 연관도는 지속적으로 증가하는 것을 확인 할 수 있었다. 커뮤니티 개수가 3일 때의 외부 커뮤니티 연관도는 19.
커뮤니티 개수가 3일 때 외부 커뮤니티 연관도는 낮았고, 커뮤니티 평균 순도는 가장 낮았다. 외부 커뮤니티 연관도는 커뮤니티 개수가 4부터 급격히 증가했다가, 커뮤니티 개수가 증가하면서 점점 감소하고 있고, 이에 반비례하여 커뮤니티 평균 순도는 증가하는 것을 확인 할 수 있었다. 커뮤니티 개수가 3일 때의 외부 커뮤니티 연관도는 19.
제안하는 외부 커뮤니티 연관도를 이용한 방법은 College football 데이터에서는 가장 높은 커뮤니티 평균 순도를 기록했으나, Political blogs에 대해서는 두 번째 커뮤니티 평균 순도를 나타냈다. 커뮤니티 개수를 살펴보면, 외부 커뮤니티 연관도를 이용한 방법과 Newman의 방법이 거의 유사한 정확도로 커뮤니티 개수를 찾아내는 것을 확인할 수 있다.
제안하는 외부 커뮤니티 연관도를 이용한 방법은 College football 데이터에서는 가장 높은 커뮤니티 평균 순도를 기록했으나, Political blogs에 대해서는 두 번째 커뮤니티 평균 순도를 나타냈다. 커뮤니티 개수를 살펴보면, 외부 커뮤니티 연관도를 이용한 방법과 Newman의 방법이 거의 유사한 정확도로 커뮤니티 개수를 찾아내는 것을 확인할 수 있다. 각각을 살펴보면, 제안하는 방법이 기존 방법들을 압도하는 성능을 보이지는 않는다.

질의응답

핵심어	질문	논문에서 추출한 답변
	네트워크 형태를 잘 이해하는데 있어서 중요한 단계는 무엇인가요?	컴퓨터과학 분야에서는 소셜 네트워크에서 존재하는 웹 사용자들 간의 연결성 확장을 통한 검색 효율을 향상시키려는 연구와 사회현상과 소셜 네트워크상의 현상에 대한 분석, 네트워크의 효율적인 구성에 관한 연구들이 활발히 진행 되고 있다[1]. 네트워크 형태를 잘 이해하는데 있어서 중요한 단계는 그 안에 있는 커뮤니티 (community)를 찾는 것이다. 이러한 커뮤니티를 찾기 위하여 그래프 분할(graph partitioning)이나 군집화(clustering)등 커뮤니티 발견을 위한 다양한 방법들이 제시되었다.
	커뮤니티 발견을 위해서는 군집화 알고리즘이 필요한데 커뮤니티 발견의 주목적은 무엇인가요?	군집화는 유사한 데이터 개체들의 집합인 군집으로 데이터를 분할함으로써 데이터 속에 숨겨져 있는 의미 있는 정보를 자동으로 발견하는 것이다. 커뮤니티를 발견하는 것은 정확하게 해당 커뮤니티를 다른 커뮤니티와 구분 하는 것이 아니라, 비슷한 특징을 가지는 커뮤니티들을 함께 모아둠으로써 사용자가 심도 있는 분석을 할 때 도움을 주고자 하는데 주목적을 지닌다.
	좋은 커뮤니티 선택이란 무엇인가요?	좋은 커뮤니티 선택은 커뮤니티 내의 노드들은 서로 조밀하게(density) 연결되며 외부 커뮤니티의 노드들과는 성기게(sparse) 연결되는 노드의 그룹을 선택하는 것으로 정의된다. 즉, 같은 커뮤니티에 속한 노드 간에는 조밀한 연결이 이루어져야 하고, 외부 커뮤니티 사이에도 성긴 연결이 존재하게 된다.

참고문헌 (13)

최창현, 박건우, 이상훈, "지식검색 서비스에서의 소셜네트워크 기반 영향력 지수 알고리즘", 한국컴퓨터정보학회 논문집, Vol .14, No. 10, 2009.
Yong-Yeol Ahn, James P. Bagrow, Sune Lehmann, " Link communities reveal multiscale complexity in networks", nature, vol. 466, pp.761-764. 2010.

상세보기
Richard Freeman, "Topological Tree Clustering of Social Network Search Results", in Proceedings of the Eight International Conference on Lecture Notes in Computer Science (LNCS 4481), Springer, pp. 760-769, 2007.
Romain Boulet, Bertrand Jouvea, Fabrice Rossi, Nathalie Villa, "Batch kernel SOM and related Laplacian methods for social network analysis", Neurocomputing, Vol. 71, PP. 1257-1273, 2008.

상세보기
강윤섭, 최승진, "공통 이웃 그래프 밀도를 사용한 소셜네트워크 분석", 정보과학회논문지:컴퓨팅 실제 및 레터, Vol. 16, No. 4, pp. 432-436, 2010.
장익진, "다차원 척도 분석법", 연암사, 1998.
Earl Gose, Richard Johnsonbugh and Steve Jost, "Pattern Recognition and Image Analysis", Prentice Hall, 1996.
Douglass R. Cutting, David R. Karger, Jan O. Pedersen and John W. Tukey, "Scatter/Gather: a cluster-based approach to browsing large document collections", In Proc. of the 15th annual international ACM SIGIR, June, pp. 318-329, 1992.
Y. Wang, H. Song, W. Wang and M. An, "A microscopic view on community detection in complex networks", Proceeding of the 2nd PhD Workshop on Information and Knowledge Management, New York, US A, pp. 57-64, 2008.
M. E. J. Newman, "Modularity and community structure in networks", Proceedings of the National Academy of Science, USA, 103(23):8577-8582, 2006.

상세보기
L. A. Adamic and N. Glance, "The Political Blogosphere and the 2004 U. S. Election: Divided They Blog", Proceedings of the 3rd International Workshop on Link Discovery, Chicago, Illinois, pp. 36-43, 2005.
M. E. J. Newman , "Finding community structure in networks using the eigenvectors of matrices", Physical Review E, 74(3), 19 pages, 2006.
R. Ghosh and K. Lerman, "Structure of Heterogeneous Networks", International Conference on Computational Science and Engineering, vol. 4, pp.98-105, 2009.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

외부 커뮤니티 연관도를 이용한 소셜 네트워크 분석
Social Networks Analysis using External Community Relationship 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

질의응답

참고문헌 (13)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

외부 커뮤니티 연관도를 이용한 소셜 네트워크 분석 Social Networks Analysis using External Community Relationship 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

질의응답

참고문헌 (13)

이 논문을 인용한 문헌

저자의 다른 논문 :

지태창 (5)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

외부 커뮤니티 연관도를 이용한 소셜 네트워크 분석
Social Networks Analysis using External Community Relationship 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper