Application of statistical physics to random graph models of networks

This thesis deals with the application of concepts from statistical physics to the understanding of static and dynamical properties of random networks. The classical paradigm for random networks is the Erdos-Renyi (ER) random graph model denoted as G(N, p), in which a network of N nodes is created by placing a link between each of the N(N--1)/2 pairs of nodes with a probability p. The probability distribution of the number of links per node, or the degree distribution, is a Poissonian distribution in the limit of asymptotic network sizes. Recent investigations of the structure of networks such as the internet have revealed a power law in the degree distribution of the network. The question then arises as how the presence of this power law affects the behavior of static and dynamic properties of a network and how this behavior is different from that seen in ER random graphs. In general, irrespective of other details of their structure, networks having a power law degree distribution are known as "scale-free" (SF) networks. In this thesis, we focus on the simplest model of SF networks, known as the configuration model. In the first chapter, we introduce ER and SF networks, and define central concepts that will be used throughout this thesis.; In the second chapter we address the problem of optimal paths on weighted networks, formulated as follows. On a network with weighted links where link weights represent transit times along the link, we define the optimal path as the path between two nodes with the least total transit time. We study the scaling of optimal path length ℓopt as a function of the network size N, and as a function of the parameters in the weight distribution. We show that when link weights are highly disordered, only paths on the "minimal spanning tree"---the tree with the lowest total link weight---are used, and this leads to a crossover between two regimes of scaling behavior for ℓopt. For a simple distribution of link weights, we derive for ER and SF networks, the scaling of the crossover point with the network size N, and propose an ansatz for ℓopt, that we verify numerically.; The subject of the third chapter is the study of structural bottlenecks in networks and their effect on the onset of congestion in the network, given an assignment of flow paths between each pair of nodes. We study a model of packet transport on a network where new packets are created with probability gamma per unit time. Above a critical value gammac, the congestion threshold, there is an onset of congestion in the network. We derive an upper bound gammaT for this threshold, which depends on the structure of the graph, and which holds for arbitrary assignments of flow paths. We show that when shortest paths (SP) are assigned as flow paths, the congestion threshold, gSPc , is significantly lower than gammaT. By providing an example path assignment which results in congestion threshold closer to the bound gammaT than gSPc , we strengthen our conjecture that shortest path assignment may not be the optimal flow path assignment. We also show that the gamma T for SF networks is lower than that for ER graphs, indicating that bottlenecks in SF networks are worse than those in ER graphs. Finally, in the fourth chapter, we study the resilience of networks to random node failures by equating the process of random failures to a percolation process. We use this analogy to determine optimally robust configurations for a network with a fixed number of nodes and edges, and show that a random network with a bimodal degree distribution achieves the best results.