Graph Theory
Module ID
Ε605
Semester
6
Hours/Week - ECTS
4 – 5
Konstantinos Kokkinos
Assistant Professor
Learning Outcomes
Upon successful completion of the course, the student will be able to:
- define and describe concepts, properties, and characteristics of graphs,
- distinguish between several types of graphs and choose the appropriate type for different applications,
- extend his algorithmic thinking to graph theory problems,
- recognize the role of graphs as a model for a wide variety of knowledge mining problems from usage data,
- model and apply the above concepts to real problems related to network applications,
- studies and analyzes data for knowledge mining using graph visualization tools and software,
- understand and apply centrality metrics and other network metrics,
- evaluate, explain, and present the results obtained from the network analysis it applies to draw conclusions.
Indicative Module Content
The main purpose of the course is to understand graph theory and its applications in modeling and algorithmic solving of practical problems related to data networks. The course includes individual exercises, summary writing and presentation of relevant research papers and applications using network analysis tools such as Python (NetworkX), R (tidyverse), Javascript (cytoscape js, sigma) and network/graph visualization software such as Gephi, Neo4j, Cytoscape , Pajek, NodeXL, etc.
- Definitions and types of graphs, Isomorphism of Graphs
- Representation of Graphs
- Operations of Graphs
- Trees, Spanning Trees, Minimum Spanning Trees, Prim and Kruskal Algorithm, Tree Traversal
- Coherent components, Euler, and Hamilton paths
- Minimum Path Algorithms
- Applications of Graph Theory in Social Networks
- Applications of Graph Theory to Biological Networks
- Eccentricity and other network metrics
- Applications of network analysis and knowledge mining from usage data in music, bibliographic references, cryptocurrencies, etc.