DIFFUSIVE PROCESSES ON SOCIAL GRAPHS

Social networks are emerging as one of the most revolutionary innovations of the last decades. Their impact in politics, social behaviour, economics is just at the very beginning and yet a better understanding of their structure is an urgent task. Despite the importance of social networks is so self-evident, a scientific study of these objects have to face issues that could appear insurmountable. First of all even a definition, in a mathematical sense, of what a social network is does not exist. Secondly, even assuming we agreed on some definition, social networks have grown at an exceptional rate. Nowadays a typical social network have tens to hundreds millions of nodes and billions of arcs, so any algorithm that is more than linear (or linearithmic) in the number of arcs is out of question. Lastly, evaluating the performances of new techniques is not a trivial task since the majority of meta-data about social networks are industrial secrets of great economical value and are treasured as such. In this thesis we present several results that, far from solving these problems, try to push a little forward our understanding of the very structure of social networks. The main theme of all the presented results is that much can be understood of the structure of a graph when we let some diffusive process evolve on it. Diffusive processes are inherently local and often randomized: each node of the graph chooses how to update its state just looking at its neighbours. Randomness is usually crucial in the initialization phase and in the update order. These kinds of processes have two major advantages: each round is linear in the number of arcs and they do not require that the whole graph is loaded into main memory. Thus they are perfect candidates for the analysis of huge networks.