Phase coexistence in the fully heterogeneous Hegselmann-Krause opinion dynamics model.

We present an extensive study of the joint effects of heterogeneous social agents and their heterogeneous social links in a bounded confidence opinion dynamics model. The full phase diagram of the model is explored for two different network's topologies and compared to two opposed extreme cases: on one hand, the heterogeneous agents constitute a mixed population and on the other, their interactions are modeled by a lattice. The results show that when agents prone to compromise coexist with close-minded ones, the steady state of the dynamics shows coexistent phases. In particular, unlike the case of homogeneous agents in networks, or heterogeneous agents in a fully mixed population, it is possible that the society ends up in consensus around one extreme opinion. Moreover, during the dynamics, the consensus may be overturned from one extreme to the other of the opinion space. We also show that the standard order parameter, the normalized average size of the largest opinion cluster, may be misleading in this case, as it hides the existence of these phases. The phase where the opinion of the society is overturned does not require the presence of agents with special characteristics, (stubborn, extremists, etc.); it results from the interplay of agents which have agreed on an extreme opinion with the remaining group that holds the opposite one. Among the former, some may be prone to compromise with other agents which are out of the majority group, these agents, according to their location in the network, may act like bridges between the two groups and slowly attract the whole society to the other extreme.

Understanding who talks about what: comparison between the information treatment in traditional media and online discussions.

We study the dynamics of interactions between a traditional medium, the New York Times journal, and its followers in Twitter, using a massive dataset. It consists of the metadata of the articles published by the journal during the first year of the COVID-19 pandemic, and the posts published in Twitter by a large set of followers of the @nytimes account along with those published by a set of followers of several other media of different kind. The dynamics of discussions held in Twitter by exclusive followers of a medium show a strong dependence on the medium they follow: the followers of @FoxNews show the highest similarity to each other and a strong differentiation of interests with the general group. Our results also reveal the difference in the attention payed to U.S. presidential elections by the journal and by its followers, and show that the topic related to the "Black Lives Matter" movement started in Twitter, and was addressed later by the journal.

Position distribution in a generalized run-and-tumble process.

We study a class of stochastic processes of the type d^{n}x/dt^{n}=v_{0}σ(t) where n>0 is a positive integer and σ(t)=±1 represents an active telegraphic noise that flips from one state to the other with a constant rate γ. For n=1, it reduces to the standard run-and-tumble process for active particles in one dimension. This process can be analytically continued to any n>0, including noninteger values. We compute exactly the mean-squared displacement at time t for all n>0 and show that at late times while it grows as ∼t^{2n-1} for n>1/2, it approaches a constant for n<1/2. In the marginal case n=1/2, it grows very slowly with time as ∼lnt. Thus, the process undergoes a localization transition at n=1/2. We also show that the position distribution p_{n}(x,t) remains time-dependent even at late times for n≥1/2, but approaches a stationary time-independent form for n<1/2. The tails of the position distribution at late times exhibit a large deviation form, p_{n}(x,t)∼exp[-γtΦ_{n}(x/x^{*}(t))], where x^{*}(t)=v_{0}t^{n}/Γ(n+1). We compute the rate function Φ_{n}(z) analytically for all n>0 and also numerically using importance sampling methods, finding excellent agreement between them. For three special values n=1, n=2, and n=1/2 we compute the exact cumulant-generating function of the position distribution at all times t.

Mean perimeter and area of the convex hull of a planar Brownian motion in the presence of resetting.

We compute exactly the mean perimeter and the mean area of the convex hull of a two-dimensional isotropic Brownian motion of duration t and diffusion constant D, in the presence of resetting to the origin at a constant rate r. We show that for any t, the mean perimeter is given by 〈L(t)〉=2πsqrt[D/r]f_{1}(rt) and the mean area is given by 〈A(t)〉=2πD/rf_{2}(rt) where the scaling functions f_{1}(z) and f_{2}(z) are computed explicitly. For large t≫1/r, the mean perimeter grows extremely slowly as 〈L(t)〉∝ln(rt) with time. Likewise, the mean area also grows slowly as 〈A(t)〉∝ln^{2}(rt) for t≫1/r. Our exact results indicate that the convex hull, in the presence of resetting, approaches a circular shape at late times due to the isotropy of the Brownian motion. Numerical simulations are in perfect agreement with our analytical predictions.

Large deviations of connected components in the stochastic block model.

