[논문]온라인 소셜 네트워크 생성 모델

이강원

doi:10.6109/jkiice.2020.24.7.914

온라인 소셜 네트워크 생성 모델
On-Line Social Network Generation Model 원문보기

한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering, v.24 no.7, 2020년, pp.914 - 924

이강원 (Department of Industrial Engineering, Seoul National University of Science and Technology)

초록
AI-Helper

본 연구에서는 소셜 네트워크를 생성 할 수 있는 인공적인 네트워크 발생 모델을 제안 하였다. 본 연구에서 제안한 발생 모델은 온라인 소셜 네트워크의 특징인 Small-World 성질과 Scale-Free 성질을 단순하게 표현하는 것에서 벗어나 모델의 두 파라메터를 적절히 조절함으로서 사용자가 원하는 다양한 위상 특성치 값들을 나타내 줄 수 있도록 하였다. 이를 위해 Preferential Attachment의 세기를 조정 할 수 있도록 파라메터 K와 군집화 계수를 적절하게 조정 할 수 있도록 파라메터 P를 도입하였다. K가 0에서 10 그리고 P가 0.3에서 0.5 사이의 조합이나 K = 0과 P = 0.9를 이용하면 소셜 네트워크의 위상적 성질을 보유하는 인공적인 네트워크를 생성할 수 있다. 이 조합 하에서는 Small-World 성질과 Scale-Free 성질이 잘 나타난다. 노드차수 분포는 Power-Law를 따른다. 또한 군집화 계수 0.130 ~ 0.238, 평균 최단거리 5.641 ~ 5.985로 나타났다. 또한 네트워크의 크기를 노드 5,000개에서 10,000개로 증가시켜도 소셜 네트워크 성질을 그대로 유지하는 것으로 나타났다.

Abstract ▼ AI-Helper

In this study we developed artificial network generation model, which can generate on-line social network. The suggested model can represent not only scale-free and small-world properties, but also can produce networks with various values of topological characteristics through controlling two input parameters. For this purpose, two parameter K and P are introduced, K for controlling the strength of preferential attachment and P for controlling clustering coefficient. It is found out on-line social network can be generated with the combinations of K(0~10) and P(0.3~0.5) or K=0 and P=0.9. Under these combinations of P and K small-world and scale-free properties are well represented. Node degree distribution follows power-law. Clustering coefficients are between 0.130 and 0.238, and average shortest path distance between 5.641 and 5.985. It is also found that on-line social network properties are maintained as network node size increases from 5,000 to 10,000.

주제어

표/그림 (14)

표 Table. 1 Average Shortest Path Distance of Social Network Obtained through Measurements
표 Table. 2 Clustering Coefficient of Social Network Obtained through Measurements
표 Table. 3 Power-Law of On-Line Social Network
그림 Fig. 1 Network Generation Process
그림 Fig. 2 TF Process
표 Table. 4 Network Topological Characteristics according to K
표 Table. 5 Network Topological Characteristics according to P
표 Table. 6 Average Network topological Characteristics according to Combination of K and P
그림 Fig. 3 Clustering Coefficient and Average Shortest Path Distance according to K(P = 0.1)
그림 Fig. 4 Clustering Coefficient and Average Shortest Path Distance according to P(K = 10)
표 Table. 7 Combination of K and P for Small-World Property
표 Table. 8 Combination of K and P for Scale-Free Property
표 Table. 9 Topological Characteristics according to Combination of K and P
그림 Fig. 5 Clustering Coefficient and Average Shortest Path Distance according to Number of Node

AI 본문요약
AI-Helper

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

문제 정의

