Course

Syllabus

Graphs and Networks- Review of basic graph theory, Mathematics of networks- Networks and their representation, Graph spectra, Graph Laplacian, Structure of complex networks, Clustering, Com- munity 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, 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. Graph databases like Neo4j, Graph Convolutional Neural Networks, Graph algorithms and implementation using NetworkX and Gephi.

Preamble

Network science is an inter disciplinary field that combines mathematics, social science, computer science and many other areas. This course is essentially bringing an understanding on the behavior of networked systems such as the Internet, social networks, and biological networks.

Course Objectives

• Exploring graph models in networked systems; understanding the structure and the behavior.
• Empirical study and hands-on experience on social networks and other systems

Course Outcomes

Prerequisites

• Primary knowledge of linear algebra and familiarity with graphs.
• Working knowledge in Python for data science.

CO-PO Mapping

Evaluation Pattern – 70:30

• Midterm Exam – 20%
• Lab Assignments – 20%
• Project – 30%
• End Semester Exam – 30%

Text Book / References

1. E.J. Newman, “Networks: An Introduction”, Oxford University Press, 2018.
2. Dougles West, “Introduction to Graph Theory”, Third Edition, PHI Learning Private Limited, 2021.
3. Guido Caldarelli, “Scale-Free Networks – Complex Webs in Nature and Technology (2nd ed.)”, Oxford University Press, 2020.
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.