Jag accepterar att kakor lagras på min dator

Läs mer

Graph optimization and the Potts spin model.

Graph optimization and the Potts spin model. Beställ tryckt exemplar Lägg i kundvagnen
Författare: Bengtsson Mats
Ort: Linköping
Sidor: 24
Utgivningsår: 1998
Publiceringsdatum: 1998-10-22
Rapportnummer: (FOA-R--98-00860-616)
Nyckelord neutral networks, statistical mechanics, Potts spin, network, optimization, neutronnät, statistisk mekanik, Potts spinn, nätverk, optimering, E7015, 73
Sammanfattning Vi beskriver sambandet mellan en Potts spinnmodell med en nodberoende ferromagnetisk växelverkan och en svag konstant antiferromagnetisk term, med en grafmodell där länkvariablerna är dynamiska. Modellen likna Fortuin-Kastelyn-Swendsen-Wang representationen, men där den extra antiferromagnetiska termen resulterar i ett icke-trivialt superantiferromagnetiskt grundtillstånd hos systemet. Detta gör det möjligt att använda medelfältsdynamik och därmed en effektiv numerisk implementering. Modellen kan också tolkas som en kombinerad spinn- och länkmodell. Givet en viss spinnkonfiguration så kan länkvariablerna bestämmas helt lokalt. Följaktligen är lösningen av länkmodellen trivial när väl spinntillståndet är bestämt. Isomorfismen mellan spinnmodellen och grafmodellen kan därför tjäna som en bas för optimering av komplexa nätverk.
Abstract We have developed the connection between a Potts spin model with a ferromagnetic site dependent interaction and a weak constant antiferromagnetic term, and a graph model where the bonds act as dynamic variables. The model is similar to the Fortuin-Kastelyn-Swendsen-Wang representation, but where the additional antiferromagnetic term ensures that a nontrivial superantiferromagnetic state is found as the ground state of the system. This makes it possible to use mean field dynamics, and thereby make a fast numerical implementation. In addition the model can be interpreted as a combined spin and bond model. Given a certain spin configuration, the bond variables are determined strictly locally. Thus, given a spin configuration, the solution of the corresponding bond optimization problem is trivial. The isomorphism between the spin model and the graph model may therefore serve as a framework for complex network optimiation problems.

Kundvagn

Inga rapporter i kundvagnen

FOI, Totalförsvarets forskningsinstitut

FOI
Totalförsvarets forskningsinstitut
164 90 Stockholm

Tel: 08-555 030 00
Fax: 08-555 031 00

Orgnr: 202100-5182