대형 그래프에 대한 BFS와 인덱싱 간의 격차 해소

:::정보
저자:

(1) 바르일란 대학교 Talya Eden([email protected]);

(2) MIT의 Omri Ben-Eliezer([email protected]);

(3) C. Seshadhri, UC Santa Cruz ([email protected]).

:::

링크 표

초록 및 1. 서론

1.1 우리의 기여

1.2 설정

1.3 알고리즘

관련 업무
연산

3.1 구조적 분해 단계

3.2 라우팅 단계

3.3 웜홀의 변종
이론적 분석

4.1 예선

4.2 내부 링의 부선형성

4.3 근사 오류

4.4 쿼리 복잡성
실험 결과

5.1 WormHole𝐸, WormHole𝐻 및 BiBFS

5.2 인덱스 기반 방법과의 비교

5.3 원시적인 WormHole: WormHole𝑀

참고자료

추상적인

대규모 실제 네트워크에서 거리를 계산하고 최단 경로를 찾는 것은 네트워크 분석의 기본 알고리즘 작업입니다. 이 작업을 해결하는 데는 두 가지 주요 접근 방식이 있습니다. 한편으로는 전처리 단계가 없지만 개별 거리 조회 속도가 느린 BiBFS(양방향 너비 우선 검색)와 같은 순회 기반 알고리즘이 있습니다. 반면에 대규모 인덱스를 생성하고 유지 관리하는 인덱싱 기반 접근 방식이 있습니다. 이를 통해 개별 문의에 매우 빠르게 답변할 수 있습니다. 그러나 인덱스 생성은 중간 규모 네트워크의 경우에도 엄청나게 비용이 많이 듭니다. 3천만 개의 간선이 있는 그래프의 경우 최첨단 기술로 생성된 인덱스는 약 40GB입니다. 우리는 비용이 많이 드는 전처리 없이 거리 문의에 신속하게 응답하는 두 가지 극단을 연결하고자 합니다.

\ WormHole은 기존 방법에 비해 몇 가지 추가 이점을 제공합니다. (i) 전체 그래프를 읽을 필요가 없으므로 그래프에 대한 액세스가 속도 제한되는 설정에서 사용할 수 있습니다. (ii) 대부분의 인덱스 기반 알고리즘과 달리 거리뿐만 아니라 경로도 반환합니다. (iii) 더 빠른 조회 시간을 위해 하위 선형 코어에서만 실행함으로써 다른 인덱스 기반 솔루션과 효과적으로 결합할 수 있습니다.

1 소개

대규모 네트워크에서 확장 가능한 거리 및 최단 경로 계산은 과학 및 엔지니어링 전반에 걸쳐 적용되는 그래프 마이닝 및 그래프 학습 작업에서 가장 기본적인 알고리즘 과제 중 하나입니다. 이러한 응용 프로그램의 예로는 생물학적 및 생태학적 네트워크에서 중요한 유전자 또는 종의 식별이 포함됩니다. [18]도로망의 운전 방향 [1–3]모바일 장치에서 클라우드로 작업 처리 재분배 [59]컴퓨터 네트워크 설계 및 보안 [24, 30, 31, 58]소셜 네트워크에서 최대 영향력을 가진 사용자 집합을 식별합니다. [32, 56]다른 많은 것 중에서. 그래서 긴 작업줄 [5, 21, 25, 28, 62] 다양한 실제 작업을 위한 거리 계산을 위한 확장 가능한 알고리즘을 구축하면서 수년에 걸쳐 개발되었습니다.

\ 최단 경로 조회(𝑠,𝑡)에 응답하는 가장 간단한 방법은 순회를 사용하며, 그 중 가장 기본적인 방법은 𝑠에서 시작하여 𝑡에 도달할 때까지 너비 우선 검색(BFS)입니다. 그러나 BFS에 대한 조회 시간은 네트워크 크기에 대해 선형적이므로 실제 네트워크에 비해 너무 느립니다.1 널리 사용되는 수정인 양방향 BFS(BiBFS)는 양쪽 끝이 만날 때까지 양쪽𝑠 및 𝑡에서 BFS를 교대로 실행합니다. BiBFS가 광범위한 네트워크에서 최단 경로 조회에 대해 놀라울 정도로 잘 수행된다는 것이 문헌에서 잘 관찰되었습니다(예: [8, 12, 62] 그리고 그 안에 많은 참고자료가 있습니다). BiBFS는 네트워크 구조에 대한 사전 지식이 필요하지 않기 때문에 최단 경로 조회 수가 상대적으로 적을 때 적합합니다. 그러나 순수 순회 기반 접근 방식은 다수의 최단 쌍 문의에 응답해야 하는 경우에는 잘 확장되지 않습니다. 그림 1에서 볼 수 있듯이 BiBFS는 단 몇 백 번의 쿼리 내에 전체 그래프를 보게 됩니다.

현대적인 접근 방식을 따라 네트워크를 전처리하고 인덱스를 생성함으로써 근본적으로 다른 방식으로 거리 계산 문제를 해결합니다. 인덱스는 매우 빠른 실시간 거리 계산을 지원합니다. 이 작업 계열은 Pruned Landmark Labeling(PLL, Akiba et al. [5]) 아마도 가장 영향력 있는 접근 방식일 것입니다.

