Course

Unit I

Graph clustering: Algorithms for partitioning a graph into well-connected pieces (spectral partitioning, sparsest-cuts, multi-way cuts)

Distances in graphs: Algorithmic methods for geometric problems in graphs, such as the Traveling Salesperson Problem, Minimum Spanning Trees, Shortest Paths

Unit II

Flows in graphs: Min-cut/max-flow duality, and its extensions to multi-commodity flows. Applications to divide & conquer. – Graph compression: Methods for representing succinctly large graphs (spectral sparsifiers, vertex sparsifiers, graph spanners)

Unit III

Graph Clustering and Community Detection: Clustering algorithms for graphs: k-means, spectral clustering, Community detection algorithms: modularity-based, hierarchical clustering, Evaluation metrics for graph clustering

Applications of Graph Mining: Social network analysis, Web mining and, recommendation systems, Biological network analysis, Knowledge graphs and semantic web

Course Objectives

• The course aims at Acquiring basic knowledge in the area of algorithmic graph theory including learning the key concepts of mathematical rigor in the analysis of graph algorithms, and of the efficiency of algorithms.
• It exposes the students to focus on mathematical properties of graphs and networks, as a tool for the design of better algorithms.

Course Outcomes

CO1: Understand the basics of graphs, directed graphs, and weighted graphs, and be able to relate them to

practical examples.

CO2: Use effective algorithmic techniques to study basic parameters and properties of graphs.

CO3: Design efficient algorithms for various optimization problems on graphs.

CO4: Use effective techniques from graph theory to approach practical problems in networking and

telecommunication

CO-PO Mapping

Evaluation Pattern: 70:30

*CAT – Can be Quizzes, Assignments, and Reports

*CAL – Can be Lab Assessments, Project, and Report

**End Semester can be theory examination/ lab-based examination/ project presentation

Textbook(s)

1. A. Bondy and U. S. R. Murty, “Graph Theory with Applications”,2008.

Reference(s)

Richard J Trudeau, “Introduction to Graph Theory”, 2017 Edition.

1. Ahuja, L. Magnanti, and J. Orlin, “Network Flows: Theory, Algorithms, and Applications”.

Nagiza F. Samatova, William Hendrix, John Jenkins, Kanchana Padmanabhan, Arpan Chakraborty, “Practical Graph Mining”,2014.

Xu, R., & Wunsch, D. (2005). “Survey of clustering algorithms”. IEEE Transactions on neural networks, 16(3), 645-678.