Growth And Interdependence Of Complex Networks

This dissertation consists of studies of mathematical models for phase transitions and interdependence in complex networks. The studies contained take the first steps towards addressing three fundamental challenges that are faced when studying phase transitions in real systems: (i) it might not be feasible to identify an order parameter to detect the occurrence of the phase transition, (ii) real systems are often dynamic and continuously growing, and (iii) complex systems are often comprised of several types of relationships that are interdependent on each other. First, we decompose the entropy density of a system into different information measures, which can be used to identify the occurrence of a phase transition. We then focus on structural changes by analyzing the emergence of a giant component in a growing network in which edges are added according to a simple rule. Using master equations, we provide a rigorous analysis of the phase transition to show that critical behavior is dominated by growth when starting from a small set of seed nodes. Lastly, we study correlations present in the edge dynamics of networks with different types of relationships. We use a Markov chain based approach to extract correlations from longitudinal data. We provide a null model to help distinguish real correlations from those that occur due to chance. Understanding the correlations between the dynamics of different types of edges may enable us to discover novel phase transitions that might exist in these systems.