The course is made of three parts
  1. Introduction: The first lecture aims at getting yourself acquainted with social information network and developing a critical eye towards research in this domain.
  2. Fundamentals: In a series of 7 lectures, the course will cover a series of classical results that form the core of our current understanding of social information network. Practice will be encouraged by homework.
  3. Empirical studies and advanced topics: The last 6 lectures are devoted to recent studies on online social networks (4 lectures) and some advanced topics (2 lectures). By nature this part covers less mature material, which are more prone to lead to a promising research direction. Highly interactive, each lecture will be organized with a set of recent research papers and a presentation and discussion where students will be expected to answer some challenges and open ended questions.

Date of Lecture
Brief Description
Scribing + Practice Exercice
Lecture materials and associated bibiography
Thursday, January 20th
Introduction:
The role of Social Information Networks today.

Study of the Small world experiment:
  • Milgram's experiment and the “small-world” phenomenon,
  • Uniform Random graph,
  • The different roles of strong and weak ties,
  • A first model of augmented lattice
N/A
  • Introduction:



  • Study of the Small world experiment:




Milgram. The small world problem. Psychology today (1967)

Travers and Milgram. An experimental study of the small world problem. Sociometry (1969) vol. 32 (4) pp. 425-443

Granovetter. The strength of weak ties: A network theory revisited. Sociological theory (1983)

Watts and Strogatz. Collective dynamics of 'small-world'networks. Nature (1998)


Complete bibliography on small world:
Thursday, January 27th
  • Algorithmic Analysis of the small world phenomenon
  • The ubiquitous power law.

Scribes: Aditi Bhatnagar, Ari Golub


  • Algorithmic Analysis of the small world phenomenon


Kleinberg. The small-world phenomenon: an algorithm perspective. STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing (2000)

Complete bibliography on small world

  • The ubiquitous power law.


Newman. Power laws, Pareto distributions and Zipf's law. Contemporary Physics (2005) vol. 46 (5) pp. 323-351

Clauset et al. Power-law distributions in empirical data. SIAM review (2009) vol. 51 (4) pp. 661-703

Kumar et al. Stochastic models for the Web graph. Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on (2000) pp. 57 - 65

Faloutsos et al. On power-law relationships of the internet topology. Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication (1999) pp. 251-262

Complete bibliography on power laws:
Thursday, February 3rd
  • How do power-laws build up by reinforcement, optimization, artefacts?
  • Fragility of power law, inoculation. Addressing the long tail with replication.
Scribing:

Scribe: Bo Hyun Kim

  • How do power-laws build up by reinforcement?

Yule. A Mathematical Theory of Evolution, Based on the Conclusions of Dr. J. C. Willis, F.R.S. Philosophical Transactions of the Royal Society of London. Series BContaining Papers of a Biological Character (1925) vol. 213 pp. 21-87

Simon. On a Class of Skew Distribution Functions. Biometrika (1955) vol. 42 (3/4) pp. 425-440

Barabási and Albert. Emergence of scaling in random networks. Science (1999)

Kleinberg et al. The web as a graph: Measurements, models, and methods. Proceedings of the 5th annual international conference on Computing and combinatorics (1999) pp. 1-17

Kumar et al. Stochastic models for the Web graph. Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on (2000) pp. 57 - 65

Riordan and Bollobas. Robustness and vulnerability of scale-free random graphs. Internet Mathematics (2004)

Riordan and Bollobas. The diameter of a scale-free random graph. Combinatorica (2004)

Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Mathematics (2004) vol. 1 (2) pp. 226-251

  • Power law created by optimization, and how to best take advantage of the popularity power law by replication

Mandelbrot. An informational theory of the statistical structure of language. Communication Theory (1953) pp. 486--502

Fabrikant et al. Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet. ICALP '02: Proceedings of the 29th International Colloquium on Automata, Languages and Programming (2002)

Lv et al. Search and replication in unstructured peer-to-peer networks. SIGMETRICS '02: Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems (2002)

Cohen and Shenker. Replication strategies in unstructured peer-to-peer networks. SIGCOMM '02: Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications (2002)

  • Power law obtained by random stopping and artefacts:

Miller. Some effects of intermittent silence. The American Journal of Psychology (1957)

Lakhina et al. Sampling biases in IP topology measurements. INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies (2003) vol. 1 pp. 332 - 341 vol.1

Clauset and Moore. Accuracy and scaling phenomena in Internet mapping. Physical review letters (2005)

Achlioptas et al. On the bias of traceroute sampling. Journal of the ACM (2009) vol. 56 (4) pp. 1-28

