CS 60078 Complex Networks

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 write-up 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/Hour
•        Books
•        Evaluation
•        Lectures
•        Syllabus
•        Students List
•        Assignments
•        Term projects

• 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
• 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. 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).
• 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, 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).
  For epidemics
• SIR Study material
• SIS Study material
• R. Pastor-Satorras 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

• Mark Newmann
• Lada Adamic
• Jon Kleinberg
• Duncan Watts
• Panayiotis Tsaparas
• Aurel A. Lazar
• Douglas R. White

1. 04.01.07 - Introduction,
2. 08.01.07 - Graph Theory - Adjacency Matrix, Shortest Path, Incidence Matrix, Directed Graph, Connected Component, Rank - 1
3. 09.01.07 - Graph Theory, Centrality (Scribe Graph Theory Basics ) - 5
4. 11.01.07 - Centrality, Eigenvector Centrality
5. 15.01.07 - Page Ranking Algorithm  (Scribe Centrality to Page ranking ) - 5 
6. 16.01.07 - Core, Cliques and Clan (Scribe on Core, Cliques and Clan) - 16
7. 18.01.07 - Equivalence
8. 22.01.07 - Equivalence
9. 25.01.07 - Equivalence (Scribe on Equivalence) - 16
10. 29.01.07 - Small world properties
11. 01.02.07 - Assortativity (Scribe for last two class) - 3
12. 05.02.07 - Term project discussion
13. 06.02.07 - Community Identification - (Spectral Bisection and Keningham Lin Algorithm)
14. 08.02.07 - Community Identification - (Wu-Hubermann algorithm)
15. 12.02.07 - Community Identification - (Michel Girvan and Radichchi ALgorithm)
16. 13.02.07 - Pajek (AM)
17. 15.02.07 - Community Identification  (Scribe for community identification) - 1
18. 26.02.07 - Random Graphs
19. 27.02.07 - Models of network – Random graph, E-R graph
20. 01.03.07 - Construction of Random graph (etc) (Scribe on random Graphs - 13)
21. 05.03.07 - Methods (Algorithms) of construction of Random graphs. Introduction to Generating function and Go(x) and moments.
22. 06.03.07 - Generating Functions - Degree sequence
23. 08.03.07 - Generating Functions - Distribution of second neighbors
24. 12.03.07 - Generating Functions - Special degree distribution
25. 13.03.07 - Generating Functions - Component Size
26. 15.03.07 - Pajek (AM) (Scribe on Pajek - 11)
27. 19.03.07 - Generating Function - Component Size
28. 20.03.07 - Generating Function - Component Size, Evolution Model (Scribe on Generating Functions - 9)
29. 23/03/07 - Evolution of networks, Preferential attachment, Random attachment
30. 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.
31. 27/03/07 - Sub-linear, Linear, Super-linear1, Super-linear growth.
32. 02/04/07 - Small World Network
33. 03/04/07 - Connected Caveman Problem
34. 05/04/07 - Watts Model, Newman Model, Klienberg Model etc. (Scribe on power-law and Small world - 14)
35. 08.04.07 - Epidemics - SIR Model
36. 09.04.07 - Epidemics - SIS Model
37. 10.04.07 - Epidemics
38. 16.04.07 - Epidemics in powerlaw network
39. 17.04.07 - Search in Network (Scribe on Epidemics and search - 8)
    
    

Assignments

1. Assignment I - Assignment on Social Networks  (2,5)

Solutions (partial): 2    5    10
2. Assignment II - More Assignments on Social Networks (3,7,16)

Solutions (partial): 3    7    16
3. Assignment III - Assignment on Random Graphs (11, 13)

Solutions (partial): 11    13
4. Assignment IV - Assignment on generating function (6)

Solutions: Not Submitted
5. Assignment V - Assignment on growth and power-law (15)

Solutions: 15
6. Assignment VI - Assignment on small-world and powerlaw (12,18)

Solutions (partial): 12    18

 

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.

  List of Term Projects

  1. Dynamical networks of moving agents
  2. Complex networks in biology: enzymes - metabolic pathways network
  3. Complex networks in biology: protein - protein interaction network
  4. Improving robustness of existing networks
  5. Studies on Orthographic Networks
  6. Edge weight revision for semantic net
  7. Comparing different clustering algorithms on weighted networks through task completion (task being Part Of Speech tagging for English)
  8. Gradient based search of multiple targets
  9. Opinion and Friendship Network
  10. Community formation in networks
  11. Survey of Biological Network