\ 사실상 모든 인덱스 기반 방법에서 사전 처리에는 랜드마크라고 불리는 노드의 하위 집합 L을 선택하는 작업이 포함됩니다. 그들 사이의 모든 최단 경로를 계산합니다. 네트워크의 모든 노드와 모든 랜드마크의 거리 지수를 유지합니다. 따라서 인덱스에 필요한 공간은 최소한 𝑛· |L| 차수입니다. 여기서 𝑛는 총 노드 수입니다. 순진하게도 이 메모리 요구 사항은 𝑛의 2차만큼 나쁠 수 있습니다. 2차 설치 공간을 극복하기 위한 몇 가지 개선에도 불구하고 기존 허브는

\ 및 랜드마크 기반 접근 방식은 계속해서 비용이 높으며 적당한 크기의 그래프에도 실행 불가능할 수 있습니다. [40].

\ 특히 대부분의 인덱스 기반 접근 방식은 경로 자체가 아니라 그래프에 거리만 반환합니다. 최단 경로를 출력하는 솔루션에 대한 최초의 구체적이고 체계적인 조사는 Zhang et al.에 의해 이루어졌습니다. [62]. 그들의 작업은 기존 인덱스 기반 솔루션이 최단 경로를 출력하도록 조정될 수 있지만 이러한 조정은 거리 계산에 필요한 것 외에도 매우 높은 추가 공간 비용을 초래한다는 점을 지적합니다. 저자 [62] 그런 다음 지수 구축 공간 비용을 절약하기 위해 MLL(단조적 랜드마크 라벨링)이라는 새로운 접근 방식을 제안했습니다. 그들의 알고리즘은 이 문제에 대한 최신 기술이지만 역시 인덱스 기반이므로 전처리 비용이 여전히 다소 비쌉니다. 건설 단계의 계산 복잡성을 개선하는 것은 여전히 근본적인 과제로 남아 있습니다.

\ 계산상의 제약을 넘어서 전체 네트워크에 대한 액세스를 가정하는 것은 때로는 단순히 비현실적입니다. 제한된 쿼리 액세스를 통해서만 액세스가 제공되는 시나리오의 예로는 외부 API를 통한 소셜 네트워크 분석 등이 있습니다. [10]웹 그래프의 페이지 다운로드 [14]기업 보안의 최신 경량 모니터링 솔루션 [26, 60]소프트웨어 테스팅, 강화 학습 및 로봇 공학의 상태 공간 탐색 [27]다른 많은 것 중에서. 기존 인덱싱 기반 접근 방식은 전제 조건으로 전체 그래프를 읽어야 하기 때문에 이러한 시나리오에 적합하지 않습니다. BiBFS와 같은 순회 기반 방법이 적합하지만 앞서 언급한 것처럼 다중 거리 계산이 필요한 경우 확장이 잘 되지 않습니다.

\ 인덱싱 기반 및 순회 기반 방법의 한계로 인해 인덱스 기반 접근 방식보다 전처리가 더 효율적이고 순회 기반 접근 방식보다 빠른 조회 시간을 갖는 중간 솔루션이 있는지에 대한 자연스러운 질문이 발생합니다. 즉, 우리는 이렇게 묻습니다.

\
값비싼 인덱스를 구축하거나 전체 그래프를 보지 않고도 대규모 네트워크에서 최단 경로 문의에 매우 빠르게 응답할 수 있습니까?

\ 임의의 그래프에 대한 일반적인 솔루션은 아마도 불가능할 것입니다. 그러나 실제 사회 및 정보 네트워크에서는 악용될 수 있는 질서와 구조가 허용됩니다. 이 연구에서 우리는 그러한 네트워크에서 최단 경로 문제의 약간 완화된 버전에 대해 이 질문을 긍정적으로 해결합니다. 대규모 네트워크의 핵심-주변 구조에서 영감을 얻었습니다. [43, 50, 52, 63]우리는 하위 선형 크기의 인덱스를 구성하고 엄격한 하위 선형 정점 하위 집합을 쿼리하여 문의에 응답하는 솔루션을 제공합니다. 특히 우리 솔루션은 전체 네트워크에 접속할 필요가 없습니다. 알고리즘은 근사치 오류가 추가되고 매우 작은(거의 항상 0 또는 1) 근사 최단 경로를 반환합니다. 실제로 설정 시간은 무시할 수 있으며(10억 개의 에지 그래프의 경우 몇 분) 조회 시간은 BiBFS보다 향상됩니다. 또한 기존 인덱스 기반 솔루션과 쉽게 결합하여 조회 시간을 더욱 향상시킬 수 있습니다. 우리는 또한 경험적 성과를 밝히는 이론적 결과를 포함합니다.

:::info 이 논문은 arxiv에서 사용 가능 CC BY 4.0 라이센스에 따라.

:::

[1] 혼란을 피하기 위해 이 문서 전체에서 조회라는 용어를 사용하여 𝑠과 𝑡 사이의 짧은 경로 SP(𝑠,𝑡)를 계산하기 위한 요청(데이터 구조에 대한 실시간 입력으로 도착)을 나타냅니다. 쿼리라는 용어는 알고리즘 자체에서 수행되는 특정 노드에 대한 정보를 검색하는 행위를 나타냅니다. 우리가 고려하는 쿼리 모델에 대한 자세한 내용은 §1.2를 참조하세요.)

출처 참조