그래프에는 비교적 적은 수의 가장자리로만 서로 상대적으로 조밀하게 연결된 구성 요소가 두 개 있다고 가정 해보십시오. 구성 요소는 어떻게 식별 할 수 있습니까? 나는 적절한 용어를 모르고 있지만 직관적으로는 상대적으로 조밀하게 연결된 서브 그래프가 몇 개의 스레드에 의해 다른 서브 그래프에 매달려 있다는 것입니다. 그래프의 나머지 부분과 느슨하게 연결된 이러한 덩어리를 확인하고 싶습니다.그래프의 느슨하게 연결된 구성 요소를 식별하는 방법
대답은 다소 일반적 일 수 있지만 문제를 유동 문제로 모델링하고 최소 절단을 생성 할 수 있습니다. here을 참조하십시오. 가장자리는 용량이 1 인 양방향 일 수 있으며 그 결과 잘라내어 원하는 파티션을 얻을 수 있습니까?
아마도 min cut 대신 sparsest cut을 원할 것입니다. 컴포넌트에서 여러 노드를 식별 할 수 없으면 min cut은 각도가 작을 때 매우 불균형하게되는 경향이 있습니다. 가장 희소 한 절단에 대한 일반적인 접근 방법 중 하나는 그래프의 라플라시안 (Laplacian)의 고유 벡터를 계산하고 임계 값을 계산하는 것입니다.
그래프가 실제 시스템을 나타내면이 작업을 커뮤니티 검색이라고합니다. Fortunato's review (2010)으로 시작하는 많은 기사를 찾을 수 있습니다. 그는 다른 것들 중에서, 이전 답변에서 언급 된 분 - 컷 기반 방법을 설명합니다.
이있어 또한 다음과 같은 SO에 많은 게시물 : 크로스 인증 됨에서
사람들은 또한 지역 사회의 감지에 대해 이야기 :
마지막으로,보다 직접적으로이 문제와 관련 될 새로운 Network Science 사이트 51 구역의 제안은있다.
Tim Roughgarden의 [최소 삭감 강의] (https://www.youtube.com/watch?v=Zfc1iUQGy48 & list = PLLH73N9cB21W1TZ6zz1dLkyIm50HylGyg)는 좋은 소개가 될 것입니다. –