CS 60078 Complex Networks
(Spring Semester 2007)
Niloy Ganguly (NG) firstname.lastname@example.org
Animesh Mukherjee (AM) Animesh.Mandal@iitkgp.ac.in
Monojit Choudhury (MC)
Bivas Mitra (BM)
- 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
write-up in latex and also the source code and data repository (if any) you
- 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
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
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
Lectures : Mon - 4, Tue - 2, Thu - 5
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.
- 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, 167-256 (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
Stephen P. Borgatti.
Stephen P. Borgatti.
Equivalence: Practical and Theoretical Issues
- Assortative mixing in
networks, M. E. J. Newman, Phys. Rev. Lett. 89, 208701
- Mixing patterns
and community structure in networks, M. E. J. Newman and M. Girvan, in
Statistical Mechanics of Complex Networks, R. Pastor-Satorras,
J. Rubi, and A. Diaz-Guilera (eds.), Springer, Berlin (2003).
For Community Structure
- Detecting community structure in
networks, M. E. J. Newman, Eur. Phys. J. B 38, 321-330
- 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,
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
For growth model
- M. E. J. Newman, The structure and function of complex networks,
SIAM Review 45, 167-256 (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, 819-841 (2000).
- SIR Study material
- SIS Study material
- R. Pastor-Satorras and A. Vespignani.Epidemic
dynamics and endemic states in complex networks
- Jon M. Kleinberg Authoritative
sources in a hyperlinked environment
Related Course Webpages
Mid-sem : 20 (4)
Term Project : 35
Class Performance (Scribe, Assignment and Attendance): 10
End-sem : 35 (17)
- 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) -
- 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
- 08.02.07 - Community Identification - (Wu-Hubermann algorithm)
- 12.02.07 - Community Identification - (Michel Girvan and Radichchi
- 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, E-R 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 -
- 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 - Sub-linear,
Linear, Super-linear1, Super-linear 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 power-law 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
- Assignment II - More Assignments on
Social Networks (3,7,16)
- Assignment III - Assignment on
Random Graphs (11, 13)
Solutions (partial): 11
- Assignment IV - Assignment on
generating function (6)
- Assignment V - Assignment on growth
and power-law (15)
- Assignment VI - Assignment on
small-world and powerlaw (12,18)
Every student has to carry out one term project. The term project consists of the