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.

DIFFUSIVE PROCESSES ON SOCIAL GRAPHS / M. Rosa ; relatore: S. Vigna. Universita' degli Studi di Milano, 2012 Mar 06. 24. ciclo, Anno Accademico 2011. [10.13130/rosa-marco_phd2012-03-06].

DIFFUSIVE PROCESSES ON SOCIAL GRAPHS

M. Rosa
2012

Abstract

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.
6-mar-2012
Settore INF/01 - Informatica
VIGNA, SEBASTIANO
Doctoral Thesis
DIFFUSIVE PROCESSES ON SOCIAL GRAPHS / M. Rosa ; relatore: S. Vigna. Universita' degli Studi di Milano, 2012 Mar 06. 24. ciclo, Anno Accademico 2011. [10.13130/rosa-marco_phd2012-03-06].
File in questo prodotto:
File Dimensione Formato  
phd_unimi_R08197.pdf

accesso aperto

Tipologia: Tesi di dottorato completa
Dimensione 1.32 MB
Formato Adobe PDF
1.32 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/172444
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact