CS 60078 Complex Networks

Notices

Midsem marks out

Term Project 2nd assessment marks out

Term Project 1st assessment marks out

Term Project Allotted!!!

Term Project, Survey, Scribe proposal

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

• Guido Caldarelli, Scale-Free Networks, Oxford University Press, Oxford (2007)
• 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 Clustering Coefficient
• Higher order clustering coefficients in BarabŽasi-Albert networks

For Spectral Graph Theory
• Linear Algebra and its Applications, Gilbert Strang (Chapter 5)  http://math.mit.edu/linearalgebra/ila0601.pdf, http://web.mit.edu/18.06/www/Video/video-fall-99-new.html (Lecture 21)
• Lectures by Daniel Spielman.
• Banerjee and Jost, 2007
• Mukherjee, Choudhury and Kannan
  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
• Kernigham Lin Algorithms xerox
  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
• Albert-LŽaszlŽo BarabŽasi and RŽeka Albert, Emergence of Scaling in Random Networks
• Albert-LŽaszlŽo BarabŽasi and RŽeka Albert, Topology of evolving networks: local events and universality
• Ravi Kumar Prabhakar Raghavany Sridhar Rajagopalan D Sivakumar Andrew Tomkins Eli Upfalz, Stochastic models for the web graph (Vertex Copying Model)
• Jon M Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan and Andrew S Tomkins,  The Web as a graph measurements models and methods (Vertex Copying)
  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).
• Connected Caveman Problem - Notes
• J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 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

Lectures

Slides of Centrality,

Slide on Spectral Analysis

Slides on Random Walk

Slides on Bipartite Networks 1, 2, 3

Video Lecture - http://10.35.32.102/

Scribes

Assignments

Assignment 1 (Graph Theory)

Assignment 2 (Social Networks)

Assignment 3 (Spectral Graph Theory)

Assignment 4 (Random Graph Theory)

Term Projects