CS 60078 Complex Networks

(Spring Semester 2008)

Niloy Ganguly (NG) niloy@cse.iitkgp.ernet.in

Teaching Assistant
Bivas Mitra (BM) bivas_mitra@yahoo.com



Final Grades are out!! Enjoy

1.  Allotment of term project done - 21.2
2. Abstract of term project due - 7.3.08
3. First draft of scribe due - 27.2.08

Class Room/Hours

Lectures : Wed - 3, Thu - 2, Fri - 4
Room : CSE 302
Units : 3-0-0
Credits : 3
Contact : Room #313 (CSE), Phone 3460


A list of useful books and materials is given below.

Related Course Webpages

Evaluation (Tentative)

Mid-sem : 20
Term Project/ (Scribes, Assignment) : 35
Class Performance (Attendance etc): 5 
End-sem : 40


4/1/2008                                     Introduction

9/1/2008 to 11/1/2008                Pajek

16/1/2008                                   Introductory graph theory, properties of adjacency matrix and incidence matrix, calculating diameter, shortest path.

17/1/2008                                   Introductory graph theory, planer graph, properties of planer graph, connected component, clique, k-plex,

18/1/2008                                   Centrality measures, degree centrality, closeness, betweenness, eigenvector centrality, analytical expressions.

24/1/2008                                   Searching the web, hubs and authorities, HITS algorithm, Page rank.

30/1/2008                                   Social network analysis, roles in network, concept of equivalence, structural similarity, Pearson correlation, Euclidian distance.

31/1/2008                                   Clustering coefficient, higher order clustering coefficients, Assortativity, automorphic equivalence, hierarchical clustering

6/2/2008                                     Community formation, Graph partitioning algorithm, sociological influence, new approaches, Keningham Lin algorithm, and         spectral bisection method

7/2/2008                                    Community finding algorithms, Wu-Huberman algorithm, Newman Girvan, Bridge edges, finding shortest path betweenness, spanning tree based approach.

8/2/2008                                    Community finding algorithms, random walker based approach, Raddicchi’s algorithm, Motif network

13/2/2008                                  Introduction to Random graphs, degree distribution, Erdos Renyi graph, scale free networks, construction of random graphs

14/2/2008                                 Concept of giant component, phase transition, size of the giant component, different properties of E-R graphs

15/2/2008                                 Generating function, Basic concepts and results, calculation of the moments

20/2/2008                                Generating function, power property, calculating the degree distribution of the first neighbors, number of second neighbors, calculation of component size distribution like H1(x) and H0(x).

5/3/2008                                  Generating function, deriving the condition of phase transition and emergence of giant component, calculation of the number of neighbors and average path length.  

06/03/2008                              Models of network growth, preferential attachment, Barabasi-Albert Model.

07/03/2008                              Barabasi-Albert Model., Price’s growth model

12/03/2008                              Generalized growth model, Kaprivsky-Render model, theory for sublinear and linear growth.

13/03/2008                              Kaprivsky-Render model, theory for sublinear and linear growth, Problems of Barabasi model

14/03/2008                              Growth in the rewiring environment, vertex copying model of network growth

19/03/2008                              Small World network, small world property, Watts and Strogatz model, – diameter, clustering cooefficient, no. of neighbors.

20/03/2008                              Small World, Newman and Watts model,  rewiring, connected caveman model – prisoner’s dilemma.

02/04/2008                              Kleinberg’s model, 2 d grid network as small world, Decentralized algorithm for search in 2 D grid network, processes on network.

03/04/2008                              Epidemics, SIS model, Epidemic threshold, modeling,  initial dynamics(butterfly effect)

04/04/2008                              Different models of epidemics, SIR, SIRS model.

09/04/2008                              Robustness of a network, degree independent and dependent failure, stability condition of an infinite graph

10/04/2008                              Stability condition for finite size graph, mathematical approximation of the deformed topology due to node disruption, percolation condition for finite size graph, percolation threshold.

11/04/2008                              percolation in finite graph for random failure and information sensitive attach, growth in bipartite networks





1. Scribes on basics of graph theory        04CS1014  

2. Scribe on Social Networks                  04CS1016 (new)

3. Scribe on community identification        04CS1029       

4. Theory of random graphs                     04CS3009

First draft due - 27.2.08, prepare scribe in latex (must)

5. Glossary of essential terms in CNT       04CS1015

6. Growth of Networks                            04CS1015

7. Small World                                          04CS1005  

8.  Pajec                                                    04CS1016

9. Epidemics on Network                         04CS1011

10. Resilience on Network                        04CS1029

11. Bipartite Network                                04CS1011


1. Assignment 1    04CS1014

2. Assignment 2    04CS3014

3. Assignment 3    04CS3009

4. Assignment 4    04CS1005

Term Projects

1. Search in small world networks.

2. Community Structure in networks - Developing and evaluating overlapping communities

3. Routing Strategy in complex networks

4. Study of the spectral plots of different connectivity matrices of a graph

5. Technique to calculate all eigenvalues of huge matrix

6. Hierarchical Model of Internet Topology

7. Classification of Edges in Citation Networks

8. Forming Random Graphs.

9. Routing Strategy in faulty hypercube networks

10. Finding standard measures of various real life networks

    Term Project and scribe allotment list