Social Network Analysis and Time Varying Graphs

Abstract

The thesis focuses on the social web and on the analysis of social networks with particular emphasis on their temporal aspects. Social networks are represented here by Time Varying Graphs (TVG), a general model for dynamic graphs borrowed from distributed computing.

In the first part of the thesis we focus on the temporal aspects of social networks. We develop various temporal centrality measures for TVGs including betweenness, closeness, and eigenvector centralities, which are well known in the context of static graphs. Unfortunately the computational complexities of these temporal centrality metrics are not comparable with their static counterparts. For example, the computation of betweenness becomes intractable in the dynamic setting. For this reason, approximation techniques will also be considered. We apply these temporal measures to two very different datasets, one in the context of knowledge mobilization in a small community of university researchers, the other in the context of Facebook commenting activities among a large number of web users. In both settings, we perform a temporal analysis so to understand the importance of the temporal factors in the dynamics of those networks and to detect nodes that act as “accelerators”.

In the second part of the thesis, we focus on a more standard static graph representation. We conduct a propagation study on YouTube datasets to understand and compare the propagation dynamics of two different types of users: subscribers and friends. Finally, we conclude the thesis with the proposal of a general framework to present, in a comprehensive model, the influence of the social web on e-commerce decision making.