우정 관계 추적 알고리즘

Question

나는 "증명하려는 응용 프로그램을 생각하고있다"6 도의 분리"소셜 네트워크의 일부인 사용자 세트가있는 이론.

나는 그 요소를 가질 것이다 :

1. 6도 이론을 증명하고 싶은 두 명의 사용자
2. 각 사용자에 대해 소셜 네트워크의 친구 목록을 알고 있습니다.

두 사용자가 연결되어 있는지 확인하기위한 최상의 알고리즘은 어느 정도, 어떤 정도와 연결 단계를 표시합니까?

Answer 1

소셜 네트워크에서 두 사람 사이의 분리 정도를 찾는 것은 그래프에서 두 지점 사이에서 가장 짧은 경로를 찾는 특별한 경우 일뿐입니다. 가장 일반적인 접근법은입니다 Dijkstra의 알고리즘, 그러나 더 긴 토론도 참조하십시오 가장 짧은 경로 문제.

또한 All-Pairs 최단 경로 알고리즘을 실행하면 전체 네트워크에 대한 최소, 최대 및 평균 분리 정도를 찾을 수 있습니다.

Answer 2

일부 추가 배경 자료 :

이 문제를 일반적으로 해결하려면 웹 스크래핑 및 하나의 소셜 네트워크에 특정한 기타 임시 기술을 피해야합니다. 대신, 당신은 아마보고 싶을 것입니다 XHTML Friends Network (XFN) 이는 하이퍼 링크의 rel = ""속성을 사용하여 해당 하이퍼 링크와 귀하의 대상 간의 관계를 나타내는 방법입니다. 경쟁 표준도 있습니다 FOAF 사용하는 RDF.

이것들 미세 기름 한동안 주변에 있었지만, 그들에 대한 지원은 최근에 큰 성장했습니다. StackoverFlow는 프로필 페이지의 링크에서 "ME"를 사용합니다. WordPress 블로그는 Blogroll 이이 태그를 추가 할 수있는 편집 인터페이스에서 쉬운 방법을 제공합니다. 많은 소셜 사이트는 이들을 친구 간의 링크에 사용하여 관계를 나타냅니다.

이 때문에 Google은 이것에 관심을 갖고이 데이터를 채굴하기 시작했습니다. 그들은 가지고 있습니다 소셜 그래프 API XFN과 FOAF 데이터를 모두 채굴하여 원하는 작업 중 일부를 정확히 수행 할 수 있습니다. 거기에서 시작하는 것이 좋습니다. Google의 API에 대한 좋은 점은 웹 전체를 통해 이것을 채굴하기 때문에 생각했던 특정 소셜 네트워크를 넘어 검색을 넓힐 수 있습니다.