Welcome, Guest . Login . Türkçe
Where Am I: Ninova / Courses / Institute of Science and Technology / BLG 549E / Course Informations
 

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
Ninova is an ITU Office of Information Technologies Product. © 2024