Linear threshold rank on random social networks

The Linear Threshold Rank (LTR) is a centrality measure based on the Linear Threshold Model for influence spread. In this thesis we study the LTR on two random graph models: the Erdös–Rényi Graphs and the Random Geometric Graphs. The main focus is on the impact the threshold definition has on the algorithm output. Two kind of deterministic thresholds are considered: a natural one, the percentage of neighbours that must be active; an approximation of the first one, that replaces the number of neighbours with the maximum number of connections a node can have. The experiments show similar behaviors for the two thresholds on both models (directed and undirected), even if the approximated version resulted faster. We notice some interesting properties with phase transitions. It is also observed that, in the connected regime and with an increasing percentage value in the threshold definition, the metric goes from being maximum to count only the nodes in the initial activation set. In correspondence of this change in the metric value, the maximum levels have a peak and the ranking assumes values in a larger range. After the experiments discussion, some theoretical results are proved only for the Erdös–Rényi model.