Complex Networks (CS60078)

Spring Semester 2015

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

Teaching Assistant: Abhijnan Chakraborty (chakraborty.abhijnan@gmail.com) and Suman Kalyan Maity (sumankalyannit@gmail.com)

Class Timings: Wednesday 11:30 -- 12:25 (AN), Thursday 10:30 -- 11:25 (AN) and Friday 9:30 -- 10:25 (AN)
Location: Room 107, CSE
Ofice of the Instructor: Room 102, CSE

Course Rules
  1. A blog discussing everyday course lectures (each day there will be one or two students who will be incharge of rolling on the disucssion) shall be hosted. This should be a real discussion of the topic taught and not just a reiteration of "clasroom notes". New materials can also be exchanged over the blog. Any malpractice on the blog shall lead to immeadiate deregistration 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. Failue to maintain the required attendance shall directly lead to loss of marks and deregistration.

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: Small World!!

Term Projects Flipkart to sponsor prizes worth USD 1000 to the best three 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 Dr. 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. Assortativity,
    5. Rich club coefficient,
    6. Strength,
    7. Weighted CC,
    8. Entropy of DD,
    9. Edge reciprocity,
    10. Matching index
  3. Social Network
    1. Homophily
    2. Cliques,
    3. Clans,
    4. Clubs,
    5. Plex,
    6. Bib-coupling,
    7. Equivalence of ties,
    8. 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)
  5. Random Graphs/Generating Functions
    1. Random Graph Models
    2. Generating functions
    3. Second Neighbors and Component Sizes
  6. Growth Models
    1. Barabasi-Albert Model, also see The original paper
    2. Price's Model
    3. Small-world model
    4. Vertex copying, also see Stochastic models for the web graph (Vertex Copying Model)
    5. Bipartite network models
  7. Percolation Theory
  8. Epidemic Models -- SIS, SIR
  9. Search on networks
  10. Graph Mining -- Frequent Subgraphs, Motifs