Complex Networks (CS60078)

Spring Semester 2016

Instructor: Animesh Mukherjee (animeshm@cse.iitkgp.ernet.in)

Adjunct faculty: Matteo Marsili, ICTP, Trieste, Italy

Teaching Assistant: Abhik Jana (abhikjana1@gmail.com) and Soumya Sarkar (portkey1996@gmail.com)

Class Timings: WED (12:00-12:55), THURS (11:00-11:55), FRI (09:00-09:55)
Location: Room 107, CSE
Ofice of the Instructor: Room 121, CSE

Course Rules
  1. A blog discussing everyday course lectures (each day there will be one or two students who will be in-charge of rolling on the discussion) shall be hosted. This should be a real discussion of the topic taught and not just a reiteration of "classroom notes". New materials can also be exchanged over the blog. Any malpractice on the blog shall lead to immediate de-registration of the candidate trapped. The TA shall co-ordinate the blog.
  2. Group email shall be hosted.
  3. Term projects (Results and report before midsem; viva-voce and final report before endsem).
  4. Required attendance (>80%). Attendance shall be marked twice. Once before midsem and once before endsem. Failure to maintain the required attendance shall directly lead to loss of marks and de-registration.

Marks Division
  1. Midsem: 20%
  2. Term project: 30%
  3. Attendance and class performance: 10%
  4. Contribution to the blog: 5%
  5. Endsem: 35%

Blog: Filter Bubble!!

Blog Assignments

Term Projects

References:
  1. Networks: An Introduction, Oxford University Press, Oxford, 2010.
  2. Evolution of Networks, Oxford University Press, Oxford, 2003.
  3. The structure and function of complex networks, SIAM Review 45, 167-256, 2003.
  4. Statistical mechanics of complex networks, Rev. Mod. Phys., 74(1), 2002.
  5. Further references can be found on the course page of Prof. Niloy Ganguly.
Course Outline
  1. Introduction
    1. What is a complex system?
    2. Abstraction as a network -- examples for motivation
  2. Basic metrics
    1. Degree distribution (DD),
    2. Clustering coefficient (CC),
    3. Centrality,
    4. PageRank,
    5. Hubs and authorities,
    6. Bib-coupling,
    7. Co-citation index,
    8. Edge reciprocity,
    9. Rich club phenomenon
  3. Social Network
    1. Homophily
    2. Cohesiveness
      1. Cliques,
      2. Clans,
      3. Clubs,
      4. Plex,
    3. Equivalence of ties,
    4. Ego-centric networks
  4. Community Structures
    1. Hierarchical Agglomerative
    2. Edge betweenness
    3. Modularity
    4. Blondel et al. (Louvain)
    5. A briefing of linear algebra techniques and spectral methods (material1, material2, also available at http://www.cs.berkeley.edu/~demmel/cs267/lecture20/lecture20.html)
    6. Permanence
  5. Citation Networks
    1. Rise and fall of CS fields
    2. Interdisciplinarity of CS fields
    3. Temporal structures of citation profiles
    4. Citation count prediction
    5. Ancient Papers
    6. Co-authorship circles
  6. Economic and financial network analytics (slides have been already passed to you)
  7. Graph mining, Motifs
  8. Measuring user engagement