SNA (Social Network Analysis) 알고리즘 요청

Question

나는 만들기위한 임무를 받았다 소셜 그래프, 여기서, 한 명의 사용자와 함께 센터, 그것은 그가 가진 연결을 보여줍니다.

그러나 우리가 도달하기 전에 우리의 초점은 우리가 결정할 수있는 방법입니다. 가장 짧은 경로 2 명의 사용자 사이.

나는 그것을 할 알고리즘을 발견했지만 많은 시간이 걸리는 것 같습니다. 사회적 링크에 관한 것이기 때문에 우리는 가장 빠른 링크를 찾고 있습니다. 친구의 업데이트.

그렇다면 두 사용자 사이의 가장 짧은 경로를 결정하는 가장 빠른 방법이 무엇인지 알고 있습니까?

추신 : PHP & MySQL에서 예를 알고 있다면 가상 맥주 (또는 콜라)를 줄 것입니다. :디

Answer 1

Dijkstra의 알고리즘 그래프에서 두 노드 사이에서 가장 짧은 경로를 찾습니다.

Answer 2

당신이 원하는 것은 모든 페어 최단 경로 연산; 그래프에 대해 전역으로 쌍을 생성 해야하는 경우 모든 쌍에 대해 가장 짧은 경로 알고리즘을 실행하는 것보다 빠릅니다. 이 업데이트를 유지하는 것은 또 다른 문제입니다. 사람을 추가 할 때마다뿐만 아니라 그래프에 연결을 추가 할 때마다 수행해야합니다. 이것이 제작 사이트의 경우, PHP보다 빠른 언어로 작성된 오프라인 작업으로 그래프 생성을 유지하고 결과를 DB에 다시 작성하는 것이 좋습니다. 기존 C ++ 구현을 찾을 수 있습니다.

Answer 3

어쨌든 전체 그래프를 그릴 경우 가장 쉬운 것은 그래프에 추가 될 때 각 사람의 경로를 추적하는 것입니다. 따라서 그 사람의 친구에게는 길은 단지 "주인 -> 친구"입니다. 그런 다음 각 친구를 그래프에 추가하면 "Main Person-> Friend 1-> Friend 2"등을 저장하십시오.

내 마음 속의 그림이 정확하다면, 그것은 가장 쉬운 방법 인 것처럼 보이지만 다소 오해 할 수 있습니다.

Answer 4

Dijsktra의 알고리즘은 가중 그래프에서 잘 작동합니다. 소셜 그래프에서 모든 가장자리는 무게가 동일합니다. 따라서 dijkstra의 알고리즘은 BFS가됩니다. 그러나 밀도가 높은 그래프에서 각 레벨에서 검사 한 노드 목록은 엄청날 것입니다. 당신이 할 수있는 한 가지 최적화는 양쪽 끝 (A 및 B)에서 검색을 시작하는 것입니다.