J'ai une base de données de 20 millions d'utilisateurs et de connexions entre ces personnes. Comment puis-je prouver le concept de "Six degrés de séparation" concept de la manière la plus efficace en programmation?Comment puis-je prouver par programmation le concept "Six Degrees of Separation"?
link to the article about Six degrees of separation
Vous voulez juste mesurer la diameter of the graph. C'est exactement la métrique de trouver la séparation entre les nœuds les plus lointainement connectés dans un graphique. Un grand nombre d'algorithmes sur Google, Boost graph aussi.
Vous pouvez probablement adapter le graphique en mémoire (dans la représentation que chaque sommet connaît une liste de ses voisins). Puis, à partir de chaque sommet n, vous pouvez exécuter une recherche en largeur d'abord (en utilisant une file d'attente) à la profondeur de 6 et compter le nombre de sommets visités. Si tous les sommets ne sont pas visités, vous avez réfuté le théorème. Dans les autres cas, continuez avec le prochain sommet n.
Ceci est O (N * (N + #)) = N * (N + N * 100) = 100N^2, si l'utilisateur a 100 connexions en moyenne, ce qui n'est pas idéal pour N = 20 millions. Je me demande si les bibliothèques mentionnées peuvent calculer le diamètre en meilleure complexité temporelle (l'algorithme général est O (N^3)).
Les calculs des sommets individuels sont indépendants, ils peuvent donc être effectués en parallèle.
Une petite heuristique: commencez par les sommets qui ont le degré le plus bas (meilleure chance de réfuter le théorème).
Je pense que c'est nettement pire que O (n^2). même en supposant que chaque nœud est connecté à seulement 3 autres nœuds, une trace de pile de profondeur 6 serait 3 * 2^0 + 3 * 2^1 + 3 * 2^2 + 3 * 2^3 + 3 * 2^4 + 3 * 2^5. Croissance exponentielle – patros
Pour chaque sommet, vous visitez chaque sommet au maximum une fois, de sorte que la course pour un sommet prend O (N). –
Ah, c'est vrai, c'est une limite. Je pense que c'est toujours O (N^3), alors n'est-ce pas? Trouver un chemin du sommet A au sommet B est O (N), et vous devez le faire O (N^2) fois. – patros
Je pense que le moyen le plus efficace (pire des cas) est presque N^3. Construire une matrice d'adjacence, puis prendre cette matrice^2,^3,^4,^5 et^6. Recherchez toutes les entrées dans le graphique qui sont 0 pour la matrice à travers la matrice^6. Heureusement, vous pouvez essayer de distinguer les sous-graphes (de grands groupes de personnes qui ne sont connectés à d'autres groupes que par un nombre relativement restreint de nœuds de type "bridge"), mais il n'y a aucune garantie que vous en ayez.
Vous ne pouvez pas créer une matrice d'adjacence de taille 20x20 millions en mémoire. De plus, la multiplication serait O (N^3), où N est 20 millions. –
C'est à peu près n^2,8 avec l'algorithme de strassen, car ce sont des matrices carrées. vous n'avez pas non plus besoin de garder toute la matix en mémoire, seulement les parties que vous multipliez activement. Page le reste sur le disque. – patros
Nécessite beaucoup de disque mais ... 400 To pour une approche naïve. Beaucoup de place pour la compression cependant. – patros
Eh bien, une meilleure réponse a déjà été donnée, mais de prime abord, j'aurais choisi l'algorithme Floyd-Warshall pour les paires les plus courtes, qui est O (n^3). Je ne suis pas sûr de la complexité de l'algorithme de diamètre de graphe, mais il "sonne" comme ceci serait également O (n^3). J'aimerais avoir des précisions à ce sujet si quelqu'un le sait. D'un autre côté, avez-vous vraiment une telle base de données? Effrayant.
Est-ce que six degress est un maximum ou une moyenne? La plupart des analyses que j'ai lues utilisent la moyenne et non le maximum. –
La conception commune de "six degrés de séparation" est que c'est un maximum. Bien sûr, ce n'est pas vrai du tout dans la réalité. C'est juste plus impressionnant de le dire de cette façon et difficile de trouver des contre-exemples. –