The advent of new information and communication technologies such as the Internet and mobile telephones is the driving force of important paradigm shifts, not only in Computer Science. In the pre-Internet era computers were stand alone machines, whose computing cycles were devoted to number crunching. Today, most of the computer time in the world, a power orders of magnitude greater than ever before, is mainly used to shuffle information around. The urge to communicate is so powerful that what we witness today is the convergence between social and technological networks: human relations are becoming more and more interlaced with communication technologies, and it seems inevitable that this trend will acquire further momentum in the future. In this scenario, technologically-mediated social networks (TMSNs) play a pervasive and prominent role, and will continue to do so in the near future. Nowadays perhaps billions of people interact with the Internet on a daily basis and while doing so
they leave digital footprints that are transformed into various types of TMSNs. TMSNs can be explicit, as in the case of popular social networking services such as Facebook or Google+, or, more often than not, implicit, as in the case of the menagerie of TMSNs that are constantly processed by web companies with the goal of improving the services they provide and, crucially, to monetize. TMSNs are a gold mine for scientists and companies alike: they are a field where social sciences and information management come to meet, fruitfully interacting and providing each other with a theoretical foundation and new computational tools. We expect this interaction to keep growing in the immediate future.
The abundance of data representing important human activities, from mobility to social interaction, and the ability to distill relevant information and manipulate it efficiently is causing an important paradigm shift in the social and computing sciences, while it can be a matter of life and death for a world leading technological company. This vast endeavor, the ability to cope with and efficiently process large-scale social networks, is intrinsically algorithmic. Algorithmic techniques are one of the linchpins of innovation and often are key enablers for the various types of web services that are offered by world leading companies vying for world prominence by offering various kinds of web services, from search engines and content delivery networks to computational advertising, maps, chat services and recommendation systems. In all these examples, we see again and again that sophisticated algorithmic techniques are one of the key ingredients. The goal of this project is to tackle some fundamental
algorithmic questions related to large-scale TMSNs, both from a foundational and from an application viewpoint.
The broad context of our project is defined by the following research directions:
1. To develop new compression algorithms for large scale TMSNs
2. To tackle a set of relevant open problems, described below, related to the diffusion of information and the spread of influence within TMSNs
3. To improve the state of the art for a few key computational advertising problems related to electronic auctions
4. To develop novel algorithms for predicting the evolution of TMSNs
The techniques used will be those of the theory of algorithms that appear more relevant to the problems at hand and that proved so successful in developing key web applications so far: machine learning, algoritmic game theory, randomized algorithms and the probabilistic analysis of algorithms, stochastic modelling, the theory of fault-tolerant distributed algorithms, and the design and analysis of algorithms and data structures. Our project spans the entire spectrum, from the development of novel results of foundational relevance, all the way down to the efficient implementation of novel protocols and algorithms.
Algorithms for TMSNs have a dual nature. From the point of view of "computational sociology" many phenomena of interest in the context of social networks can be couched and fruitfully studied in algorithmic terms. But such algorithms can also be understood in a purely "technological" sense as communication protocols and give raise to new applications. This dual nature will be a running theme of this project.