We study the stochastic block model, which is often used to model community structures and study community-detection algorithms. We consider the case of two blocks in regard to its largest connected component and largest biconnected component, respectively. We are especially interested in the distributions of their sizes including the tails down to probabilities smaller than 10^{-800}. For this purpose we use sophisticated Markov chain Monte Carlo simulations to sample graphs from the stochastic block model ensemble. We use these data to study the large-deviation rate function and conjecture that the large-deviation principle holds. Further we compare the distribution to the well-known Erdos-Rényi ensemble, where we notice subtle differences at and above the percolation threshold.

When open mindedness hinders consensus.

We perform a detailed study of the Hegselmann-Krause bounded confidence opinion dynamics model with heterogeneousconfidence εi drawn from uniform distributions in different intervals [ε1, εu]. The phase diagram reveals a highly complex andnon-monotonous behaviour, with a re-entrant consensus phase in the region where fragmentation into multiple distinct opinionsis expected for the homogeneous case. A careful exploration of the phase diagram, along with an extensive finite-size analysis,allows us to identify the mechanism leading to this counter-intuitive behaviour. This systematic study over system sizes whichgo well beyond those of previous works, is enabled by an efficient algorithm presented in this article.

Large deviations of a random walk model with emerging territories.

We study an agent-based model of animals marking their territory and evading adversarial territory in one dimension with respect to the distribution of the size of the resulting territories. In particular, we use sophisticated sampling methods to determine it over a large part of territory sizes, including atypically small and large configurations, which occur with probability of less than 10^{-30}. We find hints for the validity of a large deviation principle, the shape of the rate function for the right tail of the distribution, and insight into the structure of atypical realizations.

Collective effects of the cost of opinion change.

We study the dynamics of opinion formation in the situation where changing opinion involves a cost for the agents. To do so we couple the dynamics of a heterogeneous bounded confidence Hegselmann-Krause model with that of the resources that the agents invest on each opinion change. The outcomes of the dynamics are non-trivial and strongly depend on the different regions of the confidence parameter space. In particular, a second order phase transition, for which we determine the corresponding critical exponents, is found in the region where a re-entrant consensus phase is observed in the heterogeneous Hegselmann-Krause model. For regions where consensus always exist in the heterogeneous Hegselmann-Krause model, the introduction of cost does not lead to a phase transition but just to a continuous decrease of the size of the largest opinion cluster. Finally in the region where fragmentation is expected in the heterogeneous HK model, the introduction of a very small cost surprisingly increases the size of the largest opinion cluster.

Number of longest increasing subsequences.

We study the entropy S of longest increasing subsequences (LISs), i.e., the logarithm of the number of distinct LISs. We consider two ensembles of sequences, namely, random permutations of integers and sequences drawn independent and identically distributed (i.i.d.) from a limited number of distinct integers. Using sophisticated algorithms, we are able to exactly count the number of LISs for each given sequence. Furthermore, we are not only measuring averages and variances for the considered ensembles of sequences, but we sample very large parts of the probability distribution p(S) with very high precision. Especially, we are able to observe the tails of extremely rare events which occur with probabilities smaller than 10^{-600}. We show that the distribution of the entropy of the LISs is approximately Gaussian with deviations in the far tails, which might vanish in the limit of long sequences. Further, we propose a large-deviation rate function which fits best to our observed data.

Asymptotic behavior of the length of the longest increasing subsequences of random walks.

We numerically estimate the leading asymptotic behavior of the length L_{n} of the longest increasing subsequence of random walks with step increments following Student's t-distribution with parameters in the range 1/2≤ν≤5. We find that the expected value E(L_{n})∼n^{θ}lnn, with θ decreasing from θ(ν=1/2)≈0.70 to θ(ν≥5/2)≈0.50. For random walks with a distribution of step increments of finite variance (ν>2), this confirms previous observation of E(L_{n})∼sqrt[n]lnn to leading order. We note that this asymptotic behavior (including the subleading term) resembles that of the largest part of random integer partitions under the uniform measure and that, curiously, both random variables seem to follow Gumbel statistics. We also provide more refined estimates for the asymptotic behavior of E(L_{n}) for random walks with step increments of finite variance.

Phase transitions of the typical algorithmic complexity of the random satisfiability problem studied with linear programming.

