MSc Defence: Iterators and Densifiers for Complex Networks

MSc Candidate: Xiwen Tian

Supervisor: Dr. Anthony Bonato

Abstract: We investigate deterministic iterative models that generate increasingly dense graphs over time. Densification, observed in real-world networks such as financial systems and neural architectures, refers to the superlinear growth of edges relative to nodes. We begin by analyzing existing models, including the Iterated Local Transitivity (or ILT) model, the Iterated Local Anti-Transitivity (or ILAT) model, and the half-model, demonstrating their densification behavior and small-world characteristics. We then introduce three new densifier models: the k-deleted model, where new nodes connect to all but k existing nodes; the k-extension model, which adds nodes adjacent to k-subsets of existing nodes; and the J- ILT model, a generalization of ILT that introduces multiple clones per node. these models. Our findings contribute to the understanding of structural evolution in complex networks and suggest future directions for modeling systems with densification behavior.  Theoretical results establish densification and bounded-diameter properties for