초록
링크 예측은 추천 시스템, 커뮤니티 탐지, 위조 연결 식별 등 다양한 응용 분야를 포함하는 그래프 이론의 핵심 문제이다. 특성 기반 방법은 높은 정확도를 달성하지만, 노드 속성에 의존하기 때문에 특성 없는 그래프에 적용하기에 한계가 있다. 이러한 그래프에 대해서는 공통 이웃 기반 및 차수에 의존하는 구조 기반 접근법이 일반적으로 사용된다. 그러나 이러한 방법의 효과성은 그래프의 밀도에 따라 달라지며, 공통 이웃 기반 알고리즘은 밀도가 높은 그래프에서 우수한 성능을 보이고, 차수에 의존하는 방법은 희박하거나 트리 구조에 가까운 그래프에 더 적합하다. 그럼에도 불구하고, 기존 문헌에서는 밀도가 높은 그래프와 희박한 그래프를 구분할 명확한 기준이 부족하다. 본 논문에서는 그래프 밀도 평가를 위한 기준으로 평균 클러스터링 계수를 제안하여 링크 예측 알고리즘 선택을 지원한다. 실증 분석을 위한 데이터셋 부족 문제를 해결하기 위해, 구조적 이질성을 유지하면서 그래프 밀도를 제어 가능한 방식으로 조절할 수 있는 새로운 그래프 생성 방법을 제안한다. 이는 바라바시-알버트 모델을 기반으로 한다. 합성 및 실세계 데이터셋을 대상으로 한 종합적인 실험을 통해 평균 클러스터링 계수에 대한 경험적 경계를 설정하였으며, 이는 효과적인 링크 예측 기법 선택을 가능하게 한다.