본 문서에서는 EDBT 2020에서 발표될 "BalanSiNG: Fast and Scalable Generation of Realistic Signed Networks" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
그러나 부호화된 네트워크는 광범위하게 활용되고 있음에 비해, 어떻게 해야 실제 부호화된 네트워크와 비슷한 성향을 가지며 새로운 형태의 다른 부호화된 네트워크를 생성할 수 있는지에 대한 연구는 많이 진행되지 않았습니다. 네트워크 생성 (network generation) 문제는 실세계 그래프 형성의 이해에 대한 중요한 문제로, 네트워크 생성 문제는 다음과 같은 방안으로 많이 활용되고 있습니다.
Desired Properties of Signed Networks
그렇다면 부호화된 네트워크를 생성하는데 있어서 어떠한 특성들이 만족되어야 할까요? 이를 위해서 본 절에서는 실세계 부호화된 네트워크들이 가지는 공통적인 특성들을 살펴봅니다. 실세계 부호화된 네트워크는 부호에서 비롯된 독특한 특징들을 가지고 있는 동시에 부호가 없는 네트워크의 구조적 특징도 동시에 가집니다. 아래 그림은 실세계 부호화된 네트워크인 BitcoinA, BitcoinO, Epinions 데이터에 대한 특성들의 경향을 보여줍니다.
그림 3. 부호화된 네트워크 생성을 위한 자기 유사성. 파란선은 양의 간선이고 빨간선은 음의 간선을 의미.
자기 유사성 (self-similarity)이란 자기 유사한 물체는 근사적으로 자기 자신의 일부분과 비슷한 모양을 가지는 현상을 의미합니다 (참고). 그래프 생성에 있어서도 자기 유사성을 가지는 그래프는 연결 차수의 분포가 power-law를 따른다라는 연구 결과가 있습니다. 본 논문에서는 부호화된 네트워크를 생성하는데 있어서 어떠한 형태의 자기 유사성을 따르면 좋을지 살펴봅니다.
그림 3에서 첫 번째 그림은 실세계 부호화된 네트워크 중 하나인 Congresss 네트워크를 시각화 한 것으로 파란색 선은 양의 간선 빨간색 선은 음의 간선을 의미합니다. 그림에서 알 수 있다시피 네트워크가 크게 두 개의 그룹으로 클러스터링되는 것을 알 수 있습니다. 즉 각각의 그룹 내에서는 양의 간선이 많고 그룹 간에는 음의 간선이 많은 것을 알 수 있습니다.
이를 추상화한 것이 그림 3의 두 번째 그림입니다. 여기에서 관찰할 수 있는 것은 그림 3의 세 번째 그림 처럼 부분을 확대해도 똑같은 형태 (두 그룹으로 나눠지는 것), 즉 자기 유사한 구조를 가지는 것을 알 수 있습니다. 이를 최종적으로 추상화 하면 그림 3의 마지막 그림과 같이 표현됩니다. 이를 자기 유사한 균형잡힌 구조 (self-similar balanced structure)라고 명명하였습니다.
균형잡힌 네트워크의 가장 큰 특징은 균형잡힌 삼각형이 생기기 쉬운 환경이라는 것입니다. 즉 그룹 내에서는 +++ 삼각형이 그룹 간에는 +-- 삼각형이 생깁니다. 특히 완벽하게 균형잡힌 네트워크 (fully balanced signed network)는 그룹 내에는 음의 간선이, 그룹 간에는 양의 간선이 없기 때문에 균형잡히지 않은 삼각형 (unbalanced triangle)이 생성되지 않습니다. 따라서 최대한 균형잡힌 네트워크의 구조를 유지하면서 부호화된 네트워크를 생성하는 것이 본 논문이 제안하는 핵심 아이디어 입니다.
본 논문에서는 부호화된 네트워크 생성을 위해 자기 유사한 균형잡힌 구조를 시뮬레이션 할 수 있는 모델인 SKSG-B와 개선된 버전인 SKSG를 제안합니다. SKSG-B 모델은 위 그림에서 시작 네트워크 (seed network)를 인접 행렬로 표현하고 이 인접 행렬에 크로네커 곱 (Kronekcer product, 참고)을 계속하여 네트워크의 크기를 배로 늘려 키웁니다. 첫 번째 크로네커 곱을 하면 그림 4의 두 번째 그림 처럼 되고 두 번째 크로네크 곱을 하면 세 번째 그림 처럼 커집니다. 여기서 곱을 해나가도 두 개의 그룹의 형태가 유지됩니다. 이와 같이 SKSG-B는 크로네커 곱을 이용하여 자기 유사성을 띄며 균형잡힌 부호화된 네트워크를 생성하고, 결과적으로 완벽하게 균형잡힌 부호화된 네트워크를 만들어 냅니다 (즉, 그룹 내에는 양의 간선만 그룹 간에는 음의 간선만 존재합니다).
그러나 SKSG-B에 의해 생성되는 완벽하게 균형잡힌 부호화된 네트워크는 실세계 그래프와 다른 양상을 띕니다. 자세한 사항은 논문에서 확인 할 수 있지만 결과적으로 SKSG-B가 생성하는 네트워크와 실세계 그래프는 다음의 차이를 보입니다.
- Title: BalanSiNG: Fast and Scalable Generation of Realistic Signed Networks
- Authors: Jinhong Jung, Ha-Myung Park, and U Kang
- Conference: International Conference on Extending Database Technology (EDBT) 2020
Signed Network and Network Generation
부호화된 네트워크 (signed network)란 정점 간의 신뢰 관계를 + (양, 신뢰) 또는 - (음, 불신뢰)의 부호가 붙은 간선으로 표현하는 네트워크를 말하며, Epinions와 같은 온라인 소셜 서비스는 각 사용자에게 다른 사용자에 대한 신뢰를 표현할 수 있게 하여 자연스럽게 부호화된 네트워크를 형성합니다 (참고). 이와 같이 부호화된 네트워크는 정점 간의 신뢰 관계를 기반으로 링크 예측, 정점 랭킹, 정점 분류, 이상현상 탐지 등의 다양한 그래프 응용에 활용되고 있습니다.
그림 1. 부호화된 네트워크의 예시.
- 확장성 테스트 (scalability evaluation): 확장성 테스트는 개발한 알고리즘이 얼마나 큰 데이터를 처리 할 수 있는지 실험적으로 확인하는 작업으로 생성되는 네트워크의 크기를 점진적으로 늘려 개발한 알고리즘의 수행 시간 변화를 관찰합니다.
- 네트워크 시뮬레이션 (network simulation): 네트워크 시뮬레이션은 네트워크의 특정 특성을 활용하는 모델이 있을 때, 생성되는 네트워크가 해당 특성에 대해 다른 경향을 가지도록 네트워크를 생성한 뒤 제안한 모델의 성능 변화를 관찰하는 작업을 말합니다.
- 데이터 익명화 (data anonymization): 기업과 같은 곳에서 수집한 네트워크를 개인 정보 등의 이유로 공개하지 못하는 경우, 해당 네트워크와 비슷한 특성을 가지되 전혀 다른 네트워크를 생성하여 데이터를 익명화 하는데도 활용할 수 있습니다.
Desired Properties of Signed Networks
그렇다면 부호화된 네트워크를 생성하는데 있어서 어떠한 특성들이 만족되어야 할까요? 이를 위해서 본 절에서는 실세계 부호화된 네트워크들이 가지는 공통적인 특성들을 살펴봅니다. 실세계 부호화된 네트워크는 부호에서 비롯된 독특한 특징들을 가지고 있는 동시에 부호가 없는 네트워크의 구조적 특징도 동시에 가집니다. 아래 그림은 실세계 부호화된 네트워크인 BitcoinA, BitcoinO, Epinions 데이터에 대한 특성들의 경향을 보여줍니다.
그림 2. 실세계 부호화된 네트워크의 여러 특성치.
- 부호의 분포 (sign distribution): 간선이 가지는 부호의 비율을 의미하며 그림 2 (a)와 같이 양의 간선이 음의 간선보다 더 많이 존재합니다.
- 부호화된 삼각형의 분포 (signed triangle distribution): 부호화된 삼각형은 그래프에서 삼각형의 간선에 부호가 있는 것을 의미하며, 실세계 부호화된 네트워크는 그림 2 (b)와 같이 삼각형의 부호가 +++ 또는 +--인 삼각형이 ++- 또는 ---인 삼각형 보다 더 많이 존재합니다. +++ 또는 +--인 삼각형을 균형잡힌 삼각형 (balanced triangle) 라고 부르고 그 외의 삼각형은 균형잡히지 않은 삼각형 (unbalanced triangle)이라고 부릅니다. 균형잡힌 삼각형에 대한 분석 및 관련 이론을 balance theory라고 합니다.
- 양 또는 음의 간선을 대상으로한 연결 차수의 분포 (degree distribution for only + or - edges): 연결 차수는 정점에 연결된 간선의 수를 연결 차수라고 부르며, 특정 연결 차수를 가지는 정점의 수에 대한 분포를 연결 차수의 분포 (degree distribution)라고 합니다. 실세계 부호화된 네트워크에서는 양의 간선으로만 한 네트워크에서의 연결 차수와 음의 간선으로만 한 네트워크에서의 연결 차수가 모두 power-law (참고)를 따릅니다 (그림 2 (c) 와 (d)).
- 부호를 제거한 그래프에서 연결 차수의 분포 (degree distribution): 실세계 부호화된 네트워크에서 부호를 없애고 난 뒤의 연결 차수의 분포 역시 power-law를 따릅니다 (그림 2 (e) 와 (f)).
- 홉 플랏 (hop plot): 홉 플랏은 각 정수 k에 대해 k hop 내에 서로 도달할 수 있는 정점 쌍의 비율을 의미합니다. 홉 플랏은 네트워크 반경 (network diameter)와 긴밀하게 연결되어 있는데 그림 2 (g)를 보면 k가 4-5에서 수렴하는 것을 알 수 있는데 이는 4~5 hop 정도면 임의의 두 정점이 서로 왕래 가능하고, 이러한 거리가 네트워크 반경을 의미합니다. 이와 같이 실세계 그래프는 작은 네트워크 반경을 가집니다.
- 특이값 분포 (singular value distribution): 부호를 제거하고 남은 네트워크의 인접 행렬에 대한 특이값 (singular value)의 분포를 의미 하며 실세계 그래프에서는 그림 2 (h)와 같이 특이값의 분포가 power-law의 형태를 따르게 됩니다.
Proposed Method
본 논문에서는 그림 2와 같은 실세계 그래프의 공통적 특징을 따르는 인공적인 부호화된 네트워크를 생성하는 방법인 BalanSiNG (Balanced Signed Network Generator)를 제안합니다.
본 논문에서의 핵심적인 목표는 실세계 그래프의 고유한 특징들이 잘 드러날 수 있는 부호화된 네트워크를 생성하는 것입니다. 여러 특징들 중에서, 부호화된 삼각형의 분포가 실세계 부호화된 네트워크를 구별 짓는 가장 두드러지는 특징이기 때문에 부호화된 삼각형의 분포를 잘 조절하는 것에 집중했습니다. 그림 2에서 알 수 있다시피 균형잡힌 삼각형이 훨씬 많기 때문에 이러한 네트워크를 균형잡힌 부호화된 네트워크 (balanced signed network)라고 합니다. 이를 위해서 본 논문에서는 균형잡힌 부호화된 네트워크를 생성하기 위해 만족되어야할 자기 유사성 (self-similarity)을 먼저 정의합니다 (자세한 내용은 다음 절에서 설명합니다).
그 후에 자기 유사성을 시뮬레이션하여 완벽하게 균형잡힌 부호화된 네트워크를 생성하는 모델인 Basic Stochastic Kronecker Signed Graph (SKSG-B) 모델을 제안합니다. 그러나 완벽하게 균형잡인 부호화된 네트워크는 실세계 그래프의 부호 분포, 연결 차수 분포, 부호화된 삼각형 분포에 있어서 다른 경향을 가지기 때문에 이러한 분포들을 실세계 네트워크와 유사하게 조정할 수 있는 개선된 버전인 Stochastic Kronecker Signed Graph (SKSG) 모델을 제안합니다. 여기에 SKSG 모델을 잘 따르면서 빠르고 병렬적으로 확장성 있게 부호화된 네트워크를 생성할 수 있는 BalanSiNG을 제안합니다.
본 논문에서의 핵심적인 목표는 실세계 그래프의 고유한 특징들이 잘 드러날 수 있는 부호화된 네트워크를 생성하는 것입니다. 여러 특징들 중에서, 부호화된 삼각형의 분포가 실세계 부호화된 네트워크를 구별 짓는 가장 두드러지는 특징이기 때문에 부호화된 삼각형의 분포를 잘 조절하는 것에 집중했습니다. 그림 2에서 알 수 있다시피 균형잡힌 삼각형이 훨씬 많기 때문에 이러한 네트워크를 균형잡힌 부호화된 네트워크 (balanced signed network)라고 합니다. 이를 위해서 본 논문에서는 균형잡힌 부호화된 네트워크를 생성하기 위해 만족되어야할 자기 유사성 (self-similarity)을 먼저 정의합니다 (자세한 내용은 다음 절에서 설명합니다).
그 후에 자기 유사성을 시뮬레이션하여 완벽하게 균형잡힌 부호화된 네트워크를 생성하는 모델인 Basic Stochastic Kronecker Signed Graph (SKSG-B) 모델을 제안합니다. 그러나 완벽하게 균형잡인 부호화된 네트워크는 실세계 그래프의 부호 분포, 연결 차수 분포, 부호화된 삼각형 분포에 있어서 다른 경향을 가지기 때문에 이러한 분포들을 실세계 네트워크와 유사하게 조정할 수 있는 개선된 버전인 Stochastic Kronecker Signed Graph (SKSG) 모델을 제안합니다. 여기에 SKSG 모델을 잘 따르면서 빠르고 병렬적으로 확장성 있게 부호화된 네트워크를 생성할 수 있는 BalanSiNG을 제안합니다.
Self-Similarity for Signed Networks
그림 3. 부호화된 네트워크 생성을 위한 자기 유사성. 파란선은 양의 간선이고 빨간선은 음의 간선을 의미.그림 3에서 첫 번째 그림은 실세계 부호화된 네트워크 중 하나인 Congresss 네트워크를 시각화 한 것으로 파란색 선은 양의 간선 빨간색 선은 음의 간선을 의미합니다. 그림에서 알 수 있다시피 네트워크가 크게 두 개의 그룹으로 클러스터링되는 것을 알 수 있습니다. 즉 각각의 그룹 내에서는 양의 간선이 많고 그룹 간에는 음의 간선이 많은 것을 알 수 있습니다.
이를 추상화한 것이 그림 3의 두 번째 그림입니다. 여기에서 관찰할 수 있는 것은 그림 3의 세 번째 그림 처럼 부분을 확대해도 똑같은 형태 (두 그룹으로 나눠지는 것), 즉 자기 유사한 구조를 가지는 것을 알 수 있습니다. 이를 최종적으로 추상화 하면 그림 3의 마지막 그림과 같이 표현됩니다. 이를 자기 유사한 균형잡힌 구조 (self-similar balanced structure)라고 명명하였습니다.
균형잡힌 네트워크의 가장 큰 특징은 균형잡힌 삼각형이 생기기 쉬운 환경이라는 것입니다. 즉 그룹 내에서는 +++ 삼각형이 그룹 간에는 +-- 삼각형이 생깁니다. 특히 완벽하게 균형잡힌 네트워크 (fully balanced signed network)는 그룹 내에는 음의 간선이, 그룹 간에는 양의 간선이 없기 때문에 균형잡히지 않은 삼각형 (unbalanced triangle)이 생성되지 않습니다. 따라서 최대한 균형잡힌 네트워크의 구조를 유지하면서 부호화된 네트워크를 생성하는 것이 본 논문이 제안하는 핵심 아이디어 입니다.
Stochastic Kronecker Signed Graph (SKSG) Models and BalanSiNG
그림 4. SKSG-B 모델이 self-similar balanced structure를 시뮬레이션 하는 과정.
그러나 SKSG-B에 의해 생성되는 완벽하게 균형잡힌 부호화된 네트워크는 실세계 그래프와 다른 양상을 띕니다. 자세한 사항은 논문에서 확인 할 수 있지만 결과적으로 SKSG-B가 생성하는 네트워크와 실세계 그래프는 다음의 차이를 보입니다.
- 부호의 비율: SKSG-B는 양/음의 간선의 비율이 거의 동치이지만 실세계 그래프는 양의 간선이 훨씬 많습니다.
- 균형잡힌 삼각형의 비율: SKSG-B는 오로지 균형잡힌 삼각형 (balanced triangle)만 생성하지만 실세계 그래프에는 균형잡히지 않은 삼각형 (unbalanced triangle)도 일정 부분 존재합니다.
- 연결 차수 분포: 실세계 그래프는 power-law를 따르지만 SKSG-B에 의해 생성된 네트워크의 연결 차수 분포는 위아래로 요동치는 (fluctuating) 형태를 따릅니다.
BalanSiNG은 SKSG 모델을 정확하게 따르면서 부호화된 네트워크를 빠르게 생성할 수 있도록 설계 되었습니다. 핵심적인 아이디어는 SKSG는 생성해야할 네트워크의 인접 행렬을 모두 구축해야 하기 때문에 n을 정점의 수라고 하면 n 제곱의 계산량이 요구되어 확장성에 제약이 있는데, BalanSiNG은 인접 행렬을 명시적으로 구하는 것이 아니라 간선 하나를 생성할 때 꼭 필요한 연산만을 수행해 전체 인접 행렬을 구하지 않고도 필요한 간선들을 만들어 낼 수 있습니다. 하나의 간선을 만드는데 있어서 다른 간선의 생성과 독립적이기 때문에 간선을 독립적으로 생성할 수 있고, 이는 BalanSiNG이 병렬적으로 작동하여 부호화된 네트워크를 생성할 수 있음을 의미합니다. 제안 모델 및 기법에 대한 자세한 설명과 수식적 유도 및 증명은 논문을 통해 확인하실 수 있습니다.
Experimental Results
본 절에서는 제안 방법인 BalanSiNG에 대한 주요 실험 결과를 보여 줍니다. 첫 번째는 BalanSiNG 및 다른 경쟁 방법이 생성한 부호화된 네트워크의 특성들이 실제 부호화된 네트워크의 특성들과 얼마나 유사한지를 살펴봅니다. 두 번째는 BalanSiNG의 계산 성능을 다른 경쟁 방법과 비교합니다.
Properties of Generated Signed Networks
그림 5. 제안 방법인 BalanSiNG과 다른 경쟁 기법으로 생성한 부호화된 네트워크의 특성치 비교. BitcoinO는 실세계 부호화된 네트워크의 특성치를 의미하고 빨간 박스로 쳐진 플랏들은 해당 특성이 실세계 그래프와 많이 맞지 않는 것을 의미.
그림 5는 실세계 부호화된 네트워크인 BitcoinO와 해당 그래프와 같은 정점 및 간선 수를 가지도록 생성된 인공적인 부호화된 네트워크의 특성치를 보여줍니다. 각 기법을 이용해서 네트워크를 생성할 때 간선의 부호 분포 (그림 5 (a))를 실세계 그래프와 같게 맞추어 네트워크를 생성하였습니다. 결과를 보면 제안 방법인 BalanSiNG이 생성한 네트워크가 다른 방법으로 생성한 네트워크보다 균형잡힌 삼각형의 분포, 연결 차수 분포, 홉 플랏, 특이값 분포등이 실세계 네트워크와 유사한 것을 알 수 있습니다. 특히 경쟁 기법인 IB와 Evo의 연결 차수는 power-law를 따르지 않는데 이는 생성된 네트워크의 구조가 실세계 네트워크의 구조와 많이 다른 것을 의미 합니다. 이와 같이 제안 방법인 BalanSiNG는 사실적인 부호화된 네트워크를 생성하는 것을 알 수 있습니다. 다른 실세계 부호화된 네트워크에 대해서도 아래와 비슷한 결과를 보여줍니다.
Computational Performance
Computational Performance
그림 6. 제안 방법인 BalanSiNG의 계산 성능.
그림 6은 제안 방법인 BalanSiNG과 다른 경쟁 방법들의 계산 성능을 비교합니다. 먼저 다른 경쟁 기법들은 단일 머신에서만 동작하기 때문에 단일 머신 상에서의 비교를 합니다. 특히 BSCL은 고정된 정점 및 간선 수에 대해서만 네트워크를 생성하기 때문에 이 환경에 맞추어 다른 방법과 비교를 합니다. 단일 머신에서 수행되는 기법은 모두 C++로 구현하였습니다. 그림 6 (a)를 보면 다른 경쟁 기법 대비 최대 265배 빠르게 부호화된 네트워크를 생성하는 것을 알 수 있습니다.
그림 6 (b)는 임의의 간선 수가 주어졌을 때 부호화된 네트워크를 생성하는 시간을 비교합니다. 그림 6 (b)에 따르면 생성해야 하는 간선 수가 늘어남에 따라 제안 방법인 BalanSiNG은 거의 선형적으로 실행 시간이 늘어나는 것을 알 수가 있습니다. 또한 IB와 Evo와 비교를 해보았을 때 굉장히 빠르게 부호화된 네트워크를 생성한다는 것을 알 수가 있습니다.
제안하는 방법인 BalanSiNG은 또한 병렬적으로 수행될 수 있기 때문에 분산 환경 상에서의 계산 확장성을 실험합니다. 분산 시스템에서 동작되는 BalanSiNG은 Apache Spark을 이용하여 구현하였습니다. 그림 6 (c)는 생성되어야 하는 간선의 수 대비 실행 시간이 선형적으로 증가하는 것을 보이고 있고, 최종적으로 68.7 billion 개의 간선을 생성하였습니다. 그림 6 (d)는 동시에 수행되는 워커 (worker)의 수의 증가 대비 실행시간이 선형적으로 감소하는 것을 보이고 있습니다. 결과에 대한 자세한 추가 설명은 논문을 참고하면 됩니다.
Conclusion
본 문서에서는 EDBT 2020에 발표될 예정인 "BalanSiNG: Fast and Scalable Generation of Realistic Signed Networks" 논문을 소개하였습니다. 해당 논문은 실세계 부호화된 네트워크의 공통된 특징들을 잘 보여주는 새로운 형태의 다른 부호화된 네트워크를 생성할 수 있는 기법인 BalanSiNG 기법을 제안하였고, 병렬 처리를 위한 BalanSiNG은 Apache Spark을 이용하여 구현하였습니다. 실험을 통해 제안한 기법이 다른 경쟁 기법들 보다 더 사실적인 부호화된 네트워크를 매우 빠르고 확장성 있게 생성하는 것을 검증하였습니다. 논문에 대한 상세 정보는 (링크)를 통해 확인할 수 있습니다.