Graphs and Network Analysis

Learning Outcomes

Students will acquire a comprehensive understanding of fundamental graph theory concepts, network metrics, and advanced algorithms applied to real-world scenarios. By delving into topics such as degree centrality, eigenvector centrality, and community detection, students will develop a robust skill set in graph analysis and visualization. The course not only equips students with the ability to represent complex systems as graphs but also enables them to utilize cutting-edge tools and methodologies for problem-solving. Furthermore, the exploration of applications, including social networks and pharmacology, ensures that students gain practical insights into diverse fields. Upon completion, graduates will possess a refined capacity to analyze, model, and interpret intricate relationships within networks, fostering their competence in research, industry, and various interdisciplinary domains. The profound impact of this course is expected to extend beyond academic realms, empowering students with a skill set highly sought after in today's data-driven and interconnected world.

Course Content

1. Introduction to graphs. Basic definitions. Paths, cycles, shortest paths.
   Representation of graphs and toolbox of problems/algorithms on graphs.
   Overview of basic concepts of graph theory. Introduction to network analysis metrics.
   Degree centrality, eigenvector centrality, Katz centrality. Pagerank and HITS. Co-citation and bibliographic coupling networks. Closeness centrality, Betweenness centrality.
   Node groups. Transitivity. Reciprocity. Signed graphs. Node similarity. Homophily.
   The Internet as a graph. Properties of networks in the real world. Gnp and Gnm models. Smallworld model. Power-law and scale-free networks. Barabasi-Albert model. R-MAT model.
   Study of degree distributions in real graphs. Finding power-law exponents in power-law distributions. Generating graphs with realistic characteristics.
   Link prediction in graphs.
   Community detection in graphs.
   Shallow methods for knowledge representation vector generation (graph embeddings).
   Message-passing methods.
   Graph Neural Networks.
   Applications (social networks, pharmacology, and others).