Harrison Hartle

Harrison Hartle, P. L. Krapivsky, S. Redner et al.

In networks that grow by isotropic redirection (IR), a new node selects an initial target node uniformly at random and attaches to a randomly chosen neighbor of the target. The emerging networks exhibit leaf proliferation, in which the number of nonleaves scales sublinearly as $N^μ$ and the degree distribution has an algebraic tail with exponent $1+μ$. To understand these mysterious properties, we introduce a class of models with redirection to leaves whenever possible. The resulting networks exhibit qualitatively similar phenomenology to IR networks, but avoid the inherent non-locality of the IR growth rule. These networks admit an analytical description of the leaf degree distribution, from which we extract the exponent $μ$.

Marcus J. Hamilton, Abhishek Yadav, Harrison Hartle et al.

Human societies continuously transform scattered information into collective judgments and coordinated action, whether through markets discovering prices, governments allocating resources, communities enforcing norms, or science converging on reliable claims. Importantly, the computational difficulty of collective decision-making, particularly the time and communication required to reach solutions, imposes fundamental constraints on social organization. While theoretical computer science offers formal tools for analyzing such problems, for instance, by analyzing resource requirements, including time and memory, surprisingly, there is no domain of social science that focuses on the nature of computation in the human world. This perspective argues that we now have the opportunity to deploy these computational frameworks to study human social organization, opening research directions at the intersection of computer science and social science. We highlight core social phenomena that can be framed as computational, including (i) distributed consensus and coordinated action, (ii) societal restructuring with scale, (iii) hierarchical and modular structure, and (iv) externalized memory systems. We identify several concepts from theoretical computer science that may provide insight into these phenomena, especially emphasizing more recently developed approaches beyond the paradigm of Turing~Machines and worst-case computational complexity.

Filippo Radicchi, Dmitri Krioukov, Harrison Hartle et al.

Existing information-theoretic frameworks based on maximum entropy network ensembles are not able to explain the emergence of heterogeneity in complex networks. Here, we fill this gap of knowledge by developing a classical framework for networks based on finding an optimal trade-off between the information content of a compressed representation of the ensemble and the information content of the actual network ensemble. In this way not only we introduce a novel classical network ensemble satisfying a set of soft constraints but we are also able to calculate the optimal distribution of the constraints. We show that for the classical network ensemble in which the only constraints are the expected degrees a power-law degree distribution is optimal. Also, we study spatially embedded networks finding that the interactions between nodes naturally lead to non-uniform spread of nodes in the space, with pairs of nodes at a given distance not necessarily obeying a power-law distribution. The pertinent features of real-world air transportation networks are well described by the proposed framework.