Dissertations, Theses, and Capstone Projects

Date of Degree


Document Type


Degree Name





Hernan A. Makse

Subject Categories



Pure sciences, Boltzmann, Immunization strategies, Statistical physics


Optimization problem has always been considered as a central topic in various areas of science and engineering. It aims at finding the configuration of a large number of variables with which the objective function is optimal. The close relation between optimization problems and statistical physics through the probability measure of the Boltzmann type has brought new theoretical tools from statistical physics of disordered systems to optimization problems. In this thesis, we use message passing techniques, in particular cavity method, developed in the last decades within spin glass theory to study optimization problems in complex systems. In the study of force transmission in jammed disordered systems, we develop a mean-field theory based on the consideration of the contact network as a random graph where the force transmission becomes a constraint satisfaction problem, with which the constraints enforce force and torque balances on each particle. We thus use cavity method to compute the force distribution for random packings of hard particles of any shape, with or without friction and find a new signature of jamming in the small force behavior whose exponent has attracted recent active interest. Furthermore, we relate the force distribution to a lower bound of the average coordination number of jammed packings of frictional spheres. The theoretical framework describes different types of systems, such as non-spherical objects in arbitrary dimensions, providing a common mean-field scenario to investigate force transmission, contact networks and coordination numbers of jammed disordered packings. Another application of the cavity method is immunization strategies. We study the problem of finding the most influential set of nodes in interaction networks to immunize against epidemics. By means of cavity method approach, we propose a new immunization strategy to identify immunization targets efficiently with respect to the susceptable-infected-recovered epidemic model. We implement our method on computer-generated random graphs and real networks and find that our new immunization strategy can significantly reduce the size of epidemic.

Included in

Physics Commons