먼저 K와 P의 변화에 따른 네트워크의 위상 특성치 값들의 변화를 살펴보고 이들 조합에 따라 어떤 특성을지닌 네트워크를 생성할 수 있는지 조사하였다.
- 이를 토대로 본 연구의 목적인 소셜 네트워크를 생성하는 방법을 제안하였다.
다음은 네트워크의 크기(노드 개수)가 증가할 때 보이는 성질에 대하여 살펴보았다. 이를 위해 소셜 네트워크를 생성하는 조합인 K = 0과 P = 0.
따라서 본 연구의 목적은 실제적인 소셜 네트워크에 존재하는 Small-World와 Scale-Free 성질뿐만 아니라 네트워크의 특정 위상적 특성치(Topology Characteristics) 값들을 재생산 할 수 있는 인공적인 네트워크 발생 모델을 구축하는 것이다. 본 연구에서는 두 개의 파라메터를갖는 온라인 소셜 네트워크 생성 모델을 제안하고 이 파라메터들의 조절을 통해 원하는 다양한 위상 특성치들을 갖는 네트워크를 생성해 나가는 과정을 보였다.
구축하는 것이다. 본 연구에서는 두 개의 파라메터를갖는 온라인 소셜 네트워크 생성 모델을 제안하고 이 파라메터들의 조절을 통해 원하는 다양한 위상 특성치들을 갖는 네트워크를 생성해 나가는 과정을 보였다. 이를 위해서 본 연구는 서론에 이어 2장에서 소셜 네트워크의 위상적 특성을 살펴보았다.
본 연구에서는 소셜 네트워크를 생성할 수 있는 인공적인 네트워크 발생 모델을 제안했다. 모델은 소셜 네트워크의 특징인 Small-World 성질과 Scale-Free 성질을 효율적으로 나타낼 수 있도록 구축하였다.
그런데 이들 모델은 단편적으로 특정 네트워크를 생성해 줄 뿐 다양한 유형의 네트워크나 다양한 네트워크의 위상 측도값들을 생성하지는못한다. 본 연구의 목적은 2장에서 살펴본 온라인 소셜네트워크의 다양한 위상적 특성을 갖는 네트워크를 생성하는 것이다. 따라서 Small-World, Scale-Free 성질을갖고 있으며 우리가 원하는 다양한 값의 군집화 계수, 노드 간 평균 최단거리, 그리고 다양한 종류의 노드 차수 분포 등을 생성해 줄 수 있는 네트워크 생성 모델이필요하다.
본장에서는 기존의 여러 연구에서 밝힌 온라인 소셜네트워크가 갖는 위상적 특성에 대해서 살펴보았다.

가설 설정

신규로 들어오는 노드의 링크 개수는 평균 3개의 지수분포로 가정하였다. 소수점은 반올림하여 사용하였는데 최소 1개의 링크는 갖도록 하였다.
이루어진다. 네트워크에 새롭게 들어온 노드의 차수는 지수 분포를 가정한다. PA 과정은 신규 노드가 기존 노드와 연결될 때 노드 차수가 큰 노드에 더 큰 확률을 부여하여 연결 노드를 선정한다.

제안 방법

