전통적인 사회관계망 분석에 있어서 각 노드의 매개 중심도는 메시지 전달 측면에서의 각 노드들의 상대적인 중요도를 파악하는 척도로 오랫동안 사용되어 왔다. 하지만, 매개 중심도를 산출하기 위한 계산 복잡도가 높기 때문에 노드의 수와 간선의 수가 매우 많은 대규모 사회관계망에서는 각 노드의 매개 중심도를 산출하기가 어렵다. 본 논문에서는 각 노드들마다 자신의 지역정보, 즉 이웃노드들이 지닌 각각의 이웃노드 정보를 활용하여 구성가능한 확장 자아 네트워크(Expanded Ego Network)를 새롭게 정의하고 이러한 네트워크를 기반으로 확장 자아 매개 중심도(Expanded Ego Betweenness Centrality)를 정의한다. 일반적인 사회관계망의 특성인 척도 없는 네트워크(Scale-free Network)를 생성할 수 있는 Barab$\acute{a}$si-Albert 네트워크 모델을 사용한 실험을 통하여 제안한 확장 자아 매개 중심도의 각 노드별 순위는 기존의 전통적인 방식으로 산출한 매개 중심도의 각 노드별 순위와 거의 일치함을 보인다.
전통적인 사회관계망 분석에 있어서 각 노드의 매개 중심도는 메시지 전달 측면에서의 각 노드들의 상대적인 중요도를 파악하는 척도로 오랫동안 사용되어 왔다. 하지만, 매개 중심도를 산출하기 위한 계산 복잡도가 높기 때문에 노드의 수와 간선의 수가 매우 많은 대규모 사회관계망에서는 각 노드의 매개 중심도를 산출하기가 어렵다. 본 논문에서는 각 노드들마다 자신의 지역정보, 즉 이웃노드들이 지닌 각각의 이웃노드 정보를 활용하여 구성가능한 확장 자아 네트워크(Expanded Ego Network)를 새롭게 정의하고 이러한 네트워크를 기반으로 확장 자아 매개 중심도(Expanded Ego Betweenness Centrality)를 정의한다. 일반적인 사회관계망의 특성인 척도 없는 네트워크(Scale-free Network)를 생성할 수 있는 Barab$\acute{a}$si-Albert 네트워크 모델을 사용한 실험을 통하여 제안한 확장 자아 매개 중심도의 각 노드별 순위는 기존의 전통적인 방식으로 산출한 매개 중심도의 각 노드별 순위와 거의 일치함을 보인다.
In traditional social network analysis, the betweenness centrality measure has been heavily used to identify the relative importance of nodes in terms of message delivery. Since the time complexity to calculate the betweenness centrality is very high, however, it is difficult to get it of each node ...
In traditional social network analysis, the betweenness centrality measure has been heavily used to identify the relative importance of nodes in terms of message delivery. Since the time complexity to calculate the betweenness centrality is very high, however, it is difficult to get it of each node in large-scale social network where there are so many nodes and edges. In this paper, we define a new type of network, called the expanded ego network, which is built only with each node's local information, i.e., neighbor information of the node's neighbor nodes, and also define a new measure, called the expended ego betweenness centrality. Through the intensive experiment with Barab$\acute{a}$si-Albert network model to generate the scale-free networks which most social networks have as their embedded feature, we also show that the nodes' importance rank based on the expanded ego betweenness centrality has high similarity with that based on the traditional betweenness centrality.
In traditional social network analysis, the betweenness centrality measure has been heavily used to identify the relative importance of nodes in terms of message delivery. Since the time complexity to calculate the betweenness centrality is very high, however, it is difficult to get it of each node in large-scale social network where there are so many nodes and edges. In this paper, we define a new type of network, called the expanded ego network, which is built only with each node's local information, i.e., neighbor information of the node's neighbor nodes, and also define a new measure, called the expended ego betweenness centrality. Through the intensive experiment with Barab$\acute{a}$si-Albert network model to generate the scale-free networks which most social networks have as their embedded feature, we also show that the nodes' importance rank based on the expanded ego betweenness centrality has high similarity with that based on the traditional betweenness centrality.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
따라서, 노드의 수와 간선의 수가 매우 많은 대규모 사회관계망에서 각 노드의 매개 중심도를 산출하거나 각 노드들에 대한 매개 중심도 측면의 상대적인 중요도 순위를 얻어내는 작업은 매우 어렵다. 본 논문에서는 이와 같은 문제점을 해결하기 위해 사회관계 망에서 빠른 시간 내에 모든 노드들에 대한 매개 중심도 기반 중요도 순위를 추정해내는 새로운 방안을 제안한다.
본 논문은 사회관계망 분석에 있어서 전통적으로 많이 활용되어 온 각 노드의 매개 중심도 값을 보다 빠르게 산출하기 위하여 각 노드에 대한 지역 정보를 활용한 확장 자아 네트워크를 새롭게 정의하고 그 확장 자아 네트워크를 활용 한 확장 자아 매개 중심도를 산출하는 방법을 제안하였다. 또한 확장 자아 매개 중심도의 노드별 상대적 순위가 기존의 전통적인 방법으로 구한 매개 중심도의 노드별 상대적 순위와 거의 차이가 없음을 실험을 통하여 증명하였다.
본 논문은 이 4가지 중심도 측정들 중에서 매개 중심도에 관한 연구 결과를 소개한다. 각 노드들의 매개 중심도를 구하기 위해서는 각 노드 사이의 최단경로를 구하는 작업을 수행해야 하며 이와 같은 계산은 시간 복잡도(Time Complexity)가 높다고 알려져 있다[3].
제안 방법
본 논문에서는 이와 같이 실제 사회관계망을 모델링하는 네트워크를 랜덤하게 생성하였으며 노드의 수 n은 50, 200, 500, 1000개로 나누어 실험하였고, 새로운 노드를 추가할 때 기존에 이미 생성되 어 있는 노드들과 생성하는 간선의 수 λ는 1로 설정하였다. 마지막으로 Triad를 형성하는 추가 간선이 생성되는 확률인 pt는 0.1, 0.5, 0.9로 나누어 설정하였다. Fig.
본 논문에서는 이와 같이 실제 사회관계망을 모델링하는 네트워크를 랜덤하게 생성하였으며 노드의 수 n은 50, 200, 500, 1000개로 나누어 실험하였고, 새로운 노드를 추가할 때 기존에 이미 생성되 어 있는 노드들과 생성하는 간선의 수 λ는 1로 설정하였다.
본 논문은 [7]의 결과를 더욱 발전시켜서 자아 네트워크와 그 구성측면에서 구성의 용이성이 동일한 확장 자아 네트워크를 정의하고, 전체 네트워크 기반의 노드 중요도 순위와 더욱 유사성이 높은 중요도 순위를 산출할 수 있는 확장 자아 매개 중심도 (Expanded Ego Betweenness Centrality)를 제안한다.
본 장에서는 주어진 전체 네트워크에 대하여 다음과 같은 세 개의 데이터 리스트에 대한 순위 측면에서의 유사성 비교 분석을 수행한다.
한편, 본 논문에서는 각 노드마다 확장 자아 네트워크를 구성하고 이 네트워크에서 각각 독립적으로 “확장 자아 매개 중심도(Expanded Ego Betweenness Centrality)”를 산출하여 이들 간의 상대적 중요도 순위를 정한다.
대상 데이터
본 실험을 위하여 Python 2.7과 NetworkX, Scipy, Numpy 등의 Python 모듈을 활용하였으며 iMAC (3.4Ghz Intel Core i7, 16GB 1600Mhz DDR3) OS X (Version 10.8.2)에서 본 실험을 수행하였다.
데이터처리
한편, 각 노드별 CB(i) 값과# 값의 순위 유사성 및 CB(i) 값과 # 값의 순위 유사성을 얻기 위하여 스피어만 상관계수(Spearman correlation coefficient)를 사용하였다.
이론/모형
실험 결과의 가치를 높이기 위하여 일반적인 사회관계망이 지닌 특성인 척도 없는 네트워크를 성성할 수 있는 Barabási-Albert 네트워크 모델을 활용하였다.
확장 자아 매개 중심도의 정확성 실험의 조사 대상 네트워크를 생성하기 위하여 본 논문에서는 Barabási-Albert 네트워크 [13]라고 알려진 척도 없는(Scale-free) 네트워크 생성 방법에 노드간의 클러스터링(Clustering) 특성을 부여한 네트워크 생성 모델 [14]을 사용한다.
성능/효과
1에서 주어진 전체 네트워크에서 각 노드들에 대한 1) 매개 중심도, 2) 자아 매개 중심도, 3) 확장 자아 매개 중심도 및 상대적인 순위(Rank)를 비교하여 보여준다. 각 매개 중심도들에 대한 값 자체는 차이가 있지만 상대적인 순위를 비교해 보면 본 논문에서 제안하는 확장 자아 매개 중심도가 자아 매개 중심도보다 기존 매개 중심도 와 더욱 유사함을 알 수 있다.
본 논문은 사회관계망 분석에 있어서 전통적으로 많이 활용되어 온 각 노드의 매개 중심도 값을 보다 빠르게 산출하기 위하여 각 노드에 대한 지역 정보를 활용한 확장 자아 네트워크를 새롭게 정의하고 그 확장 자아 네트워크를 활용 한 확장 자아 매개 중심도를 산출하는 방법을 제안하였다. 또한 확장 자아 매개 중심도의 노드별 상대적 순위가 기존의 전통적인 방법으로 구한 매개 중심도의 노드별 상대적 순위와 거의 차이가 없음을 실험을 통하여 증명하였다. 실험 결과의 가치를 높이기 위하여 일반적인 사회관계망이 지닌 특성인 척도 없는 네트워크를 성성할 수 있는 Barabási-Albert 네트워크 모델을 활용하였다.
즉, 사회관계망의 특성과 약간 거리가 있는 Bernoulli 네트워크에서도 자아 네트워크를 사용한 노드 중요도 측정값이 매우 의미가 있음을 밝힌 것이다. 아울러, 실제 사회관계망에서 도출한 8개의 샘플 네트워크 데이터를 사용하여 실험한 결과 그 유사도는 평균적으로 95% 정도를 나타냄을 보였다. 이렇듯 매개 중심도 분석에 있어서 비교적 구성이 용이한 자아 네트워크의 사용이 노드들 간의 상대적인 중요도를 파악함에 있어서 그 정확성이 매우 높음을 알 수 있다.
이와 같은 페이스북의 보안정책은 임의의 노드 vi에 대한 자아 네트워크 구성을 다소 어렵게 만들며, 2차 자아 네트워크 구성을 위해서는 임의의 사용자를 대표하는 노드 vi의 #에 속한 노드들끼리 연결된 간선 집합인 # 정보가 필요하며 이는 다시 해당 사용자의 친구들에 대한 친구들까지도 그 사용자에게 정보 열람 허가를 해주어야하기 때문에 2차 자아 네트워크 구성은 더욱더 힘들게 만들다. 여기서 주목할 점은 만약 임의의 사용자의 친구들 모두가 자신의 정보 공개를 그 사용자에게 허용한다면 그 사용자를 중심으로 한 자아 네트워크 구성이 가능하며 또한 본 논문에서 제안하는 확장 자아 네트워크인 Xi도 쉽게 구성할 수 있다는 점이다. 즉, 자아 네트워크와 확장 자아 네트워크는 구성의 용이성이 동일하다.
즉, 본 논문에서 제안하는 확장 자아 네트워크 Xi는 기존의 자아 네트워크 Ωi와 비교하여 동일한 구성의 용이성을 가지면서도 자아 네트워크 Ωi보다 더욱 많은 지역 정보를 가지고 있기 때문에 사회 관계망 분석에 대한 정확성을 좀 더 높여줄 수 있다.
후속연구
확장 자아 네트워크의 구성과 이에 대한 확장 자아 매개 중심도 산출은 각 노드별로 독립적으로 수행이 가능하기 때문에, 네트워크의 각 노드별로 병렬적인 동시 계산이 가능하다. 그러므로, 본 논문에서 제안한 확장 자아 매개 중심도는 대규모 사회 관계망에서 상대적인 노드의 중요도를 파악하는데 많은 도움이 될 것으로 기대된다. 또한, 무선 이동 네트워크 분야에서 사회관계망 분석기법을 도입할 때 지리적으로 분산되어 있는 이동 노드들의 연결 관계 정보를 하나의 중앙 집중화 된 서버에 기록하기가 어렵기 때문에 각 노드들이 자율적으로 확장 자아 네트워크를 구성하고 각자 자신의 확장 자아 매개 중심도를 파악하여 인접한 다른 노드들과 중요도를 상대적으로 비교하는 데에도 활용될 수 있다.
그러므로, 본 논문에서 제안한 확장 자아 매개 중심도는 대규모 사회 관계망에서 상대적인 노드의 중요도를 파악하는데 많은 도움이 될 것으로 기대된다. 또한, 무선 이동 네트워크 분야에서 사회관계망 분석기법을 도입할 때 지리적으로 분산되어 있는 이동 노드들의 연결 관계 정보를 하나의 중앙 집중화 된 서버에 기록하기가 어렵기 때문에 각 노드들이 자율적으로 확장 자아 네트워크를 구성하고 각자 자신의 확장 자아 매개 중심도를 파악하여 인접한 다른 노드들과 중요도를 상대적으로 비교하는 데에도 활용될 수 있다. 본 논문의 연구 결과를 더욱 확장하여 향후에는 각 노드의 지역 정보만을 활용하여 자신과 사회적 관계를 자주 형성한 노드들과의 커뮤니티(Community) 구성방법에 대해 연구할 예정이다.
또한, 무선 이동 네트워크 분야에서 사회관계망 분석기법을 도입할 때 지리적으로 분산되어 있는 이동 노드들의 연결 관계 정보를 하나의 중앙 집중화 된 서버에 기록하기가 어렵기 때문에 각 노드들이 자율적으로 확장 자아 네트워크를 구성하고 각자 자신의 확장 자아 매개 중심도를 파악하여 인접한 다른 노드들과 중요도를 상대적으로 비교하는 데에도 활용될 수 있다. 본 논문의 연구 결과를 더욱 확장하여 향후에는 각 노드의 지역 정보만을 활용하여 자신과 사회적 관계를 자주 형성한 노드들과의 커뮤니티(Community) 구성방법에 대해 연구할 예정이다.
질의응답
핵심어
질문
논문에서 추출한 답변
사회관계망은 무엇인가?
사회관계망(Social Network)은 개인과 개인 사이의 사회적 관계를 연결선으로 표현하여 구성한 논리적 네트워크를 지칭 한다[1]. 이러한 사회관계망을 기반으로 하는 웹 서비스들이 현재 계속해서 증가하고 있으며, 이러한 웹서비스들은 사용자들에게 다른 사용자들과 관계를 맺고, 관심사를 공유 하고, 서로 소통할 수 있도록 도와줌으로써 사람들 간의 인맥형성과 정보교환을 위한 새로운 플랫폼을 제시하고 있다[2].
사회관계망 분석 기법 중 노드 중심성 분석 기법은 네트워크에 존재하는 노드들 중에서 중요도가 높은 노드를 선별하기 위하여 어떤 측정 방법을 사용하는가?
사회관계망 분석 기법 중에는 노드 중심성(Centrality) 분석, 노드 유사성(Similarity) 분석, 약한 간선(Weak Tie)/강한 간선(Strong Tie) 분석, 커뮤니티 검출(Community Detection)등 다양한 기법들이 존재한다[3, 4]. 그 중에서 노드 중심성은 네트워크에 존재하는 노드들 중에서 중요도가 높은 노드를 선별하기 위하여 사용하며 대표적으로 연결 중심도(Degree Centrality), 거리 중심도(Closeness Centrality), 매개 중심도(Betweenness Centrality), 고유벡터 중심도 (Eigenvector Centrality) 측정들이 존재한다.
사회관계망 분석 기법에는 어떤 것들이 있는가?
사회관계망 분석 기법 중에는 노드 중심성(Centrality) 분석, 노드 유사성(Similarity) 분석, 약한 간선(Weak Tie)/강한 간선(Strong Tie) 분석, 커뮤니티 검출(Community Detection)등 다양한 기법들이 존재한다[3, 4]. 그 중에서 노드 중심성은 네트워크에 존재하는 노드들 중에서 중요도가 높은 노드를 선별하기 위하여 사용하며 대표적으로 연결 중심도(Degree Centrality), 거리 중심도(Closeness Centrality), 매개 중심도(Betweenness Centrality), 고유벡터 중심도 (Eigenvector Centrality) 측정들이 존재한다.
참고문헌 (15)
H. Kwak, C. Lee, H. Park, and S. Moon, "What is Twitter, a social network or a new media?," in Proceedings of the 19th International World Wide Web (WWW) Conference, pp.591-600, April 26-30, 2010.
R. Pittinger, "Linkbar and Forensik: Two Systems for Interactive Visualization of Online Social Networks," University of Applied Sciences Augsburg, 2007.
Lei Tang and Huan Liu, "Community Detection and Mining in Social Media," Synthesis Lectures on Data Mining and Knowledge Discovery, Vol.2, No.1, 2010.
M. Baglioni, F. Geraci, M. Pellegrini and E. Lastres, "Fast Exact Computation of Betweenness Centrality in Social Networks," in Proceedings of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp.450-456, 2012.
M. Everett, S. P. Borgatti, "Ego Network Betweenness," Social Networks, Vol.27, No.1, pp.31-38, Jan., 2005.
F. Odella, "Using Ego-networks in Surveys: Methodological and Research Issues," In Proceedings of International Conference on Network Science, May, 2006.
E. Daly and M. Haahr, "Social Network Analysis for Information Flow in Disconnected Delay-Tolerant MANETs," IEEE Trans. on Mobile Computing, Vol.8, No.5, pp.606-621, May, 2009.
Y.-h. Kim, C.-M. Kim, Y.-H. Han, Y.-S. Jeong and D.-S. Park, "Betweenness of Expanded Ego Networks in Sociality-Aware Delay Tolerant Networks," Ubiquitous Information Technologies and Applications (LNEE, Proc. of CUTE 2012), Springer, pp.499-505, Dec., 2012.
A. Mtibaa, M. May, M. Ammar, and C. Diot. "PeopleRank: combining social and contact information for opportunistic forwarding," In Proceedings of INFOCOM, 2010.
F. Fabbri and R. Verdone, "A sociability-based routing scheme for delay-tolerant networks," EURASIP Journal on Wireless Communications and Networking, Jan., 2011.
A. L. Barabasi and R. Albert "Emergence of scaling in random networks," Science 286, pp.509-512, 1999.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.