ProblèmeGrapheCarréConnexions

This page started as a translation of link:ConnectedGraphSquaringProblem.

Nous pouvons imaginer un réseau social comme un graphe où les noeuds sont des personnes et les fils des relations.

Pour des petits groupes sociaux le graphe peut être presque "complet", c'est à dire que chaque personne peut maintenir une relation personnelle avec aussi chacune des autres personnes dans le groupe.

Pour de plus grands groupes, comme une nation toute entière, ceci est impossible ; il y a beaucoup trop de personnes pour que chaque personne puisse avoir une relation avec même une fraction significative de ce groupe. Ainsi les choses deviennent impersonnelles, ce qui génère des problèmes.

Techniquement, s'il y a n personnes dans le réseau, alors pour que le graphe soit "complet", c'est à dire, pour que chaque personne connaisse toutes les autres, chaque personne doit maintenir n - 1 relations, et le réseau en tant qu'ensemble sera de l'ordre de n^2 de fils. Ceci est impossible parce que chaque personne n'a tout bonnement pas suffisamment de temps et d'énergie pour maintenir les relations personnelles ; nous pouvons imaginer que chaque fil "coûte quelque chose", et ainsi alors que le réseau en tant qu'ensemble peut être capable d'induire beaucoup de fils, il ne peut probablement pas induire n^2 quand n est grand.

C'est la raison pour laquelle le problème d'échelle d'un réseau social est parfois appelée un exemple de ProblèmeGrapheCarréConnexions.

LangueFrançaise PageTranslation ConnectedGraphSquaringProblem


Discussion

SVP, regardez MeatBall:ConnectedGraphSquaringProblem en anglais pour le reste de la discussion.

Une personne suggérait l'usage d'arbres laps de temps minimaux pour fournir un graphe connecté tout en minimisant les relations. Ainsi, en termes de réseau social, nous construisons des sous-réseaux en arbre minimaux… intéressant… au lieu de clubs sociaux qui connectent des membres "similaires", et qui contiennent des sous-réseaux de noeuds (des personnes), nous voulons trouver un sous-jeu de fils (amitiés) entre toutes les personnes sur la Terre.

Je suppose que les "coûts de fils" pourraient être la réciproque de "l'affinité naturelle" des gens à se connecter (par exemple il existe un "coût" pour se connecter à quelqu'un que vous connaissez mais n'aimez pas beaucoup). Alors nous pourrions utiliser l'algorithme de Prim pour construire un arbre minimal de chevauchement. En réalité, nous demandons, par ordre, que chaque personne sur la Terre de se connecter à son meilleur ami, si ce n'est que quiconque dans le réseau soit écarté.

Alors nous leur disons tout ce qu'ils veulent, ils n'ont pas besoin de se soucier à communiquer avec toutes les autres personnes qu'ils connaissent, ils peuvent simplement router des messages avec leurs une ou deux connexions, et tout sera parfait parce le net est encore connecté.

Une idée intéressante et une qui montre vraiment en fait la manière d'avoir une société dimensionnable. Cependant, je pense que la difficulté la plus pressante avec une grande société n'est pas simplement de s'assurer de la connexité, mais plutôt de savoir la manière de porter la collégialité/un plus grand sens de relations personnelles à l'intérieur des grands réseaux sociaux. En termes de graphe, un minimum d'arbre de chevauchement minimise les fils, ce qui est bon, mais accroît le nombre moyen de sautillements entre les noeuds, ce qui accroît la distance sociale (tout en minimisant aussi, peut-être, les fils requis, car ceux-ci constituent des "dépenses de maintenance").

BayleShanks


Pour un groupe donné de personnes, plus de connexions est souvent mieux. Le "jeu du téléphone" illustre le problème avec "seulement 2 connexions".

Malheureusement, il est impossible pour quiconque d'avoir une connexion directe à quiconque sur la planète – c'est un ProblèmeGrapheCarréConnexions.

Ainsi, nous allons avoir des connexions indirectes – et du fait des problèmes posés par le "jeu du téléphone", nous voulons minimiser le nombre d'étapes d'indirection.

Imaginons que le cerveau humain soit réglé pour traiter avec environ 10 autres personnes. (Je prends simplemnet ce chiffre pour faire que les mathématiques puissent fonctionner aisément – je serais très intéressé que la recherche actuelle essaye de quantifier cela.)

Alors nous pourrions construire des groupes de 11 personnes, chacun d'eux connaissant toutes les autres personnes dans le groupe, mais chaque groupe serait isolé.

Ou nous pourrions construire une bande linéaire de 3 personnes de large d'une longeur indéfinie, où chaque personne connaît les 10 personnes proche d'elle.

Ou nous pourrions construire des hiérarchies de taille indéfinie, où chaque membre du "middle management" parle vers le haut à son boss, et vers le bas à environ 10 employés. Parce qu'il y a moins de 10^9 personnes aux Etats-Unis à cette heure, la totalité de la population des Etats-Unis serait seulement à 9 degrés de séparation de la personne racine. Parce qu'il y a moins de 10^10 personnes sur la Terre dans l'InstantWiki, la totalité de la population sur la terre serait seulement à 10 degrés de séparation de la personne racine.

Ceci est en rapport avec la théorie bien connue des "six degrés de séparation"1

Quels sont les autres choses que nous avons besoin de prendre en considération ?

Voir EspritDeRuche.

DavidCary


Voilà un peu de recherche :

"Le Nombre de Dunbar en tant que limite aux Tailles des Groupes" http://www.lifewithalacrity.com/2004/03/the_dunbar_numb.html

Est-ce que ce nombre "150" est le nombre des personnes avec lequel une personne unique peut directement avoir des interactions à double-sens ? Ou avoir des liens indirects déjà formés ?

Cette page a démarré par une traduction du lien ConnectedGraphSquaringProblem. Ajoutons que dans une note d'un article traitant de la topologie des communautés, ClayShirky parle pour être plus précis de n^2-n ce qui semble plus logique même si je ne suis pas mathématicien ;)


Voir aussi TailleLimiteDiscussionPetitGroupe. Voir aussi CommunautéPeutNePasGrandir.

Footnotes:

1. NdT du projet petit monde ? pas trouvé d’article sur wikipedia francophone.

Languages:

The same page elsewhere:
MeatBall:ProblèmeGrapheCarréConnexions