- 네트워크 크기(노드 크기)에 따른 위상 특성치 값들의 변화를 조사하였다.
먼저 Scale-Free 성질을 나타내기 위하여 PA 과정을 사용하였으며 PA의 세기를 조정 할 수 있도록 파라메터 K를 도입하였다. Small-World 성질을 나타내기 위해서 군집화 계수를 적절하게 조정할 수 있도록 파라메터 P를 도입하였다.
BA 모델은 PA를 기본으로 하여 Scale-Free 네트워크를 잘 구현할 수 있다. 다만 본 연구에서는 PA의 세기를 조절하기 위하여 신규노드 i가 기존 노드 j에 연결될 확률을 파라메터 K를 도입하여 다음식 (1)과 같이 변형하였다.
모델은 소셜 네트워크의 특징인 Small-World 성질과 Scale-Free 성질을 효율적으로 나타낼 수 있도록 구축하였다. 먼저 Scale-Free 성질을 나타내기 위하여 PA 과정을 사용하였으며 PA의 세기를 조정 할 수 있도록 파라메터 K를 도입하였다. Small-World 성질을 나타내기 위해서 군집화 계수를 적절하게 조정할 수 있도록 파라메터 P를 도입하였다.
네트워크 발생 모델을 제안했다. 모델은 소셜 네트워크의 특징인 Small-World 성질과 Scale-Free 성질을 효율적으로 나타낼 수 있도록 구축하였다. 먼저 Scale-Free 성질을 나타내기 위하여 PA 과정을 사용하였으며 PA의 세기를 조정 할 수 있도록 파라메터 K를 도입하였다.
본 장에서는 3장에서 제안한 네트워크 생성 모델을이용하여 두 개의 파라메터 K와 P를 변화시켜 나가면서다양한 네트워크를 생성한 후 이들의 위상적 특성을 분석하였다.
985로 앞에서 언급한 기준치 안에 속하므로 Scale-Free 성질도 나타낸다. 아울러 K와 P의 조합에 따른 Power-Law 성질의 세기, 군집화 계수, 평균 최단 거리를 나타내는 표를 만들어서 사용자가 원하는 위성 특성 값은 갖는 인공 소셜네트워크를 생성하도록 하였다. 또한 네트워크의 크기를 노드 5,000개에서 10, 000개로 증가시켜도 소셜 네트워크 성질을 유지하는 것으로 나타났다.
위의 논의를 바탕으로 본 연구에서는 다음의 세 가지 요구 조건들을 만족하는 온라인 소셜 네트워크 생성 모델을 제안하였다.
성질에 대하여 살펴보았다. 이를 위해 소셜 네트워크를 생성하는 조합인 K = 0과 P = 0.5의 경우 노드 크기를 현 5,000개에서 10, 000개까지 늘려가면서 군집화 계수와 평균 최단거리의 추이를 살펴보았다. (그림 5)에서보듯이 먼저 평균 최단거리는 노드 개수가 5,000개 일때 5.
본 연구에서는 두 개의 파라메터를갖는 온라인 소셜 네트워크 생성 모델을 제안하고 이 파라메터들의 조절을 통해 원하는 다양한 위상 특성치들을 갖는 네트워크를 생성해 나가는 과정을 보였다. 이를 위해서 본 연구는 서론에 이어 2장에서 소셜 네트워크의 위상적 특성을 살펴보았다. 3장에서는 소셜 네트워크 발생 모델에 대해 다루었으며 4장에서는 본 연구에서 제안한 발생 모델을 통해 구축한 네트워크들을 분석해보고 5장에 최종 결론을 수록하였다.
다음 <표 4>는 K 값에 따른 위상 특성치의 예상 변화를 요약 정리 하였다. 이에 대한 구체적인 검증은 4장 네트워크 생성 및 분석의 “K와 P의 변화에 따른 네트워크의 위상 특성치 값들의 변화”에서 실증적으로 상세하게 논하였다.
본 연구에서도평균 최단거리 기준은 6으로 하고 군집화 계수는 2장의실측 자료를 토대로 하였다. 즉, 평균 최단거리가 6 이하고 군집화 계수가 0.130 이상이 되는 것을 Small-World 성질로 정하였다. 한편 Scale-Free 성질은 Kolmogorov-Smirnov 테스트를 통해 노드 차수 분포가 Power-Law를따르는지 여부를 기준으로 삼았다.

대상 데이터

K와 P의 조합 16개의 각각 경우에 따라 노드 수 5000 개를 갖는 인공 네트워크를 10개 생성하였다. 그리고 특정 K와 P의 조합에 따른 위상 특성치를 10개 인공 네트워크 위상 특성치들의 평균으로 다음 <표 6>에 나타냈다.
네트워크에 새롭게 참여하는 사용자는 다수개의 노드에 연결되는데 이때 노드 선정은 네트워크 전체가 아닌 일부 노드들만을 대상으로 ‘Preferential Attachment(PA)’ 과정을 통해 이루어진다. 대상이 되는 노드들은 최근 ‘Updating Time’이 Threshold θ 보다 작은 노드들로 구성된다. 그들은 θ 값이 적절하게 선정되면 발생된 인위적인 망이 Small-World 성질을 보여 주고 노드차수가 Power-Law 분포를 따르는 것을 확인하였다.

데이터처리

Ahn[8] 등은 한국 온라인 소셜네트워크인 Cyworld의 전체 네트워크와 Cyworld, Orkut 그리고 Myspace의 샘플 네트워크를 분석하였다. 온라인 소셜 네트워크의 주요 특징을 살펴보기 위하여 노드 차수 분포(Node Degree Distribution), 군집화 계수 (Clustering Coefficient), 차수 상관관계(Degree Correlation) 그리고 평균 최단거리(Average Shortest Path Distance) 분석을 실시하였다. Sun[9]등은 중국 학생들의 온라인소셜 네트워크를 실측하여 네트워크 위상 분석을 수행하였다.

이론/모형

