무작위 가중 하위 그래프

Question

나는 에 대해 here으로 보는 것과 같은 교차 언어 의미 론적지도로 작업하고 있습니다.

이 그래프를 취하여 가중치가 링크 가중치로 결정되는 가중치 임의 그래프를 n 개까지 추출 할 수 있기를 원합니다. 즉, 더 높은 가중치로 연결된 노드는 임의의 하위 그래프에 대해 우선적으로 선택됩니다. 내가 헛된, 주로 소프트웨어와 특정 서브 그래프 속성과 완전 무작위 그래프를 만드는 신문을 받고 봤어. networkx에 대한 설명서에 응시

는 가능성이 도움이 나를 파업 아무것도 굴복하지 않은,하지만 불행히도 나는이 분야에서 물장난 해요 및 용어 무지을 통해 뭔가를 누락 될 수 있습니다.

이 항목을 찾을 수있는 정확한 용어에 대한 제안 사항이나이 태스크를 수행 할 수있는 도구 (다른 프로그래밍 언어의 경우에도 있음)에 대한 포인터를 찾고 있습니다.

Answer 1

다음은 알고리즘의 대략적인 스케치입니다.

1. 그래프를 거리 매트릭스로 변환하십시오.
2. 바닐라 파이썬 random 기능을 사용하여 임의로 셀 (v_0)을 선택하십시오.
3. 그래프가 무향이라고 가정하면 v_0을 포함하는 열이나 행을 가져옵니다 (대칭이므로 동일합니다).
4. weighted choice function을 사용하면 해당 행에서 처음 정점에서 멀리 떨어져있는 정점을 잡을 수 있습니다. 체중이 꼭지점 사이의 거리이기 때문에 연결된 단편에서 weighted_pick에 행을 입력하는 것일뿐입니다 (picks = 1). 이 정점을 v_1으로합시다.
5. v_0이 포함 된 행이 0이 아니므로 다시 선택되지 않습니다.
6. m/n 번을 반복하여 새 시작점으로 v_1을 사용하여 다음 반복을 시작합니다. 선택한 정점을 하위 그래프에 저장하십시오.
7. 하위 그래프의 전체 목록을 얻으려면 전체 프로세스 n 번을 반복하십시오.

무거운 가장자리가 아닌 긴 경로를 선택했기 때문에 이것은 사용자가 요구 한 것이 아닙니다. 그러나 쉽게 수정할 수 있습니다. v_1과 v_2 사이에 모서리가 없으면 d(v_1, v_2) = 0과 같이 거리 매트릭스를 조정할 수 있습니다. 그러면 연결된 부분 그래프 만 표시됩니다. 이는 원하는 것처럼 보입니다.

이 시간은 O(|V|) * t 시간으로 실행해야합니다. 여기서 t은 가중치 적용 함수의 시간 복잡도입니다. 불행하게도 numpy은 searchsorted의 시간 복잡도를 말하지 않지만 정렬 목록에 삽입을 수행하고 있기 때문에 O(log n)이 될 것입니다. 그건 꽤 좋은 모든 일에 대해 O(|V| log |V|) 시간을 줄 것입니다. 데이터가 좋은 형식으로 시작한다면 ~ 100 줄의 파이썬에서 처리 할 수 ​​있다고 생각합니다.