ProblèmeGrapheCarréConnexions

MeatballWiki | RecentChanges | Random Page | Indices | Categories

Cette page a démarré sur ConnectedGraphSquaringProblem

Problème : Dans tout système qui peut être représenté par un graphe connecté, comment minimisez-vous ou surmontez-vous le O(N**2) coût de maintenance du réseau ?

: -- ou comment faites-vous que les sociétés se dimensionnent ?

Ce qui veut dire, que si vous avez un graphe connecté de N vertices et que chaque vertex se connecte aux autres vertices, vous aurez un total de (N-1)*N/2 = (N**2 - N)/2 côtés = O(N**2) côtés.

Généralement, maintenir un réseau façonné dans un graphe connecté est lié au coût des bords. De ce fait le coût de maintenance croît plus vite que linéairement (O(N)). C'est un problème parce que vous pouvez seulement faire croître la quantité d'énergie que vous mettez dans le réseau linéairement si les vertices agissaient indépendamment.

Un tel exemple sont les sociétés où les vertices sont des personnes et les bords sont des relations. Le ProblèmeGrapheCarréConnexions dans ce contexte décrit pourquoi "l'amitié" ne gère pas ensemble une grande société : parce que maintenir de l'amitié exige du temps et de l'énergie (émotionnelle), les gens ne peuvent pas maintenir un nombre infini d'amitiés. Par conséquent, au fur et à mesure que la société grandit, la fraction des amis qu'a chaque personne décroît.

La solution est clairement de maintenir le réseau de façon non indépendante, prenant de ce fait l'avantage du taux O(N**2) de connectivité. Intervertissez le problème en d'autres mots. Mais quels sont les bons moyens de construire un réseau de maintenance, tout spécialement dans le contexte de l'HypermédiumCollaboratif ?

Voir aussi LoiDeMetcalfe, CommunautéPeutNePasGrandir, LearningExploitationTradeOff

Notez aussi que la LoiDeMetcalfe prend cela même bien plus loin, dans ce qui pourrait s'appeler "Power set exponentiation phenomenon."

Subnetting

Quelle caractérisitique du réseau est critique pour vous dans cette application ?

La maintenance de l'arbre minimal en chevauchement est bon marché sur le plan informatique et vous maintient connecté, compte du fait vous ne devez pas générer tous les O(N**2) liens et les rejetez de cet ensemble. Ainsi regardez une heuristique qui vous donne un O(N Log N) sous-ensemble des O(N**2) liens contenant les "high scoring links" pour construire le sous réseau. Vous pouvez ne pas trouver une belle heuristique mais ceci est peu probable à s'en soucier. Votre réseau va avoir besoin dans tous les cas d'être résilient. --JamesCrook

Vraiment, vous voulez la puissance O(N^2) du grave qui vous aide, et seulement la puissance O(N) ou O(NlgN?) des sous-graphes travaillant contre vous. Par exemple, vous voulez que le coût de la bande passante pour diffuser soit de O(N), mais une fois que tous les noeuds ont le message, vous voulez que O(N^2) fonctionne pour résoudre le problème.

: Par conséquent, en termes de réseau social, nous construisons des "minimal spanning tree subnets"... intéressant... au lieu de clubs sociaux qui connectent des membres "similaires", et qui contiennent des sous-ensemble de noeuds (personnes), nous voulons trouver un sous-ensemble de bords (amitiés) entre toutes les personnes sur Terre.

: J'imagine que les "coûts des bords" pourraient être la réciproque de "l'affinité naturelle" des personnes à être connectées (par ex. il y a un coût pour connecter à quelqu'un que vous connaissez mais qui n'aime pas pas trop). Alors, nous pourrions uitliser l'algorithme de Prism pour construire un arbre de chevauchement minimal. Effectivement, nous demadons, en séquence que chaque personne sur Terre se connecte à son meilleur ami, si ce n'est que tout le monde déjà présent dans le sous-net est rejeté.

: Ensuite, nous leur disons tout ce qu'ils veulent, ils peuvent simplement router des messages à travers leurs une ou deux connexions, et tout sera beau dès que lent sera encore connecté.

: Une idée intéressante, et une qui montre bien sûr comment obtenir une société dimensionnable. Néanmoins, je pense que la difficulté la plus pressante dans une grande société n'est pas simplement de s'assurer de la connectivité, mais plutôt savoir comment porter la collégialité/ un plus grand sens de l'amitié personnelle, ce qui est bien, mais accroît le chiffre moyen du nimbre de sauts entre les noeuds, ce qui accroît la "distance" sociale ressentie par les participants. Nous voulons faire le contraire ; nous voulons non seulement préserver wela connectivité, mais seulement minimiser la distance sociale (tout en, peut-être, minimisant les bords requis, parce qu'ils représentent les "dépenses de maintenance").

: -- BayleShanks

Dans le cas de Wiki, quelques liens arrivent tout seul, sous la forme de LienAccidentel. Une bonne fonctionnalité d'AutoLien (peut-être conscience sémantique) pousserait même ce phénomène plus à fond. -- MichaelSparks?

... O(N**2) coût de maintenance ... Dans les systèmes du vrai monde, vous n'avez jamais cette situation. Par exemple dans les systèmes moléculaires, vous avez une gamme de petites force (vers 3 à 6 voisins seulement) alors que les gammes de forces longues ne s'appliquent seulement que dans des cas spéciaux (et leur calcu peut être simplifié). Ainsi cela semble être plus un problème théorique qu'un problème pratique.

On Atoms...

The reason why atoms destabilize past 168 protons is unrelated to the ConnectedGraphSquaringProblem. It is, however, an example of something else: The attraction between vertices and the repulsion between vertices as a function of N behave differently: For higher numbers of N, the attraction drops and the nucelus becomes unstable.

Here's the physical background:

Such atoms are not unstable from electrical forces between protons and electrons (which are capable of holding large things together with no trouble, for the same reason that the huge number of interacting particles contribute together to the earth's gravity.) The problem with building an atom with more than 200 protons has nothing to do with there being too many proton-electron interactions. The problem is that the nucleus becomes unstable, and that not because of too many attractive forces, but because of too few. Protons repel each other from electrical repulsion. In addition, protons and neutrons all have an attractive force towards each other at sufficiently small scales. Finally, neutrons are inherently unstable; left alone, they decay, but if they are closely bound to other neutrons or protons, then the decay is staved off. So atoms tend to have roughly as many neutrons as protons. More than that, and the neutrons would decay (beta-decay). Fewer than that and the repulsive force between protons blows the nucleus apart (producing either alpha'''Problem: In decay or fission). If you try to get way too many protons in a nucleus, a new problem happens: because the strong nuclear force (which binds the protons and neutrons to each other) operates only at very small scales, and the electric repulsion operates over arbitrarily long distances, it becomes impossible to overcome the electric repulsion once the nucleus gets to big. --ThomasBushnellBSG

So, Protons = Fanatics, Neutrons = Followers, Electrons = Nay-sayers? --WilliamUnderwood

ProblèmeGrapheCarréConnexions

Discussion