COURSE SUMMARY
Course Title: 
Networks and Spectral Graph Theory
Course Code: 
18CS710
Year Taught: 
2018
Degree: 
Postgraduate (PG)
School: 
School of Engineering
Campus: 
Coimbatore

'Networks and Spectral Graph Theory' is an elective course offered in M. Tech. in Computer Science and Engineering program at School of Engineering, Amrita Vishwa Vidyapeetham.

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.

TEXTBOOKS/REFERENCES

  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.

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

  Course Outcome Bloom’s Taxonomy Level
CO 1 Describe fundamental tools to study networks, mathematical models of network structure, computer algorithms for network data analysis and the theories of processes taking place on networks. Knowledge
CO 2 Experience working with complex network data sets and implement computer algorithms to solve network problems, use modern network tools to analyze data Application
CO 3 Compare different solutions of large network problems in terms of network performance measures, Compare structure of different types of networks Analyze
CO 4 Design algorithms to solve large real-world network problems, devise models of network structure to predict the behavior of networked systems. Synthesis