Bulletin of the American Physical Society
APS March Meeting 2014
Volume 59, Number 1
Monday–Friday, March 3–7, 2014; Denver, Colorado
Session D14: Invited Session: Algorithms from Statistical Physics and the Physics of Algorithms |
Hide Abstracts |
Sponsoring Units: GSNP DCOMP Room: 301-303 |
Monday, March 3, 2014 2:30PM - 3:06PM |
D14.00001: Fast algorithms for glassy materials: methods and explorations Invited Speaker: A. Alan Middleton Glassy materials with frozen disorder, including random magnets such as spin glasses and interfaces in disordered materials, exhibit striking non-equilibrium behavior such as the ability to store a history of external parameters (memory). Precisely due to their glassy nature, direct simulation of models of these materials is very slow. In some fortunate cases, however, algorithms exist that exactly compute thermodynamic quantities. Such cases include spin glasses in two dimensions and interfaces and random field magnets in arbitrary dimensions at zero temperature. Using algorithms built using ideas developed by computer scientists and mathematicians, one can even directly sample equilibrium configurations in very large systems, as if one picked the configurations out of a ``hat'' of all configurations weighted by their Boltzmann factors. This talk will provide some of the background for these methods and discuss the connections between physics and computer science, as used by a number of groups. Recent applications of these methods to investigating phase transitions in glassy materials and to answering qualitative questions about the free energy landscape and memory effects will be discussed. [Preview Abstract] |
Monday, March 3, 2014 3:06PM - 3:42PM |
D14.00002: The Cavity Method, Belief Propagation, and Phase Transitions in Community Detection Invited Speaker: Cristopher Moore The stochastic block model is a popular model of social and biological networks. Each vertex belongs to one of k groups, and the probability of an edge depends on the groups to which its endpoints belong. It allows both ``assortative'' communities where vertices tend to connect to others in the same group, and ``disassortative'' and directed community structures, like those in food webs, where predators form a community because they feed on similar prey. Given a network, we would like to infer the most likely block model: both the group labels of the nodes, and the parameters of the model. I will describe an efficient algorithm for this problem based on belief propagation, or equivalently the cavity method of statistical physics. Physically, the model corresponds to a generalized Potts model with strong interactions on the links of the network, and weak interactions along the non-links. Our analysis also reveals phase transitions in the detectability of communities, including an undetectable phase where no algorithm can do better than chance. There is also a regime where the accuracy we can achieve jumps discontinuously as a function of the fraction of nodes we have prior information about, and a tricritical point where this discontinuity disappears. This is joint work with Aurelien Decelle, Florent Krzakala, Lenka Zdeborov\'a, and Pan Zhang. [Preview Abstract] |
Monday, March 3, 2014 3:42PM - 4:18PM |
D14.00003: Efficient discovery of large-scale patterns in weighted networks Invited Speaker: Aaron Clauset Networks provide a rich and mathematically principled approach to characterizing the structure of complex systems. A common step in understanding the structure and function of real-world networks is to characterize their large-scale organizational pattern via community detection, in which we aim to find a network partition that groups together vertices with similar connectivity patterns. Although interactions in most real-world systems take real or integer valued weights, common approaches to community detection use only the unweighted edges, thereby ignoring a potentially rich source of additional information. In this talk, I will describe a generalization of the popular stochastic block model that can discover community structure from both the existence and weight of edges. This model can be efficiently fitted to real-world networks using ``approximate inference'' techniques, like the cavity method, originally developed in statistical physics and which are now commonly used by computer scientists in machine learning. Applied to several real-world networks, I show that edge weights sometimes contain hidden information that is distinct from what is contained in edge existences. Learning from weights also provides better estimates of missing information. I will close with a few brief comments on the impact of weight information on the detectability threshold for recovering hidden patterns in these systems, and on future opportunities in this area. [Preview Abstract] |
Monday, March 3, 2014 4:18PM - 4:54PM |
D14.00004: Non-equilibrium Monte Carlo: Sampling with Irreversible Markov ChainsĀ Invited Speaker: Marija Vucelja Markov Chain Monte Carlo (MCMC) algorithms are ubiquitous across different fields of physics. They are an invaluable numerical tool for studies of complex many body problems, critical phenomena etc. Yet often their convergence rates for real systems are slow. MCMC algorithms are used to create realizations of the desired physical system in its steady state. Most implementations of MCMC use Markov Chains that obey detailed balance, even though this not a necessary requirement for converging to a steady state. I plan to overview several examples that utilize irreversible Markov Chains, where violating detailed balance has improved the convergence rate. Finally I will pose some open questions and discuss attempts to use non-equilibrium dynamics for efficient sampling. Potential applications of such algorithms are numerical studies of phase transitions, soft matter dynamics, protein structures, granular media etc. [Preview Abstract] |
Monday, March 3, 2014 4:54PM - 5:30PM |
D14.00005: Rare-event simulation methods for equilibrium and non-equilibrium events Invited Speaker: Robert Ziff Rare events are those that occur with a very low probability in experiment, or are common but difficult to sample using standard computer simulation techniques. Such processes require advanced methods in order to obtain useful results in reasonable amounts of computer time. We discuss some of those techniques here, including the ``barrier'' method, splitting methods, and a Forward-Flux Sampling in Time (FFST) algorithm, and apply them to measure the nucleation times of the first-order transition in the Ziff-Gulari-Barshad model of surface catalysis, including nucleation in finite equilibrium states, which are measured to occur with probabilities as low as 10\textasciicircum (-40). We also study the transitions in the Maier-Stein model of chemical kinetics, and use the methods to find the harmonic measure in percolation and Diffusion-Limited Aggregation (DLA) clusters. co-authors: David Adams, Google, and Leonard Sander, University of Michigan. References: D. A. Adams, R. M. Ziff, and L. M. Sander, Computation of nucleation at a nonequilibrium first-order phase transition using a rare-event algorithm, Journal of Chemical Physics, 133, 174107 (2010) D. A. Adams, L. M. Sander and R. M. Ziff, The barrier method: A technique for calculating very long transition times, Journal of Chemical Physics 133, 124103 (2010) D. A. Adams, Yen Ting Lin, L. M. Sander and R. M. Ziff, ``Harmonic measure for critical Potts clusters,'' Physical Review E 80, 031141 (2009) [Preview Abstract] |
Follow Us |
Engage
Become an APS Member |
My APS
Renew Membership |
Information for |
About APSThe American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics. |
© 2024 American Physical Society
| All rights reserved | Terms of Use
| Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 20740-3844
(301) 209-3200
Editorial Office
100 Motor Pkwy, Suite 110, Hauppauge, NY 11788
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700