CS 60078 Complex Networks
(Spring Semester 2007)
Theory
Niloy Ganguly (NG) niloy@cse.iitkgp.ernet.in
Teaching Assistant
Animesh Mukherjee (AM) Animesh.Mandal@iitkgp.ac.in
Resource Persons
Monojit Choudhury (MC)
Bivas Mitra (BM)
Notices
 18.04.07  ALL
SCRIBES AND ASSIGNMENTS SHOULD REACH BY 22nd. EXTREMELY STRICT DEADLINE
 10.04.2007  Term Project Viva on 18.04.07, 7.30 pm . You have to submit a
writeup in latex and also the source code and data repository (if any) you
have built.
 21.03.2007  All pending assignments have to be finished by 1st April.
This include people who have submitted assignments on paper. It should be
resend electronically.
The scribes submitted till now are below quality. Please check the
Notice for proper guidance of scribe. Each one who submitted
scribe will be
individually approached for rewriting.
For the next four days I will take attendance. Absence in these class
will surely result in deregistration.
Hardly anybody has come for round 2 discussion. Last date is Friday
this week. Otherwise you get a zero
 21.03.2007  The following guidelines should be
maintained while scribing.
Since scribing is not just copying whatever is written on the class board
therefore one should provide,
1. At least a small background for each of the topic that is being taught.
This can be done by a little amount of literature survey for each of the
topics. However it should not be just a copy from the source article.
For instance, when one is explaining a community finding
algorithm there should be,
i) A small description of the algorithm with proper
references,
ii) At least one small example graph on which the run of the
algorithm is explained.
2. One should also try to enumerate the significance of a certain topic (may
be with examples) wherever necessary. (This is required in the social network
analysis type of stuffs).
 28.02.2007  2nd Project meeting, by 16th March.
Detailed Plan and initial results to be shown.
 28.02.2007  Midsem Marks are out !!
 15.02.2007  All scribing, Assignments should be submitted by 20th
February. THIS IS A HARD DEADLINE.
 06.02.2007  Term Project assigned
 31.01.2007  2,5,16 are assigned work. Kindly finish them ASAP.
 16.01.2007  Kindly prepare the scribes using latex. You will find the template
here. Please submit the tex, ps and all the fig files in a tarball.
Check your roll no.
 16.01.2007  You will be deregistered if you are absent for consecutive three
days..
Class Room/Hours
Lectures : Mon  4, Tue  2, Thu  5
Room : CSE 302
Units : 300
Credits : 3
Contact : Room #313 (CSE), Phone 3460
Books
A list of useful books and materials is given below.
 S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks, Oxford University Press, Oxford (2003)
 M. E. J. Newman, The structure and function of complex networks, SIAM Review 45, 167256 (2003).
 R. Albert and A.L. Barabasi Statistical mechanics of complex networks. Rev. Mod. Phys., Vol. 74, No. 1, January 2002.
 Narsingh Deo, Graph Theory Prentice Hall India.
For Social Networks
 Robert A. Hanneman Introduction to Social Network Methods

Martin
Everett,
Stephen P. Borgatti.
Extending Centrality

Martin
Everett,
Stephen P. Borgatti.
Computing Regular
Equivalence: Practical and Theoretical Issues
For Assortativeness
 Assortative mixing in
networks, M. E. J. Newman, Phys. Rev. Lett. 89, 208701
(2002).
 Mixing patterns
and community structure in networks, M. E. J. Newman and M. Girvan, in
Statistical Mechanics of Complex Networks, R. PastorSatorras,
J. Rubi, and A. DiazGuilera (eds.), Springer, Berlin (2003).
For Community Structure
 Detecting community structure in
networks, M. E. J. Newman, Eur. Phys. J. B 38, 321330
(2004).
 Finding Communities in
Linear Time: A Physics Approach Fang Wu, Bernardo A. Huberman

Defining and identifying communities in networks,
Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto,
Domenico Parisi

Finding and evaluating
community structure in network. M.E.J. Newman, M. Girvan
For Generating Function
 Random graphs with
