사회네트워크분석(social network analysis)은 l개 연결선을 갖는 n개 노드의 자료를 대상으로 한다. 기본적인 자료기술로서 노드 간 최단거리(shortest distance), 근접 중심성(closeness centrality), 중개 중심성(betweenness centrality) 등을 산출한다. 기존의 사회학적 연구에서 다룬 네트워크는 대개 노드 수 n이 수십 또는 수백 정도였으나 최근에는 그 크기가 수십만 또는 수백만에 이르는 경우가 드물지 않다. 이에 따라 사회네트워크분석에서도 자료 규모성(data scalability)의 이슈가 생겼다. 본 연구에서는 몬테칼로(Monte Carlo) 방법을 활용하여 n = 100,000 규모의 임의 네트워크의 작은 세상(small world) 성질을 실증적으로 탐구하고 그 정도 규모에서의 중개 중심성과 근접 중심성의 산출 방법을 제안하고자 한다.
사회네트워크분석(social network analysis)은 l개 연결선을 갖는 n개 노드의 자료를 대상으로 한다. 기본적인 자료기술로서 노드 간 최단거리(shortest distance), 근접 중심성(closeness centrality), 중개 중심성(betweenness centrality) 등을 산출한다. 기존의 사회학적 연구에서 다룬 네트워크는 대개 노드 수 n이 수십 또는 수백 정도였으나 최근에는 그 크기가 수십만 또는 수백만에 이르는 경우가 드물지 않다. 이에 따라 사회네트워크분석에서도 자료 규모성(data scalability)의 이슈가 생겼다. 본 연구에서는 몬테칼로(Monte Carlo) 방법을 활용하여 n = 100,000 규모의 임의 네트워크의 작은 세상(small world) 성질을 실증적으로 탐구하고 그 정도 규모에서의 중개 중심성과 근접 중심성의 산출 방법을 제안하고자 한다.
From a social network of n nodes connected by l lines, one may produce centrality measures such as closeness, betweenness and so on. In the past, the magnitude of n was around 1,000 or 10,000 at most. Nowadays, some networks have 10,000, 100,000 or even more than that. Thus, the scalability issue ne...
From a social network of n nodes connected by l lines, one may produce centrality measures such as closeness, betweenness and so on. In the past, the magnitude of n was around 1,000 or 10,000 at most. Nowadays, some networks have 10,000, 100,000 or even more than that. Thus, the scalability issue needs the attention of researchers. In this short paper, we explore random networks of the size around n = 100,000 by Monte-Carlo method and propose Monte-Carlo algorithms of computing closeness and betweenness centrality measures to study the small world properties of social networks.
From a social network of n nodes connected by l lines, one may produce centrality measures such as closeness, betweenness and so on. In the past, the magnitude of n was around 1,000 or 10,000 at most. Nowadays, some networks have 10,000, 100,000 or even more than that. Thus, the scalability issue needs the attention of researchers. In this short paper, we explore random networks of the size around n = 100,000 by Monte-Carlo method and propose Monte-Carlo algorithms of computing closeness and betweenness centrality measures to study the small world properties of social networks.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
노드 수가 크지 않으므로 굳이 몬테칼로 방법을 적용하지 않고 기존의 완전열거법으로 분석이 가능하다. 그럼에도 불구하고 이 사례를 연구하고자 하는 이유는 몬테칼로 방법을 완전열거법과 비교하기 위해서 이다.
본 연구에서는 이런 문제들을 해결하기 위한 몬테칼로(Monte Carlo) 방법의 활용을 제안한다. 적용 예로서 n = 100,000 규모의 임의 네트워크에 대하여 노드 간 최단거리의 분포를 찾고 아울러 중개 중심성과 근접 중심성을 산출함으로써 작은 세상 성질을 탐구한다.
이에 따라 사회네트워크분석에서 규모성(scalability) 문제는 필히 해결이 필요한 과제가 되었다. 이 연구에서는 메모리 작업의 전제 하에서 완전열거방법에 대한 대안적으로 노드 간 거리의 분포, 중개 중심성, 근접 중심성 등의 근사값을 산출해주는 몬테칼로 알고리즘을 제안하였다.
이 절에서는 임의 네트워크에 대한 몬테칼로 분석결과를 제시하고자 한다. 연구 설계는 다음과 같다(허명회, 2010).
가설 설정
2) 단계 1을 Nrep회 반복한다.
구성원 수 n이 n0 + 1인 사회에서 각 구성원이 평균 µ명을 안다고 가정한다.
그리고 모든 쌍의 구성원 i와 j (≠ i)에 대하여 i가 j를 아는 사건은 독립적으로 성공확률 θ (= µ/n0)의 베르누이 분포를 따라 임의로 결정된다고 가정한다.
제안 방법
마지막으로, 노드 수 17의 부(副)네트워크를 임의추출하여 나머지 노드들에 대한 근접 중심성을 산출하고 완전열거법에 의한 결과와의 일치도로 상관계수를 구하여 보았다. 그림 5.
이를 타개하는 방안으로 크기 n1의 노드 표본을 추출하여 “훈련용” 부(副)네트워크 S = {(i, j) |i ≤ n1, j ≤ n1}를 만들고 이 네트워크의 개별 노드들과 테스트 노드 v간 평균 최단거리를 노드 v의 근접 중앙성 지표로 정의하는 것이 어떨까?
이와 같은 설정 하에서 구성원의 임의 쌍 (I, J)에 대하여 I로부터 J(≠ I)에 도달되는 경로 I → J의 최단길이 DI,J (= D)를 구하여 그 분포를 밝히기로 한다.
본 연구에서는 이런 문제들을 해결하기 위한 몬테칼로(Monte Carlo) 방법의 활용을 제안한다. 적용 예로서 n = 100,000 규모의 임의 네트워크에 대하여 노드 간 최단거리의 분포를 찾고 아울러 중개 중심성과 근접 중심성을 산출함으로써 작은 세상 성질을 탐구한다.
net/). 즉, 임의 네트워크 생성을 위해서는 igraph 라이브러리의 random.graph.game 함수를, 구성원(노드) 간 최단거리의 분포를 구하기 위해서는 path.length.hist 함수를, 2개 노드 간 최단거리를 구하기 위해서는 get.shortest.paths 함수를 사용하였다.
대상 데이터
연구는 R의 igraph 팩키지를 활용하여 수행되었다 (http://igraph.sourceforge.net/). 즉, 임의 네트워크 생성을 위해서는 igraph 라이브러리의 random.
이론/모형
이 절에서는 Zachary (1977)의 가라테 클럽(karate club) 네트워크에 몬테칼로 방법을 적용해보기로 한다. 이 네트워크는 2년에 걸쳐 34명의 구성원간 인간 관계에 대한 연구에서 나왔다.
성능/효과
1과 유사하다. 그러나 계산 시간에 있어서는 완전열거법과 몬테칼로법이 역전되어, 몬테칼로법이 완전열거법에 비해 상대적으로 훨씬 작게 걸렸다.
표준편차에서는 차이가 있었으나 두 방법이 산출한 지표 간 상관은 0.92로서 일치도가 µ = 10인 네트워크에 비해 향상되었다.
질의응답
핵심어
질문
논문에서 추출한 답변
모든 노드 쌍에 대하여 메모리를 할당하는 경우 메모리 요구량을 시스템이 받쳐 주지 못할 수도 있는데, 이러한 문제를 해결하기 위해 본 연구는 어떤 방법을 제안하였는가?
이런 문제들 때문에 개인용 PC에서는 메모리로만 작업하는 경우 n = 10,000 규모까지만 최단경로 및 중심성 지표들을 산출할 수 있다. 본 연구에서는 이런 문제들을 해결하기 위한 몬테칼로(Monte Carlo) 방법의 활용을 제안한다. 적용 예로서 n = 100,000 규모의 임의 네트워크에 대하여 노드 간 최단거리의 분포를 찾고 아울러 중개 중심성과 근접 중심성을 산출함으로써 작은 세상 성질을 탐구한다.
사회네트워크에서 각 노드의 중개 중심성이란 무엇인가?
사회네트워크에서 각 노드의 중개 중심성(betweenness centrality)은 모든 노드 쌍의 최단경로에서 해당 노드를 통과하는 경우의 상대적 빈도로 정의된다. 즉, 노드 v의 중개 중심성 CB(v)는
완전열거란 무엇인가?
임의 네트워크 A로부터 D의 분포를 추정하는 방법으로는 1) 완전열거(complete enumeration)와 2) 몬테칼로 표본추출(Monte Carlo sampling)을 고려한다. 여기서 전자의 완전열거는 모든 노드 쌍에 대하여 최단경로의 거리를 구하는 방법이고 후자의 몬테칼로 표본추출은 모든 노드 쌍 가운데 중복을 허락하여 임의추출된 Nrep개의 노드 쌍 각각에 대하여 최단경로의 거리를 구하는 방법이다. 연구는 R의 igraph 팩키지를 활용하여 수행되었다 (http://igraph.
참고문헌 (4)
허명회 (2010). , 자유아카데미, 서울.
Travers, J. and Milgram, S. (1969). An experimental study of the small world problem, Sociometry, 32, 425-443.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.