Course

Unit I

Review of Graphs: Graphs and Sub graphs, isomorphism, matrices associated with graphs, degrees, walks, connected graphs, shortest path algorithm. Eccentricity.

Connectivity: Graph connectivity, k-connected graphs and blocks. Unit II: Matching and Colorings: Matchings, maximal matchings. Coverings and minimal coverings. Graph Dominations and Independent sets. Vertex colorings, Planar graphs. Euler theorem on planar graphs.

Large Scale networks: Introduction. Graph and Networks. Network topologies. Examples of large-scale networks and networked systems. Power Law distributions. Scale-free networks. Random graph models for large networks: Erdos-Renyi graphs, power-law graphs, small world graphs, phase transitions. Network stabilities.

Unit II

Graph Networks and Centralities: Degree and distance centralities. Closeness centrality. Betweeness centrality. Eigenvector centrality and Page ranking algorithm and applications. Clustering coefficient and clustering centrality. Introduction to community detections.

Case Studies: Implementation of the centralities and community detection algorithms with Transport networks, Biological networks, etc.

Course Objectives

• To understand the basic concepts of graphs.
• To understand and apply different graph centralities with networks
• Able to take case studies on the large scale networks with graph centralities.

Course Outcomes

Text Books:

1) J.A. Bondy and U.S.R. Murty, Graph Theory and Applications, Springer, 2008.

2) Mohammed Zuhair Al-Taie, SeifedineKadry, Python for Graph and Network Analysis, Springer, 2018.

Reference Books:

1) Barabasi and Pasfai, Network Science, Cambride University press, 2016.

2) Meghanathan Natarajan, Centrality Metrics for Complext Networks Analysis, IGI publisher, 2018.

3) Networks: An Introduction , M. E. J. Newman , Oxford University Press , 2010.

4) Complex Graphs and Networks , F. Chung and L. Lu , American Mathematical Society , 2006

5) Graph Algorithms in Neo4j