1. 초록 (Abstract)
본 보고서는 시간적 그래프(Temporal Graph) 환경에서 두 개체 간의 상호작용을 분석하기 위한 핵심 구조인 '시간적 단순 경로 그래프(Temporal Simple Path Graph, tspG)' 생성 문제에 대한 심층적인 분석을 제공한다. 본 연구는 계산적 병목을 해결하기 위해 상한 그래프 내 검증(VUG) 프레임워크를 제안한다.
2. 서론 (Introduction)
현실 세계의 개체 간 관계는 특정 타임스탬프를 수반하며, 기존의 경로 열거 방식은 $O(d^\theta \cdot \theta \cdot m)$의 지수적 시간 복잡도를 야기한다. 본 연구는 이를 혁신적으로 개선하는 VUG 알고리즘을 제안하여, 질병 통제, 금융 모니터링 등 시공간적 인과관계 추론의 도구를 제공한다.
3. 연구 방법론 (Methodology)
3.1. 빠른 상한 그래프 생성 (QuickUBG)
극성 시간(Polarity Time) 개념을 도입하여 BFS 기반으로 유효하지 않은 간선을 $O(n+m)$ 내에 제거.
3.2. 엄밀한 상한 그래프 생성 (TightUBG)
'시간 스트림 공통 정점(TCV)'을 활용하여 사이클을 유발하는 간선을 재귀적으로 가지치기 수행.
4. 분석 및 결과 (Results)
| 지표 | 성능 결과 |
|---|---|
| 시간 효율성 | 최소 100배 이상 단축 |
| 상한 그래프 품질 | 90% 이상 일치율 |
| 공간 효율성 | O(n+m) 복잡도 유지 |
5. 결론 (Conclusion)
본 연구는 시간적 단순 경로 그래프($tspG$) 생성의 난제를 VUG 프레임워크를 통해 해결하였다. 이 연구는 동적 네트워크 아키텍처 분석의 중요한 토대가 될 것이다.