130 이상이 되는 것을 Small-World 성질로 정하였다. 한편 Scale-Free 성질은 Kolmogorov-Smirnov 테스트를 통해 노드 차수 분포가 Power-Law를따르는지 여부를 기준으로 삼았다.

성능/효과

- 그런데 본 연구에서 제안한 모델을 통하여 생성할 수있는 소셜 네트워크는 군집화 계수가 증가하면 평균최단거리도 따라서 증가하고 평균 최단거리를 낮추면군집화 계수도 낮아진다. 이유는 K와 P의 변화에 따른네트워크의 위상 특성치 값들의 변화에서 설명했듯이파라메터 P값의 변화에 따라 군집화 계수와 평균 최단거리가 동시에 증가하거나 감소하기 때문이다.
그런데 (그림 4)에서 보면 반대로 P가 증가할수록 평균 최단거리도 증가함을 볼 수 있다. 3.절의 네트워크 생성 모델은 PA 과정 후 확률 P로 Triad Formation과정을 수행하는데 반복 과정 횟수가 신규 진입 노드가 갖는 링크 수에 도달할 때까지 반복적으로 수행한다. 따라서 P가 증가할수록 PA 과정 수행 횟수는 줄어들게 되고 이러면 슈퍼 허브 노드들의 출현 확률이 낮아지게 되므로 평균 최단 거리는 늘어나게 된다.
Sun[9]등은 중국 학생들의 온라인소셜 네트워크를 실측하여 네트워크 위상 분석을 수행하였다. 노드 차수는 Power-Law 분포를 따르고 아울러 Small-World 성질도 갖고 있는 것으로 확인되었다.
25로 매우 짧은 Small-World 네트워크다. 따라서 본 소셜 네트워크 생성 모델은 모델의 파라메터를 적절하게 조절함으로서 Scale-Free나 Small-World 아니면 두 성질 모두 다 갖고 있는 네트워크를 생성할 수 있어야 한다.
아울러 K와 P의 조합에 따른 Power-Law 성질의 세기, 군집화 계수, 평균 최단 거리를 나타내는 표를 만들어서 사용자가 원하는 위성 특성 값은 갖는 인공 소셜네트워크를 생성하도록 하였다. 또한 네트워크의 크기를 노드 5,000개에서 10, 000개로 증가시켜도 소셜 네트워크 성질을 유지하는 것으로 나타났다.
본 연구에서 제안한 모델을 이용하여 네트워크들을 생성한 후 분석한 결과 Power-Law 성질은 K값에 따라 조절 가능한 것으로 나타났다. K가 0에 수렴 할수록 노드 차수의 Power-Law 성질이 강하게 나타나며 증가하면 Power-Law 성질이 약해진다.
Mislove[7] 등은 4개의 가장 인기 있는 온라인 소셜 네트워크(Flicker, YouTube, LiveJournal 그리고 Orkut)에 대한 대규모(11, 300, 000 사용자, 328, 000, 000 링크)실측 조사와 분석을 시도하였다. 분석 결과는 Web등 기존에 존재하는 여타 네트워크와 매우 다른 특성을 보이는 것으로 나타났는데 Power-Law, Small-World 그리고 Scale-Free 등의 성질이 나타나는 것을 확인하였다. Ahn[8] 등은 한국 온라인 소셜네트워크인 Cyworld의 전체 네트워크와 Cyworld, Orkut 그리고 Myspace의 샘플 네트워크를 분석하였다.
것을 보여준다. 이를 위해 모델을 통해 생성된 네트워크의 노드 차수가 Power-Law 분포를 따르고 랜덤 네트워크에 비해 군집화 계수가 비교적 크고 노드 간 평균최단 거리가 비교적 작다는 것을 보인다. 그런데 Mislove[8]의 연구에서 볼 수 있듯이 실제 온라인 소셜네트워크들이 Small-World와 Scale-Free 성질을 갖고있지만 그들의 위상 특성치들은 매우 다양한 값을 갖는것으로 나타났다.
네트워크 Diameter 도 P가 증가할수록 다소 증가하는 양상을 보인다. 이를 통해 네트워크의 평균 최단거리에 가장 영향을 미치는 요소는 군집화 계수가 아니라 슈퍼 허브 노드의 존재를 가능하게 하는 Power-law 성질이라는 것을 확인할 수 있었다.
한편 Power-Law 성질은 노드 크기를 10, 000개로 늘려도 계속 유지되는 것으로 나타났다. 즉, 노드 개수가 늘어나도 Small-World 성질은 그대로 유지되고 Power-Law 성질도 노드 개수와 무관하게 존재해서 본연구에서 제안한 모델은 노드 개수와는 무관하게 소셜네트워크를 생성해주는 것으로 나타났다.
군집화 계수는 P값을 이용하면 조정 가능한 것으로 나타났으며 P가 1에 근접할수록 군집화 계수는 증가한다. 평균 최단 거리는 K와 P값에 따라 변해나가는데 K가 큰 값을 갖을수록 그리고 P가 1에 수렴할수록 증가하며 그 반대의 경우는 감소하는 것으로 나타났다.

