Welcome to the "Introduction to Social Networks" Wiki

Listed as COMS 4995-1, Fall 2012, Columbia University
Instructor: A. Chaintreau,
T.A.: Chris Riederer
Mudd 545

This website provides information and teaching material for an introductory graduate course on social networks for students with a computer science or engineering background. Note that this primary target is not restrictive: students from other backgrounds (over three years, from economics, journalism and medical school) found this class useful as well.

On this website, you will be able to:
  • Find (on this page) a brief statement about the contents and objective of the course. More information (including all teaching materials) is available on the detailed content section of this site.
  • Find answers to Frequently Asked Questions about the class (typically logistics and grading); learn about Rules enforced.
  • Find a list of references pointing to classes with overlapping contents, a brief bibliography, tools and data-sets
  • Read about opportunities from nearby start-ups/projects related to social networks, connect with our online forum (identification required) or read our blog.

Objective of this course:

What is this class about?

Social network concepts are ubiquitous in the transformation of many commercial and public services today, and they become more and more common in many aspects of computing. The objective of this course is to introduce these concepts with two special focuses:
  • Interpret real-world phenomenon using elaborate concepts from social network analysis.
  • Design algorithms that exploit social properties to optimize system design, and justify their convergence and performance.
Said differently, this course will tell you a first answer to WHY and HOW computing methods that manipulate social networking concepts have been shown surprisingly efficient.

What is related but NOT covered in this class?

Note that this course does NOT cover some important aspects of dealing with social network and computation, in particular:
  • Game-theoretic and economic analysis of the role of social network is not covered in these lectures (but it will be occasionally mentioned, and some aspect will be covered in a upcoming advanced class)
  • How to build from a system point of view a social networking service (although the concepts you will learn in the class would be important to have in mind to properly design such a system).
  • How to analyze massive data sets using Hadoop or Map reduce, and how to conduct inference and machine learning on such data set. This topic is introduced through some examples, but it is too important by itself to be treated well during a general introductory course.
Note that these topics are not completely independent or in contradiction with the objective of this course, but they require complementary skills. If your long lived goal is to train on those skills, attending this introductory class will give more breadth in general concepts connected to these other important questions.

Who should take this class?

Whether you are considering working with social networks for your own research, find a job in an industry related to the social web, or broaden your horizon with what makes some algorithms in Facebook, Twitter, Google, Wikipedia work better, you will find in this class an introduction to big ideas behind networks and our social behaviors. You will have a chance to try these concepts for yourself through maths and programming projects. You will have a chance to discuss further development with the class and participate to the discussion through blogs.

Do I need to be a coder, or a theoretician, or both to succeed in this class?
This class is designed for students with an elementary background in discrete maths and a bit of programming experience. It's probably not a good idea to take this class if you have never seen a probability or a matrix, or if you have never touched a programming language at all. However, the level of requirement is quite minimal (see more detailed in the prequisite of our FAQ), so depending on your motivation, you may take a class about it in parallel, study some of these notions on your own or, of course, take the class later.

If you are still wondering how to judge if you can do it, I recommend the following
(1) have a look at a Chapter 2-3 from Easley-Kleinberg's book "Network Crowd and Markets" (available for free online), including the advanced material section. This is a very well written book, so you should be able to read it like a novel, and basically in an hour or perhaps two digest the contents pretty well. It you start encountering some difficulties in doing that quickly, then shoot me an email and we can discuss it further. It's also a great preparation for the class on Tuesday next week.
(2) attend the two first weeks as a test: I organize these 4 first classes on purpose as an increasing slope. By the time we get to the algorithmic analysis of small world (about Sep.13th), you will have been introduced to some of the most subtle concepts. If at this time you feel comfortable, that's a good sign because the class will move on to other topics and different tools, but not go to more difficult tools.
(3) look at the first assignment, and see if you can do that in a reasonable amount of time.

Contents and Organization:


The course is organized in 2 parts in which we combine description of social concepts, new algorithms, and case studies.

The first part "A - STRUCTURE" focuses on properties that characterizes the graph connecting individuals in various social (and other) applications. It answers the following questions:
  • How do we connect to each other in a graph (i.e., Why am I only separated from all Facebook users through very small number of hops, and why it matters)?
  • Why and how are large scale networks exhibiting super nodes (i.e., Should we expect very popular videos on YouTube)? and how can we extract the most important nodes out of a graph (i.e., as Google does for the web)?
  • What makes social networks divided? (i.e., How are my community, my Flickr images and Foursquare embedded in my social networks)?
  • How do social network behave in function of time (i.e., Is it normal that I feel evermore connected to everyone?).

The second part "B - DYNAMICS" focuses on interaction between individuals along the edge of a network.
  • How do epidemics spread (i.e., why are computer worm, and peer-to-peer networks, so efficient)?
  • How am I influenced by my friend (i.e., how to make a product viral)?
  • How sharing information with my friends allows to learn collectively (i.e., can 10,000 persons communicate and be wrong)?
  • Can I use my friends to measure social networks from my desktop (i.e., are social networking entirely closed or entirely open)?
  • Are social networks useful for the economy (i.e., Is is reasonable to pay $38 for a Facebook share?)


For more information about the content of the class, please visit the Detailed Content page.