Network source location by entropic message passing

The ground state entropy of network source location problems is derived at both the replica symmetric level and one-step replica symmetry breaking level using the entropic cavity method. The recursive relations for the cavity probability and entropy are obtained in a probabilistic way by focusing on the change of the ground state size under the cavity iterations. The resulting entropic message passing inspired decimation and reinforcement algorithms identify the optimal location of sources in single instances of transportation networks. The traditional belief propagation without taking the entropic effect into account is also compared. We find that in the glassy phase the reinforcement algorithm is fastest while the entropic message passing inspired decimation yields a value of the fraction of source nodes in the optimized network closest to the ground state value.