참고문헌 (20)

B. Jang and J. Yoon, "Characteristics analysis of data from news and social network services," IEEE Access, vol.6, pp.18061-18073, 2018.

상세보기
V. Amati, A. Lomi, and A.Mira, "Social Network Model," Annual Review of Statistics and its Application, pp.1-29, Mar. 2018.
S. Tabassum, F. S. F. Pereira, S. Fernandes, and J. Gama, "Social Network Analysis: An Overview," Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, vol. 8, no. 58, pp.1- 30, Apr. 2018.
A. V. Proskurnikov and R. Tempo, "A Tutorial on Modeling and Analysis of Dynamic Social Networks. Part 1," Annual Reviews in Control, pp.1-21, May 2017.
K. W. Lee and J. S. Lee, "Power-Law of Node Degree and Information Diffusion Process," The Journal of Korean Institute of Communication and Information Sciences, vol. 44, no. 10, pp.1866-1877, 2019.

상세보기
J. Kim and M. Hastak, "Social network analysis: Characteristics of online social networks after a disaster," Information Journal of Information Magement, vol.38, pp.86-96, 2018.
A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee, "Measurement and analysis of online social networks," Internet Measurement Conference, 2007.
Y. Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong, "Analysis of topological characteristics of huge online social networking services," , Semantic Web and Web 2.0, 2007.
D. Sun, J. Wu, S. Zheng, B. Hu, and K. M. Carley, "Topological Analysis and measurements of an online chinese student social network," Complex, Part 1, pp.737-748, 2009.
A. Rezvanian and M. R. Meybody, "Stochastic graph as a model for social networks," Computers in Human Behavior, vol.64, pp.621-640, 2016.

상세보기
Q. D. Truong, Q. B. Truong, and T. Tkaki, "Graph method for social network analysis," International Conference on Nature of computation and Communication, pp.276-286, October 2016.
Z. Bu, Z. Xia, J. Wang, and C. Zhang, "A last updating evolution model for online social networks," Physica A, 392, pp.2240-2247, 2013.

상세보기
P. Erdos and A, Renyi, "On the evolution of random graph," Public Mathmatical Institute Hungary Academic Science, vol.5, pp.17-60, 1959.
D. J. Watts and S.H. Strogatz, "Collective dynamics of small-world," Nature, 393, pp.440-442,1998.
A. Barabasi and R. Albert, "Emergence of Scaling in Random Networks," Science 286, pp.509-512, 1999.

상세보기
R. D. Caux, C. Smith, D. Kniveton, R. Black, and A. Philippides, "Dynamic, small-world, social network generation through local agent interactions," Complexity, vol. 19, no. 6, pp. 44-53, 2014.

상세보기
K. W. Lee, H. K. Uhm and H. J. Choe, "Tunable network generation model for small-world and scale-free network," The Journal of Korean Institute of Communication and Information Sciences, vol.42, no.07, pp.1392-1401, 2017.

상세보기
M. Q. Pasta and Z. Jan. (2014, October). Tunable and growing network generation model with community structures. [Online] arXiv:1310.8396v2[csS1].
K. W. Lee, S. W. Moon, B. H. Kim and S. Y. Jun, "Generation method of Korea Internet AS network using BA model," The Journal of Korean Institute of Communication and Information Sciences, vol.43, no.06, pp.986-994, 2018.

상세보기
S. Milgram, "The small world problem," Psychology Today, vol.2, pp.60-67, 1967.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증