Exploring the low-energy landscape of large-scale signed social networks.

Analogously to a spin glass, a large-scale signed social network is characterized by the presence of disorder, expressed in this context (and in the social network literature) by the concept of structural balance. If, as we have recently shown, the signed social networks currently available have a limited amount of true disorder (or frustration), it is also interesting to investigate how this frustration is organized, by exploring the landscape of near-optimal structural balance. What we obtain in this paper is that while one of the networks analyzed shows a unique valley of minima, and a funneled landscape that gradually and smoothly worsens as we move away from the optimum, another network shows instead several distinct valleys of optimal or near-optimal structural balance, separated by energy barriers determined by internally balanced subcommunities of users, a phenomenon similar to the replica-symmetry breaking of spin glasses. Multiple, essentially isoenergetic, arrangements of these communities are possible. Passing from one valley to another requires one to destroy the internal arrangement of these balanced subcommunities and then to reform it again. It is essentially this process of breaking the internal balance of the subcommunities which gives rise to the energy barriers.

Adaptation as a genome-wide autoregulatory principle in the stress response of yeast.

The gene expression response of yeast to various types of stresses/perturbations shows a common functional and dynamical pattern for the vast majority of genes, characterised by a quick transient peak (affecting primarily short genes) followed by a return to the pre-stimulus level. Kinetically, this process of adaptation following the transient excursion can be modelled using a genome-wide autoregulatory mechanism by means of which yeast aims at maintaining a preferential concentration in its mRNA levels. The resulting feedback system explains well the different time constants observable in the transient response, while being in agreement with all the known experimental dynamical features. For example, it suggests that a very rapid transient can be induced also by a slowly varying concentration of the gene products.

Determining the distance to monotonicity of a biological network: a graph-theoretical approach.

The authors use ideas from graph theory in order to determine how distant is a given biological network from being monotone. On the signed graph representing the system, the minimal number of sign inconsistencies (i.e. the distance to monotonicity) is shown to be equal to the minimal number of fundamental cycles having a negative sign. Suitable operations aiming at computing such a number are also proposed and shown to outperform all algorithms that are so far existing for this task. [Includes supplementary material].