arbitrary degree distributions and their applications, M. E. J. Newman,
S. H. Strogatz, and D. J. Watts, Phys. Rev. E 64, 026118
(2001).
For growth model
 M. E. J. Newman, The structure and function of complex networks,
SIAM Review 45, 167256 (2003).
 P. L. Krapivsky and S. Redner, Organization of growing random networks
For Small World  D. J. Watts, Small Worlds, Princeton Studies in Complexity

Models of the small world, M. E. J. Newman, J. Stat. Phys.
101, 819841 (2000).
For
epidemics
 SIR Study material
 SIS Study material
 R. PastorSatorras and A. Vespignani.Epidemic
dynamics and endemic states in complex networks
For Search
 Jon M. Kleinberg Authoritative
sources in a hyperlinked environment
Related Course Webpages
Evaluation (Tentative)
Midsem : 20 (4)
Term Project : 35
Class Performance (Scribe, Assignment and Attendance): 10
Endsem : 35 (17)
Lectures
 04.01.07  Introduction,
 08.01.07  Graph Theory  Adjacency Matrix, Shortest Path, Incidence Matrix, Directed Graph, Connected Component, Rank  1
 09.01.07  Graph Theory, Centrality (Scribe Graph
Theory Basics )  5
 11.01.07  Centrality, Eigenvector Centrality
 15.01.07  Page Ranking Algorithm (Scribe
Centrality to Page ranking )  5
 16.01.07  Core, Cliques and Clan (Scribe on
Core, Cliques and Clan)  16
 18.01.07  Equivalence
 22.01.07  Equivalence
 25.01.07  Equivalence (Scribe on Equivalence) 
16
 29.01.07  Small world properties
 01.02.07  Assortativity (Scribe for last two
class)  3
 05.02.07  Term project discussion
 06.02.07  Community Identification  (Spectral Bisection and Keningham
Lin Algorithm)
 08.02.07  Community Identification  (WuHubermann algorithm)
 12.02.07  Community Identification  (Michel Girvan and Radichchi
ALgorithm)
 13.02.07  Pajek (AM)
 15.02.07  Community Identification (Scribe for
community identification)  1
 26.02.07  Random Graphs
 27.02.07  Models of network – Random graph, ER graph
 01.03.07  Construction of Random graph (etc)
(Scribe on random Graphs  13)
 05.03.07  Methods (Algorithms) of construction of Random graphs.
Introduction to Generating function and Go(x) and moments.
 06.03.07  Generating Functions  Degree sequence
 08.03.07  Generating Functions  Distribution of second neighbors
 12.03.07  Generating Functions  Special degree distribution
 13.03.07  Generating Functions  Component Size
 15.03.07  Pajek (AM) (Scribe on Pajek 
11)
 19.03.07  Generating Function  Component Size
 20.03.07  Generating Function  Component Size, Evolution Model
(Scribe on Generating Functions  9)

23/03/07  Evolution of networks, Preferential
attachment, Random attachment

26/03/07  Growth of networks, Emergence of power law.
Price model, derivation of degree distribution using beta and gamma function
in discrete growth model.
 27/03/07  Sublinear,
Linear, Superlinear1, Superlinear growth.
 02/04/07  Small World Network
 03/04/07  Connected Caveman Problem
 05/04/07  Watts Model, Newman Model, Klienberg Model etc.
(Scribe on powerlaw and Small world  14)
 08.04.07  Epidemics  SIR Model
 09.04.07  Epidemics  SIS Model
 10.04.07  Epidemics
 16.04.07  Epidemics in powerlaw network
 17.04.07  Search in Network (Scribe on
Epidemics and search  8)
 Assignment I  Assignment on Social
Networks (2,5)
Solutions (partial):
2 5
10
 Assignment II  More Assignments on
Social Networks (3,7,16)
Solutions (partial):
3 7
16
 Assignment III  Assignment on
Random Graphs (11, 13)
Solutions (partial): 11
13
 Assignment IV  Assignment on
generating function (6)
Solutions: Not
Submitted
 Assignment V  Assignment on growth
and powerlaw (15)
Solutions:
15
 Assignment VI  Assignment on
smallworld and powerlaw (12,18)
Solutions (partial):
12 18
Every student has to carry out one term project. The term project consists of the
following phases.