커뮤니티 (상호 연결된 노드)와 다른 점 간의 거리를 계산하기위한 효율적인 알고리즘

Question

공간 도메인 (구조와 같이 밀도가 높은 커뮤니티)과 쿼리 포인트에 그래프 구조가 있습니다. 이 그룹 전체와 쿼리 포인트 사이의 거리를 계산하기 위해 효율적인 알고리즘 + 데이터 구조를 고안하고 싶습니다.

여기서 적절한 거리 함수는 쿼리 포인트로부터 모든 점의 거리를 평균화 할 수 있습니다. 다른 기능이 모든 거리의 최대 값을 차지할 수 있습니다.

이 문제는 어떻게 해결해야합니까?

Answer 1

공간적 거리 : 중심점과 달리 거리 - 평균 거리를 제안하는 것은 쿼리 포인트에서 커뮤니티의 각 포인트까지의 거리의 함수라는 점에서 두 제안의 정신에 달려 있습니다. . 변수 X와 Y에서 각 점 (x, y)에 대한 거리 제곱 다항식 (X - x)^2 + (Y - y)^2를 합하여 커뮤니티를 사전 처리합니다. 그런 다음 쿼리를 연결하여 RMS 거리를 계산합니다 커뮤니티 포인트의 수로 나누고 제곱근을 취합니다.