CS 60078 Complex Networks

(Spring Semester 2006)

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

Teaching Assisstant
Animesh Mukherjee (AM) Animesh.Mandal@iitkgp.ac.in

Resource Persons
Monojit Choudhury (MC)
Pabitra Mitra (PM)

Notices

27.04.2006 - The marks are out. You can check your marks. Your grade will be directly derived from the normalized column. If you are a borderline case, and if you have not submitted scribe/term project report, please submit the scribe/report now. This is your last chance. If your scribe is already submitted by somebidy else, contact me. You can also meet me anytime till 2nd May to see your answer script.
20.04.2006 - All scribes must reach by Saturday
20.04.2006 - Note the changes in scribe. New people are now assigned the task which the others failed eg, 4(16) means 4 has lost chance to 16
20.04.2006 - Many have not submitted the term report. Also please submit your program.
20.04.2006 - SUBMISSION of program applies to everybody, submit it like program_P(your project no).tar.gz eg program_P3.tar.gz
04.04.2006 - Scribes of Roll No 1 - 10 must reach by April 17. This is a hard deadline.
04.04.2006 - All the resources to be submitted by April 21. Please have a readme file and don't forget to put 'enough' comments on your program
04.04.2006 - Presentation on 18th April, 2.30 pm
04.04.2006 - Final report to be submitted by April 17. The final report to be written in latex and typically it should not be more than 15 pages. Please submit tex, figs, eps along with the final pdf file.
04.04.2006 - Scribes of Roll No 1 - 10 must reach by April 7 morning. This is a hard deadline.
03.03.2006 - Kindly prepare the scribes. Use latex. You will find the template here. Please submit the tex, ps and all the fig files in a tarball. Check your roll no.
26.02.2006 - Term project discussion on 1st March from 3pm in my room.

       Class Room/Hour
       Books
       Evaluation
       Lectures
       Syllabus
       Students List
       Term projects

Class Room/Hours

Lectures : Wed - 5, Thu - 4, Fri - 2
Room : CSE 320
Units : 3-0-0
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, 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
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. 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 (2004).
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, 167-256 (2003).

Evaluation

Mid-sem : 20
Term Project : 35
Class Performance : 5
End-sem : 40

Lectures

Term Projects

Every student has to carry out one term project. The term project consists of the following phases.

Abstract Submission (one page) - Stating clearly what is the plan. The plan should be detailed enough with adequate reference.

Discussion - There will be a discussion session where your plan will be refined.

Report - Final report of the project clearly stating your findings as well as future work.

Resource - Software developed, should be well documented.

Project 1

Title :- Bollywood Actors Network
Brief Introduction :- Build and analyse the network where each actor is a node. There is an edge between two nodes (read actors) if they have co-acted in a film. If they have co-acted in "w" films then "w" defines the weight of the edge.
Students :- 11, 15
Resource Persons :- AM, NG
Abstract
Final Report :-
Resource :-

Project 2

Title :- IIT Collaboration Network
Brief Introduction :- Build and analyse the network where each teacher is a node. There is an edge between two nodes (read authors) if they have co-authored a paper or have a joint student. If they have co-authored "w" papers then "w" defines the weight of the edge.
Students :- 5, 6, 10
Resource Persons :- NG
Abstract
Final Report :-
Resource :-
Reference :- The structure of scientific collaboration networks, M. E. J. Newman, Proc. Natl. Acad. Sci. USA 98, 404-409 (2001)

Project 3

Title :- Graphemic and Phonemic Networks
Brief Introduction :- Build and analyse the network where each word is a node. There is an edge between every two nodes (read words) of the network with edge-weight being the edit-distance between the words (both graphemic and phonemic). Each node also has a weight equal to its usage frequency.
Students :- 2, 3
Resource Persons :- AM, NG
Abstract
Final Report :-
Resource :-

Project 4

Title :- Web Social Network
Brief Introduction :- Extract graph structure of the orcut friends network by crawling orcut.com. Extract the subgraph where members follow certain criteria like age, location, preference.
Students :- 14, 16
Resource Persons :- PM, NG
Abstract
Final Report :-
Resource :-

Project 5

Title :- Topology Management
Brief Introduction :- Study what types of networks are stable against random failure as well as targetted attack
Students :- 4, 20
Resource Persons :- NG
Abstract
Final Report :-
Resource :-

Project 6

Title :- Word Network
Brief Introduction :- Build and analyse the network where each word is a node. There is an edge between two nodes (read words) if they co-occur in a sentence. The edge weight is defined as the weighted sum of the number of sentences in which they have co-occurred. Each node also has a weight equal to its usage frequency.
Students :- 7, 8
Resource Persons :- MC, AM
Abstract :-
Final Report :-
Resource :-

Project 7

Title :- Network of Musical Strings
Brief Introduction :- Build and analyse the network where each node is a musical note or a sequence of notes (note string of a given length). The edge weight is defined as the weighted average of the distance between the note strings in a musical composition.
Students :- 12, 17
Resource Persons :- MC, AM
Abstract
Final Report :-
Resource :-

Project 8

Title :- Airlines Network
Brief Introduction :- Build and analyse the network where each node is a city. There is an edge between two cities if there is a plane connection between them.
Students :- 13, 18
Resource Persons :- NG
Abstract
Final Report :-
Resource :-
Reference :- Small-world properties of the Indian Railway network, Parongama Sen and Subinay Dasgupta and Arnab Chatterjee and P A Sreeram and G Mukherjee and S S Manna, Physical Review E.

Project 9

Title :- Networks of NGO
Brief Introduction :- Build and analyse the network where each NGO is a node and there is an edge between two NGOs if they work in a same area. The number of areas they work together in defines the edge weight.
Students :- 1, 9
Resource Persons :- AM, NG
Abstract
Final Report :-
Resource :-