결함 클리크 기반 조합탐색 및 그래프 마이닝

Defective Clique–Driven Combinatorial Search for Graph Mining

연구 내용

결함 클리크를 열거·탐색하기 위한 worst-case 최적 검색 공간과 분기한정 알고리즘을 구성하는 연구

본 연구는 전통적 클리크 정의를 완화한 k-defective clique를 대상으로, 최대 결함 클리크 열거와 탐색 문제를 효율적으로 다룹니다. 기존 접근에서 발생하는 작은 부분해의 조합 폭발과 비효율적 검색 공간을 줄이기 위해 clique-first branch-and-bound 프레임워크를 제안합니다. 또한 피벗팅 기법을 도입하여 탐색 공간의 크기를 worst-case 관점에서 최적에 가깝게 설계하며, defective cliques의 diameter-two 성질을 활용해 검색 공간을 추가로 축소합니다. 최대 k-defective clique 탐색을 위한 확장 프레임워크와 함께 실용적 가지치기 전략을 제시하여 대규모 그래프에서 처리 시간을 개선합니다.

관련 프로젝트

0건

연구 흐름

초기에는 결함 클리크 완화가 실제 네트워크에서의 누락 간선을 다루는 데 유리하다는 문제정의를 바탕으로, 열거와 최대 탐색의 계산 복잡도가 병목이 됨을 분석했습니다. 이후 clique-first 분기한정 구조로 먼저 결합 후보를 구성하고 이후 누락 간선을 보완하는 방식으로 탐색 단계의 구조를 재정렬했습니다. 다음 단계에서 worst-case 크기를 직접 제어하는 피벗팅 기법을 도입하여 검색 공간의 상한을 체계적으로 낮추었습니다. 마지막으로 degeneracy 및 defective clique의 기하적 성질을 활용해 diameter-two 기반 축소를 적용하고, 대규모 벤치마크에서 실험적 검증과 실용 테크닉을 결합하는 흐름으로 이어졌습니다.

활용 가능성

활용 가능성은 알앤디써클 특화 AI 에이전트가 생성한 내용으로, 실제 연구 가능 여부는 연구실과의 논의가 필요합니다.

결함 클리크 기반 링크 추정
커뮤니티 탐지
대규모 그래프 질의 최적화
그래프 요약 및 특징 추출
그래프 기반 추천 신호
네트워크 이상탐지
조합 최적화 문제 해결
확장 가능한 검색 공간 설계
그래프 데이터 마이닝
대규모 그래프 엔진 검증