Here we study linear programming applied to the random K-SAT problem, a fundamental problem in computational complexity. The K-SAT problem is to decide whether a Boolean formula with N variables and structured as a conjunction of M clauses, each being a disjunction of K variables or their negations is satisfiable or not. The ensemble of random K-SAT attracted considerable interest from physicists because for a specific ratio αs = M/N it undergoes in the limit of large N a sharp phase transition from a satisfiable to an unsatisfiable phase. In this study we will concentrate on finding for linear programming algorithms "easy-hard" transitions between phases of different typical hardness of the problems on either side. Linear programming is widely applied to solve practical optimization problems, but has been only rarely considered in the physics community. This is a deficit, because those typically studied types of algorithms work in the space of feasible {0, 1}N configurations while linear programming operates outside the space of valid configurations hence gives a very different perspective on the typical-case hardness of a problem. Here, we demonstrate that the technique leads to one simple-to-understand transition for the well known 2-SAT problem. On the other hand we detect multiple transitions in 3-SAT and 4-SAT. We demonstrate that, in contrast to the previous work on vertex cover and therefore somewhat surprisingly, the hardness transitions are not driven by changes of any of various standard percolation or solution space properties of the problem instances. Thus, here a more complex yet undetected property must be related to the easy-hard transition.

Large deviations of the length of the longest increasing subsequence of random permutations and random walks.

We study numerically the length distribution of the longest increasing subsequence (LIS) for random permutations and one-dimensional random walks. Using sophisticated large-deviation algorithms, we are able to obtain very large parts of the distribution, especially also covering probabilities smaller than 10^{-1000}. This enables us to verify for the length of the LIS of random permutations the analytically known asymptotics of the rate function and even the whole Tracy-Widom distribution. We observe a rather fast convergence in the larger than typical part to this limiting distribution. For the length L of LIS of random walks no analytical results are known to us. We test a proposed scaling law and observe convergence of the tails into a collapse for increasing system size. Further, we obtain estimates for the leading-order behavior of the rate functions in both tails.

Replica symmetry and replica symmetry breaking for the traveling salesperson problem.

We study the energy landscape of the traveling salesperson problem (TSP) using exact ground states and a novel linear programming approach to generate excited states with closely defined properties. We look at four different ensembles, notably the classic finite dimensional Euclidean TSP and the mean-field-like (1,2)-TSP, which has its origin directly in the mapping of the Hamiltonian circuit problem on the TSP. Our data supports previous conjectures that the Euclidean TSP does not show signatures of replica symmetry breaking neither in two nor in higher dimension. On the other hand the (1,2)-TSP exhibits some signature which does not exclude broken replica symmetry, making it a candidate for further studies in the future.

Large deviations of convex hulls of self-avoiding random walks.

A global picture of a random particle movement is given by the convex hull of the visited points. We obtained numerically the probability distributions of the volume and surface of the convex hulls of a selection of three types of self-avoiding random walks, namely, the classical self-avoiding walk, the smart-kinetic self-avoiding walk, and the loop-erased random walk. To obtain a comprehensive description of the measured random quantities, we applied sophisticated large-deviation techniques, which allowed us to obtain the distributions over a large range of support down to probabilities far smaller than P=10^{-100}. We give an approximate closed form of the so-called large-deviation rate function Φ which generalizes above the upper critical dimension to the previously studied case of the standard random walk. Further, we show correlations between the two observables also in the limits of atypical large or small values.

Ising Ferromagnets on Proximity Graphs with Varying Disorder of the Node Placement.

We perform Monte Carlo simulations to determine the critical temperatures of Ising Ferromagnets (IFM) on different types of two-dimensional proximity graphs, in which the distribution of their underlying node sets has been changed systematically by means of a parameter σ. This allows us to interpolate between regular grids and proximity graphs based on complete random placement of nodes. Each edge of the planar proximity graphs carries a weighted ferromagnetic coupling. The coupling strengths are determined via the Euclidean distances between coupled spins. The simulations are carried out on graphs with N = 162 to N = 1282 nodes utilising the Wolff cluster algorithm and parallel tempering method in a wide temperature range around the critical point to measure the Binder cumulant in order to obtain the critical temperature for different values of σ. Interestingly, the critical temperatures depend partially non-monotonously on the disorder parameter σ, corresponding to a non-monotonous change of the graph structure. For completeness, we further verify using finite-size scaling methods that the IFM on proximity graphs is for all values of the disorder in the same universality class as the IFM on the two-dimensional square lattice.

Convex hulls of random walks in higher dimensions: A large-deviation study.

The distribution of the hypervolume V and surface ∂V of convex hulls of (multiple) random walks in higher dimensions are determined numerically, especially containing probabilities far smaller than P=10^{-1000} to estimate large deviation properties. For arbitrary dimensions and large walk lengths T, we suggest a scaling behavior of the distribution with the length of the walk T similar to the two-dimensional case and behavior of the distributions in the tails. We underpin both with numerical data in d=3 and d=4 dimensions. Further, we confirm the analytically known means of those distributions and calculate their variances for large T.