Course

Course Syllabus

Graphs and Networks- Review of basic graph theory, Mathematics of networks- Networks and their representation, Graph spectra, Graph Laplacian, The structure of complex networks, Clustering, Community structures, Social networks – the web graph, the internet graph, citation graphs.

Measures and metrics- Degree centrality, Eigenvector centrality, Katz centrality, PageRank, Hubs and authorities, Closeness centrality, Betweenness centrality, Transitivity, Reciprocity, Similarity, assortative mixing.

Networks models – Random graphs, Generalized random graphs, The small-world model, Exponential random graphs, The large-scale structure of networks- small world effect, Degree distributions, Power laws and scale-free networks; Structure of the Internet, Structure of the World Wide Web.

Fundamental network algorithms- Graph partitioning, Maximum flows and minimum cuts, Spectral graph partitioning, Community detection, Girvan and Newman Algorithm, Simple modularity maximization, Spectral modularity maximization, Fast methods based on the modularity.

Models of network formation-Preferential attachment, The model of Barabasi and Albert, Vertex copying models, Network optimization models; Epidemics on networks- Models of the spread of disease, SI model, SIR model, SIS model, SIRS model; Network search-Web search, Searching distributed databases.

Course Outcome

Evaluation Pattern:

The evaluation will be as follows

• Periodical 1 – 10
• Periodical 2 – 10
• Lab -10
• Project -20
• End Semester – 50

At the end of the course the students will be able to

1. M.E.J. Newman, “Networks: An Introduction”, Oxford University Press, 2010
2. Dougles West, “Introduction to Graph Theory”, Second Edition, PHI Learning Private Limited, 2011.
3. Guido Caldarelli, “Scale-Free Networks”, Oxford University Press, 2007
4. Alain Barrat, Marc Barthelemy and Alessandro Vespignani, “Dynamical processes on Complex networks”, Cambridge University Press, 2008.
5. Reuven Cohen and Shlomo Havlin, “Complex Networks: Structure, Robustness and Function”, Cambridge University Press, 2010.