Course Information

Course Name	Turkish	Graf Teorisi ve Algoritmalar
	English	Graph Theory and Algorithms
Course Code	BLG 549E	Credit	Lecture (hour/week)	Recitation (hour/week)	Laboratory (hour/week)
Semester	1	3	3	-	-
Course Language		English
Course Coordinator		Islem Rekık
Course Objectives		This courses aims to teach students the fundamental of the field of graph theory while branching into hot topics such as "deep learning on graphs" and "data analysis". Students will gain theoretical and practical experience through exercises and projects. This course will address different questions such as: 1. What is a graph? 2. How to formalize a problem using graphs and graph-based algorithms? 3. How to solve real-world problems using graphs?
Course Description		The following is a preliminary syllabus of the course —which will be refined: 1. Introduction to graph theory (week 1) 1.1. Motivation and broad introduction: The sample is a graph, a node in a graph is a sample! Ways of using graphs. We can look at graphs in different ways, use them in diverse manners. 1.2. Graphs representation (nodes, edges, types of graphs, directionality, sparsity, adjacency matrix) 1.3 Types of graphs including decorated or annotated graphs (where nodes take attributes) Murphy, A.C. et al. Explicitly linking regional activation and function connectivity: community structure of weighted networks with continuous annotation. Preprint at https://arxiv.org/abs/1611.07962 (2016). 1.4. Introduction to graph topology (degree, centrality, neighbourhood) ==> What is the difference between a graph encoded in an adjacency matrix and an image? 2. Graph topology: tools and measures (week 2) 2.1. Centrality, Hubs, Cliques 2.2 Component, cores, and clubs 2.3 Clustering, Degeneracy, and Small Worlds [subgraphs and motifs, modularity] (week 3) 3. Basic graph-based algorithms: start with the fundamentals and go deeper with “deep learning” 3.1 Paths (path length), diffusion, and Navigation (shortest path); Chinese Postman problem, travelling salesman problem; Dijkstra’s Method (week 4) 3.2 Hamiltonian cycle and Eulerian tour 3.3 Diffusion on graphs (information, false news on FB/Twitter), transition matrix (SNF) (week); network morphospace (Bullmore) 3.4 Graph matching algorithms (week 6) 4. Graph transformation techniques 4.1 Graph factorisation techniques with and without learning (factors, arboricity, domination, independence) (week 8) 4.2 Graph Filtering techniques (week 9) 4.3 Graph spectral analysis, spectral embedding(week 10) 4.4 Graph dim reduction techniques and embedding (week 11) 4.5 Graph convolution networks (GCNs) (week 12)
Course Outcomes		I. Ability to design a graph-based algorithm for a specific problem II. Ability to analyze performance of different graph analysis methods III. Ability to combine outputs of different graph analysis techniques IV. Ability to understand the theoretical foundations and workings of different graph analysis algorithms V- Working knowledge about how graph theory is utilized in the fields of machine learning, signal processing, and deep learning.
Pre-requisite(s)		1. Ability to use a programming language such as java, python, C or Matlab. 2. Having a working knowledge of linear algebra and stats would help.
Required Facilities
Other
Textbook		Bullmore, Edward T._ Fornito, Alex_ Zalesky, Andrew - Fundamentals of Brain Network Analysis-Academic Press,Elsevier (2016)
Other References

Courses

Help

About