Key points are not available for this paper at this time.
이 논문은 두 개의 상관 랜덤 그래프 사이의 숨겨진 정점 대응을 회복하는 문제를 연구한다. 우리는 특정 개수를 가진 유도 부분 그래프 쌍이 상관되어 있는 부분 상관 에르되시-레니 그래프 모델을 제안한다. 우리는 잠재적으로 상관된 부분 그래프와 숨겨진 정점 대응을 회복하기 위한 정보 이론적 임계값을 조사한다. 상관된 노드 수에 대한 부분 회복을 위한 최적 비율이 존재함을 증명하며, 이 비율 이상의 경우 일부 정점을 올바르게 매치할 수 있고, 이 비율 이하에서는 어떤 양의 비율도 올바르게 매치할 수 없음을 입증하고, 정확한 회복을 위한 최적 비율도 도출한다. 가능성 결과의 증명에서는 상관 함수 다이어그램을 제안하여 교차 그래프의 엣지를 두 유형의 구성 요소로 나누고, 오류 확률을 더 낮은 차수의 누적 생성 함수로 제한한다. 불가능성 결과의 증명은 일반화된 파노 부등식과 상관된 에르되시-레니 그래프 모델에서 정한 회복 임계값을 기반으로 한다.
Huang et al. (Sat,)은 이 문제를 연구했다.