A brief history:

Social information networks, broadly defined, characterize attributes of individuals (e.g., interests, sociological profile) and the structure underlying their interactions (e.g., friendship, business relationship). Tradi- tionally it always was a latent force of sociological studies, and an important business factor in marketing, advertisement, and employment. In the 1990s, descriptive data of large information network became gradually available. A number of remarkable empirical observations, coupled with unified models to describe them across various application domains, gave birth to a new branch of natural physics. “Complexity” was put forward as their common denomina- tor.

Social information networks are now, and for a decade, an object of com- putational analysis. This analytical method claims that at the essence of un- derstanding these networks lies the way simple algorithms (similar to computer programs) are able to deduce from local information a global property that would otherwise require complete knowledge. In other words, whenever exhaus- tive enumeration is not cost-efficient or is simply infeasible (due to a lack of global data, or its overwhelming size), the answer to the “complexity” afore- mentioned lies in hidden structures that can be exploited by algorithms.

What is the position of social information networks today?

Today, it is hard not to see the impact of social information networks, for three reasons:
  1. The field and interest with these objects have grown with their sizes and scope, and their (partial) availability. For a company like Facebook, stor- ing and making available information networks relating a population com- parable to the world’s two largest country is by itself an active area of computer science research. For almost any large company, large data be- comes a commodity, and its ability to use them an important competitive factor.
  2. Whatever domains of applications where social information networks are integrated with technology, they typically change best practice. Busi- ness is conducted differently when the price or the service you receive depends on your friends. Media and entertainment are almost entirely redefined, incorporating contributions beyond the traditional content cre- ator/consumer model. Public issues like health, environment, economics and development are likely to quickly change as algorithms and computer systems using social information networks are introduced.
  3. In response to these new challenges, original computational methods were designed, together with a characterization of their result and speed. It significantly extended our understanding of the “Complexity” of social information network by revealing what any algorithms can and cannot do. It also impacted in many ways how information is exploited for several applications.


This course is an introduction to the computational analysis of social information network, with an emphasis on acquiring the set of theoretical skills that allow to mathematically justify the design of algorithmic methods. Examples where social informations are used by real systems will be given and analyzed, with some discussion on their broader impact.

During this course, students are expected to acquire (and will be evaluated on) the following set of skills:
  • Relate a phenomenon to common dynamics observed and analyzed among users of a social network dealing with information; develop a critical eye towards future research topics.
  • Formulate a problem dealing with social information in relation to ranking, algebraic spectral methods, and optimization.
  • Propose innovative solutions using simple distributed algorithms running on top of social networks, with a mathematical justification of their convergence.
In other words, if you wish to understand from first principles how search en- gine and recommender systems find relevant information, how does information
propagates over Facebook or Twitter, and what is the algorithmic potential of using social information, this course will help you find the answers.

The following topics, although they are related and will be mentioned at times, will not be covered or evaluated:
  • Strategic and game theoretic aspects of social information networks.
  • System principles to build and run large social networking services.
  • Machine learning and Bayesian inference on social information networks.

If you wish to acquire a deep knowledge in any of these three topics (which are covered in different lectures) this course may provide you with a good complement.