Algorithme de suivi des relations d'amitié

Question

Je pense à une application qui tenterait de prouver le & Six degrés de séparation " la théorie avec un ensemble d'utilisateurs qui font partie d'un réseau social.

J'aurais ces éléments:

1. Quelques utilisateurs pour lesquels j'aimerais prouver la théorie des six degrés
2. Pour chaque utilisateur, je connais la liste d'amis du réseau social

Quel est le meilleur algorithme pour voir si les deux utilisateurs sont connectés, avec quel degré et pour afficher les étapes éventuelles de la connexion?

Answer 1

La recherche du degré de séparation entre deux personnes dans un réseau social n’est qu’un cas particulier de recherche du chemin le plus court entre deux points d’un graphique. L’approche la plus courante est l'algorithme de Dijkstra , mais vous trouverez également une discussion plus longue du Problème du chemin le plus court .

En outre, en exécutant un algorithme du plus court chemin de toutes les paires, vous pouvez connaître le nombre minimum, maximum et moyen de degrés de séparation pour l'ensemble du réseau.

Answer 2

Quelques informations supplémentaires:

Pour résoudre ce problème en général, évitez les détections Web et autres techniques ad-hoc spécifiques à un réseau social. Au lieu de cela, vous voudrez probablement vous pencher sur le réseau d'amis XHTML (XFN) , qui permet d'utiliser le = " " attribut d'un lien hypertexte indiquant la relation entre la cible de ce lien hypertexte et vous. Il existe également une norme concurrente appelée FOAF qui utilise RDF .

Ces microformats existent depuis un moment, mais leur assistance a considérablement augmenté ces derniers temps. StackOverflow utilise " me " dans le lien sur votre page de profil. Les blogs WordPress offrent un moyen simple d’ajouter ces balises à l’interface d’édition. De nombreux sites sociaux utilisent ces liens dans les liens entre amis pour indiquer des relations.

Pour cette raison, Google s’y intéresse et commence à exploiter ces données. Ils disposent d'une API de graphique social pouvant exploiter les données XFN et FOAF pour effectuer certaines les choses que vous voulez faire. Je vous suggère de commencer par là. L’avantage de l’API de Google réside dans le fait qu’ils exploitent ce réseau sur le Web. Vous pouvez ainsi élargir votre recherche au-delà du réseau social que vous aviez en tête.