General
Introduction to Network Analysis (INA)
Course lecturer
Lovro Šubelj (R 2.49)
Outline & objective
Networks or graphs are ubiquitous in everyday life. Examples include online social networks, the Web, wiring of a neural system, references between WikiLeaks cables, Supervizor, terrorist affiliations, LPP bus map, plumbing systems and your brain. Many such real-world networks reveal characteristic patterns of connectedness that are far from regular or random. Networks have thus been a prominent tool for investigating real-world systems since the 18th century. However, while small networks can be drawn by hand and analyzed by a naked eye, real-world networks require specialized computer algorithms, techniques and models. This led to the emergence of a new scientific field about 20 years ago denoted network analysis.
The course will first introduce the field of network analysis and highlight the differences between classical graph theory and modern network science. In the main part of the course, the students will learn about fundamental concepts and techniques for the analysis of real-world networks including node centralities and equivalence, graphlet counting, blockmodeling, community detection, role discovery, link prediction, network modeling and visualization. The last part of the course will be devoted to selected practical applications of network analysis in fraud detection, software engineering, information science and other.
The objective of the course is to present a broad spectrum of network analysis concepts and techniques, clarify their theoretical foundations and demonstrate their practical applicability. The lectures will give a theoretical discussion on network concepts and present efficient algorithms and techniques for their analysis, while the students will work on practical examples of applying network analysis within labs and their coursework. The topics covered were carefully selected thus to be suitable for a wide range of students and to serve as an introduction to more advanced network analysis courses like Machine Learning with Graphs (MLG) and Advanced Topics in Network Science (ANTS).
Except for good programming skills in some general purpose language (e.g. C/C++, Python, Java), there are no specific prerequisites for the course. However, the students will benefit from a solid knowledge in graph theory, probability theory and statistics, and linear algebra.
Coursework & grading
The students are expected to attend and actively participate in lectures and labs. The ongoing coursework will consist of three homeworks on network analysis concepts and techniques covered in the lectures. Each homework will require certain amount of programming, some analytical derivations and some practical applications to real-world problems. There will also be an additional homework at the beginning of the course, which will not be graded.
The main part of the coursework will consist of a substantial course project. The topic of the project will have to be either empirical evaluation of selected concepts and techniques on an interesting domain, analytical derivation of rigorous theoretical results for selected concepts or techniques, or substantial contribution to the (Slovenian) network analysis community (e.g. online dictionary) or this course. The students will be encouraged to submit up to an eight-page technical report describing the course project to the preprint server arXiv.org, present their project in front of the faculty within Cookie seminars or AI seminars, or make their work publicly available. All students will have to present their project proposal and final project results in front of the class (tentative), while their work will have to be submitted only in the format selected (e.g. students preparing a seminar will not have to write a report). The students will be encouraged to work in pairs or triplets, while larger groups will be allowed only in exceptional cases. Further details on course projects will be given during lectures or labs.
Network analysis concepts and techniques not covered by the coursework will be evaluated within short weekly quizess during lectures or labs.
The base grade for the course will be based 37.5% on the homeworks (12.5% on each homework), 47.5% on the course project (10% on the project proposal, 15% on the project milestone and 22.5% on the final project), and 15% on weekly quizess, course participation and commitment. The final grade will be decided during an oral exam at the end of the course. The students with exceptional coursework will not have to attend the oral exam.
Literature & readings
The course notes, handouts, readings and other materials will be posted periodically on this web page. The course literature will be given in English in the form of handouts with references to selected scientific papers and relevant chapters from the following course books.
- Barabási, A.-L., Network Science (Cambridge University Press, 2016).
- Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
- Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).
- de Nooy, W., Mrvar, A. & Batagelj, V., Exploratory Social Network Analysis (Cambridge University Press, 2011).
- Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).
Course schedule
The lectures start on Feb 17th, 2019 and the labs starts on Feb 24th, 2020. The lectures and labs will be held either in English or Slovene. Weekly course schedule is as follows.
- Lectures on Mondays at 11:00am in PR 19
- Office hours on Tuesdays at 1:00pm in R 2.49
- Labs on Mondays at 2:00pm in PR 7 & Tuesdays/Fridays at 11:00am in PR 10/9
Course assignments
Course assignments will be out and due according to the schedule below. Each assignment is due on Monday at 2:00pm. Twice during the semester the students can take advantage of late days, which means that the assignment is submitted late. Late days for an assignment that is due this Monday expire on Friday at 1:00pm.
The students can prepare their assignments either in English or Slovene. Each assignment must be submitted as a hard-copy in the submission box in front of R 2.49 and also as an electronic version to eUcilnica. Hard-copies will be used for grading, while electronic submissions will be used for plagiarism detection and archive purposes. Each submission must include the course cover sheet with a signed honor code.
Week Date Out Due Challenge Comment 1 Feb 17th Homework #0 (PDF, TeX) 2 Feb 24th Homework #0 Four knights 3 Mar 2nd 4 Mar 9th Homework #1 (PDF, TeX) Grand graph 5 Mar 16th 6 Mar 23rd Homework #1 ÷-vector centrality 7 Mar 30th Homework #2 (PDF, TeX) 8 Apr 6th Five networks 9 Apr 13th Homework #2 Easter days 10 Apr 20th Homework #3 (PDF, TeX) PageRank centrality 11 Apr 27th Labour days 12 May 4th Homework #3 13 May 11th Project proposal 14 May 18th 15 May 25th 16 Jun 1st Semester ends 17 Jun 8th Project milestone Exams start 18 Jun 15th 19 Jun 22nd Project deadline 20 Jun 29th Oral exams - Barabási, A.-L., Network Science (Cambridge University Press, 2016).
Course videos
Week Date Intro Lectures Labs 5 Mar 16th 05-intro 05-bridging, 05-smallworld & 05-project v-1-labs 6 Mar 23rd 06-intro 06-science, 06-scalefree & 06-preferential v-2-labs 7 Mar 30th 07-intro 07-mixing, 07-fragments & 07-hw#1 vii-labs 8 Apr 6th 08-intro 08-community & 08-clustering viii-labs 9 Apr 13th 09-intro / / 10 Apr 20th 10-intro 10-blockmodeling, 10-cores & 10-hw#2x-labs 11 Apr 27th 11-intro / / 12 May 4th 12-intro 12-inference & 12-mining xii-labs 13 May 11th 13-intro 13-sampling, 13-visualization & 13-hw#3xiii-labs 14 May 18th 14-intro 14-comparison & 14-skeletons xiv-labs 15 May 25th 15-intro 15-fraud, 15-software & 15-bibliometrics / 16 Jun 1st / 16-farewell etc. / Course homeworks
Course projects
Course challenges
Course discussions