Extraordinary variability and sharp transitions in a maximally frustrated dynamic network*

Most previous studies of complex networks have focused on single, static networks. However, in the real world, networks are dynamic and interconnected. Inspired by the presence of extroverts and introverts in the general population, we investigate a highly simplified model of a social network, involving two types of nodes: one preferring the highest degree possible, and one preferring no connections whatsoever. There are only two control parameters in the model: the number of ``introvert'' and ``extrovert'' nodes, $N_I$ and $N_E$. Our key findings are as follows: As a function of $N_I$ and $N_E$, the system exhibits a highly unusual transition, displaying extraordinary fluctuations (as in 2nd order transitions) and discontinuous jumps (characteristic of 1st order transitions). Most remarkably, the system can be described by an Ising-like Hamiltonian with long-range multi-spin interactions and some of its properties can be obtained analytically. This is in stark contrast with other dynamic network models which rely almost exclusively on simulations.