Random Graphs with Time-Varying Fitness

Abstract

The random graph is a mathematical model simulating common daily cases, such as ranking and social networks. Generally, the connection between different users in the network is established through preference, and this phenomenon leads to a power-law behaviour of the degree sequence of the random graph. Other than studying this feature, the thesis also focuses on the decay of degree sequence itself and the height of the random graph models. Researches are conducted on four kinds of random graph models, including two fully studied modes as benchmarks, the Preferential Attachment Model (PAM) and Random Recursive Tree (RRT), and another common model, the Bianconi-Barabási Model (BBM). Previous researches show that the degree sequence of PAM follows a power-law with coefficient -3, and the degree sequence of RRT has an exponential tail in contrast. In BBM, each node is assigned a fitness value from a certain distribution, once the node is generated, and researches show that the degree sequence of BBM follows a power-law with coefficient depending on the fitness distribution but close to the one of PAM. Then, the thesis aims to find a random graph model with fitness interpolating between RRT and PAM. Thus, a new Recursive Fitness Model (RFM) is developed by using a recursive formula to generate fitness values instead of the fixed distribution in BBM. By simulation we conjecture that the degree sequences of RFMs still follow a power-law with coefficient close to that of PAM. The simulation further shows an interesting phenomenon: a special linear height increment of a particular RFM, the Plus-1 model, appears, in contrast to other RFM models. Finally, the thesis invents a new Preferential Attachment Inverse Model (PAMinv) by using the expectation of degree sequence of PAM. Degree sequence of PAMinv shows a different behaviour from PAM and RRT, and it could be the tool to interpolate RRT from PAM.