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.
Linear threshold rank on random social networks
Iacovissi, Laura
2020/2021
Abstract
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.File  Dimensione  Formato  

tesi_Iacovissi.pdf
accesso aperto
Dimensione
22.98 MB
Formato
Adobe PDF

22.98 MB  Adobe PDF  Visualizza/Apri 
The text of this website © Università degli studi di Padova. Full Text are published under a nonexclusive license. Metadata are under a CC0 License
https://hdl.handle.net/20.500.12608/21926