Computing on evolving social networks

Over the past decade, participation in social networking services has seen an exponential growth, so that nowadays most individuals are “virtually” connected to others anywhere in the world. Consistently, analysis of human social behavior has gained momentum in the computer science research community. Several well-known phenomena in the social sciences have been revisited in a computer science perspective, with a new focus on phenomena of emerging behavior, information diffusion, opinion formation and collective intelligence. Furthermore, the recent past has witnessed a growing interest in the dynamics of these phenomena and that of the underlying social structures. This thesis investigates a number of aspects related to the study of evolving social networks and the collective phenomena they mediate. We have mainly pursued three research directions. The first line of research is in a sense functional to the other two and concerns the collection of data tracking the evolution of human interactions in the physical space and the extraction of (time) evolving networks describing these interactions. A number of available datasets describing different kinds of social networks are available on line, but few involve physical proximity of humans in real life scenarios. During our research activity, we have deployed several social experiments tracking face-to-face human interactions in the physical space. The collected datasets have been used to analyze network properties and to investigate social phenomena, as further described below. A second line of research investigates the impact of dynamics on the analytical tools used to extract knowledge from social networks. This is clearly a vast area in which research in many cases is in its early stages. We have focused on centrality, a fundamental notion in the analysis and characterization of social network structure and key to a number of Web applications and services. While many social networks of interest (resulting from “virtual” or “physical” activity) are highly dynamic, many Web information retrieval algorithms were originally designed with static networks in mind. In this thesis, we design and analyze decentralized algorithms for computing and maintaining centrality scores over time evolving networks. These algorithms refer to notions of centrality which are explicitly conceived for evolving settings and which are consistent with PageRank in important cases. A further line of research investigates the wisdom of crowds effect, an important, yet not completely understood phenomenon of collective intelligence, whereby a group typically exhibits higher predictive accuracy than its single members and often experts. Phenomena of collective intelligence involve exchange and processing of information among individuals sharing some common social structure. In many cases of interest, this structure is suitably described by an evolving social network. Studying the interplay between the evolution of the underlying social structure and the computational properties of the resulting process is an interesting and challenging task. We have focused on the quantitative analysis of this aspect, in particular the effect of the network on the accuracy of prediction. To provide a mathematical characterization, we have revisited and modified a number of models of opinion formation and diffusion originally proposed in the social sciences. Experimental analysis using data collected from some of the social experiments we conducted allowed to test soundness of the proposed models. While many of these models seem to capture important aspects of the process of opinion formation in (physical) social networks, one variant we propose achieves higher predictive accuracy and is also robust to the presence of outliers.