그래프 라이브러리 부스트 라이브러리 : 커뮤니티 탐지를 위해 BGL에 내장 된 깔끔한 알고리즘이 있습니까?

Question

대형 생산 서버에 BGL을 사용하는 사람이 있습니까?

• 네트워크는 몇 개의 노드로 구성됩니까?
• 어떻게 처리합니까? 커뮤니티 탐지
• BGL은 커뮤니티를 감지 할 수있는 멋진 방법이 있습니까?
• 때로는 두 커뮤니티가 하나 또는 두 개의 가장자리로 함께 연결될 수 있지만,이 가장자리는 신뢰할 수 없으며 사라질 수 있습니다. 때로는 가장자리가 전혀 없습니다.

누군가이 문제를 해결하는 방법에 대해 간단히 말할 수 있습니까? 내 마음을 열고 영감을주십시오.

지금까지 나는 두 개의 노드가 섬에 (커뮤니티에서) 가장 비싼 방식으로 운동을했지만 이제는 별도의 섬의 두 노드가 서로 가장 가까운 곳에서 해결해야합니다. 우리는 신뢰할 수없는 지리적 데이터를 최소화 할 수 있습니다.

우리가 비 유적으로 본토와 섬과 비교하고 사회적 거리의 맥락에서 벗어나면. 나는 물 한 몸에 가장 가까운 두 비트의 땅이 가장 가까운 곳에서 운동하고 싶습니다.

Answer 1

수백만 개의 노드가있는 그래프에 BGL을 사용했지만 사용할 수있는 그래프의 크기는 실행하려는 알고리즘에 따라 다릅니다. 노드 사이의 거리를 신속하게 계산할 수 있습니다. 데이터에 따라 가장 적용 가능한 4 개의 가장 짧은 경로 알고리즘이 있습니다.

커뮤니티 탐지와 관련하여 BGL을 구체적으로 내장 된 알고리즘은 없습니다 (그러나 프로젝트를 마치면 기여할 수 있습니다). 커뮤니티 감지 알고리즘을 구축하는 데 도움이 될 수있는 몇 가지 알고리즘이 있습니다. 그만큼 최대 플로우/미트 알고리즘은 일반적으로 커뮤니티 탐지에 사용됩니다 (두 노드 사이에 흐름이 많이있는 경우 동일한 커뮤니티에있을 가능성이 높으면 흐름이 많지 않으면 Min-Cut은 도로를 나타낼 수 있습니다. 커뮤니티). 또한 그래프 노드를 주문하기위한 휴리스틱도 있습니다. 대역폭. "커뮤니티"를 구성하는 노드는 그러한 순서에서 서로 가까이있을 가능성이 높습니다.

Answer 2

내가 아는 한 BGL에는 커뮤니티 탐지를위한 알고리즘이 없습니다.

"Island"에 의해 연결이 끊어진 서브 그래프를 의미합니까?

또한 그래프에는 '거리'라는 개념이 없습니다.

이 '사회적 거리'는 당신이 정의해야 할 것입니다. 일을 마치면 작업의 많은 부분이 완료됩니다.

링크 된 페이지에 나열된 수많은 방법이 있습니다. 대부분의 사람들은 '거리'메트릭과 같은 것을 정의한 다음 정의를 알고리즘에 연결하면됩니다.

@ David Nehme

가장자리 체중이없는 그래프는 연결성에 관한 것이며 거리의 개념이 없습니다. 네트워크에 대해 이야기하고 싶다면 거리에 대해 이야기 할 수 있습니다. 그러나 가장자리가없는 그래프는 모든 모서리에 대해 묵시적 가장자리 체중 1을 가정하지 않는 한 거리가 없습니다. 그러나 이것은 실제로 그래프를 네트워크로 전환하는 것입니다.

또한 그는 연결이 끊어진 두 개의 그래프 사이의 거리에 대해 이야기하고 있습니다. 이를 모델링하려면 노드 사이의 거리에 대한 외부 개념을 가장자리 거리와 별도로 소개해야합니다.