Slides:

Complete bibliography:
Thursday, February 10th
  • life under the influence
  • Network effect
  • Contagion number and its relation with clusters
  • Maximizing the spread of influence


Scribe: Tingting Xu

  • life under the influence

Ryan and Gross. The diffusion of hybrid seed corn in two Iowa communities. Rural sociology (1943)

Coleman et al. The Diffusion of an Innovation Among Physicians. Sociometry (1957) vol. 20 (4) pp. 253-270

Asch. Opinions and social pressure. Readings about the social animal (1992)

Christakis and Fowler. The spread of obesity in a large social network over 32 years. New England Journal of Medicine (2007) vol. 357 (4) pp. 370

Christakis and Fowler. The collective dynamics of smoking in a large social network. New England journal of medicine (2008) vol. 358 (21) pp. 2249

Fowler and Christakis. Dynamic spread of happiness in a large social network: longitudinal analysis over 20 years in the Framingham Heart Study. BMJ (2008) vol. 337 (dec04 2) pp. a2338-a2338

  • The Network effect:

Granovetter. Threshold Models of Collective Behavior. The American Journal of Sociology (1978) vol. 83 (6) pp. 1420-1443

  • Contagion number and its relation with clusters

Morris. Contagion. The Review of Economic Studies (2000) vol. 67 (1) pp. 57-78

  • Maximizing the spread of influence

Kempe et al. Maximizing the spread of influence through a social network. KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (2003)

Kempe et al. Influential nodes in a diffusion model for social networks. Proceedings of 32nd International Colloquium on Automata, Languages and Programming (ICALP) (2005) pp. 1127--1138

Backstrom et al. Group formation in large social networks: membership, growth, and evolution. KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining (2006)

Mossel and Roch. Submodularity of Influence in Social Networks: From Local to Global. SIAM Journal on Computing (2010)

Slides:

Complete Bibliography:


Thursday, February 17th
  • Submodular set-function, and how they can allow to approximate optimization problem.
  • Models of influence for which the set of influenced node can be shown to be a submodular function of the initial set


Scribe: Fang Qian

(NB: No practice exercice for this lecture, but I recommend you go over
the proof again)
This course was focusing on two important results

  • Submodular set-function, and how they can allow to approximate optimization problem.
  • Models of influence for which the set of influenced node can be shown to be a submodular function of the initial set.

The arguments follow closely the
Kleinberg. Cascading behavior in networks: Algorithmic and economic issues. in Algorithmic game theory, (2007)

Slides:
Thursday, February 24th
  • Continuous models of epidemics
  • Discrete models of epidemics
  • Epidemic Algorithms and the effect of network topology

Scribe: Beomjoong Kwon

  • Continuous models of epidemics


  • Discrete models of epidemics


  • Epidemic Algorithms and the effect of network topology


Slides:
Thursday, March 3rd
  • Impact of network topology on gossip algorithm (Proof)
  • Algorithms to rank nodes based on topology

Scribe: Evangelia Skiani
Slides:
Thursday, March 10th
  • Proof of convergence of ranking algorithms
  • Application
Scribe: Nisha Ranga
Slides:
Thursday, March 24th
  • Briefing for the paper discussion and projects
Scribe: N/A
Slides:
Thursday
March 31st
Midterm
Scribe: N/A

Thursday, April 7th



Thursday, April 14th



Thursday, April 21th



Thursday, April 28th





Fundamentals

These are organized along four “trails”, corresponding to different computa- tional aspect of social information network:
• Popularity (Trail 1): What is the popularity profiles exhibited by items and nodes in a social or information network? Can we explain and exploit them?
• Spread (Trail 2): How do opinions and behavior spread by influence be- tween the nodes? Can we use this influence to one’s advantage?
• Epidemy (Trail 3): How do information or virus propagates along the edges of a network? Can we design algorithm to leverage it?
• Structures (Trail 4): Given a data sets describing a social information network, what are the underlying structures allowing to rank nodes, to map them according to similarity, and to partition them? How can such structure be extracted from large datasets?

Advanced topics

Thursday, March 24th:midterm
Thursday, March 31st-April 21th: Paper discussion
Empirical studies 1: Online social networks and their evolution (Facebook, Friendster)
Empirical studies 2: Communities and their evolution (Facebook)
Empirical studies 3: User behaviors and interactions (Twitter, Flickr)
Empirical studies 4: Content and social media (Blogs, Youtube, Digg)

Thursday, April 28th:Advanced topic
Advanced topic 1: Mobility and Space in social networks