• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Master 2020/2021

Network Science

Type: Elective course (Data Science)
Area of studies: Applied Mathematics and Informatics
When: 1 year, 3, 4 module
Mode of studies: offline
Instructors: Dmitrii Kiselev, Ilya Makarov, Leonid E Zhukov
Master’s programme: Data Science
Language: English
ECTS credits: 6
Contact hours: 80

Course Syllabus

Abstract

The course “Network Science” introduces students to new and actively evolving interdisciplinary field of network science. Started as a study of social networks by sociologists, it attracted attention of physicists, computer scientists, economists, computational biologists, linguists and others and become a truly interdisciplinary field of study. In spite of the variety of processes that form networks, and objects and relationships that serves as nodes and edges in these networks, all networks poses common statistical and structural properties. The interplay between order and disorder creates complex network structures that are the focus of the study. In the course we will consider methods of statistical and structural analysis of the networks, models of network formation and evolution and processes developing on network. Special attention will be given to the hands-on practical analysis and visualization of the real world networks using available software tools and modern programming languages and libraries.
Learning Objectives

Learning Objectives

  • To familiarize students with a new rapidly evolving filed of network science, and provide practical knowledge experience in analysis of real world network data.
Expected Learning Outcomes

Expected Learning Outcomes

  • Students know basic notions and terminology used in network science.
  • Students understand fundamental principles of network structure and evolution.
  • Students develop mathematical models of network processes.
  • Students analyze real world network data.
Course Contents

Course Contents

  • Introduction to network science
    Introduction to new science of networks. Complex networks theory. Basic network properties and metrics. Networks examples.
  • Power laws and scale-free networks
    Power law distribution. Scale-free networks. Pareto distribution, normalization, moments. Zipf’s law. Rank-frequency plot.
  • Models of network formation
    Erdos-Reni random graph model. Poisson and Bernulli distributions. Distribution of node degrees. Phase transition, gigantic connected component. Diameter and cluster coefficient. Configuration model. Barabasi-Albert model. Preferential attachment. Equation in continues approximation. Time evolution of node degrees. Node degree distribution. Average path length and clustering coefficient. Small world model. Watts-Strogats model. Transition from regular to random. changes in clustering coefficient and average path length.
  • Structure, nodes and links analysis
    Node centrality metrics, degree centrality, closeness centrality, betweenness centrality, eigenvector centrality. Graph structure based metrics. PageRank, stochastic metric and Perron-Frobenius theorem. Power iterations. Hubs and Authorities. HITS algorithm. Kendall-Tau ranking distance. Structural equivalency metrics. Euclidean and Hamming distance. Correlation coefficient. Cosine similarity. Assortative mixing and homophily. Modularity. Mixing by degree.
  • Network communities
    Network communities. Graph density. Graph pertitioning. Min-cut, quotent and normalized cuts metrics. Divisive and agglomerative algorithms. Repeated bisection. Correlation matrix. Clustering. Edge Betweenness. Newman-Girvin algorithm. Spectral methods. Modularity maximization algorithm (Newman). Approximation algorithms. Randomized min-cut (Karges's algorithm). Probability of finding min-cut. Multilevel paradigm. Multilevel algorithm for power law graphs. Local clustering. Conductance. Nibble Algorithms. Graph motiffs, k-cores, diad and triad census.
  • Evolving networks and link prediction
    Network growth. Shrinking diameter. Link reciprocity. Link prediction problem. Supervised learning for prediction.
  • Epidemics on networks
  • Diffusion of information
  • Influence propagation
Assessment Elements

Assessment Elements

  • non-blocking Homeworks
    Weekly homeworks (labs).
  • non-blocking Research projects
  • non-blocking Mid Term Exam
    The exam will consist of 10 problems, giving 10 points each, total 100 points for the exam.
  • non-blocking Final Exam
    Экзамен проводится в письменной форме с использованием синхронного прокторинга. Экзамен проводится на платформе Moodle (https://moodle.org/?lang=ru). Прокторинг проводится на платформе Экзамус (https://hse.student.examus.net). К экзамену необходимо подключиться за 15 минут. На платформе Экзамус доступно тестирование системы. Компьютер студента должен удовлетворять следующим требованиям: https://elearning.hse.ru/data/2020/05/07/1544135594/Технические%20требования%20к%20ПК%20студента.pdf) Для участия в экзамене студент обязан: заранее зайти на платформу прокторинга, провести тест системы, включить камеру и микрофон, подтвердить личность. Во время экзамена студентам запрещено: общаться (в социальных сетях, с людьми в комнате), списывать. Кратковременным нарушением связи во время экзамена считается прерывание связи до 10 минут. Долговременным нарушением связи во время экзамена считается прерывание связи 10 минут и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи.
Interim Assessment

Interim Assessment

  • Interim assessment (4 module)
    The weight of a project is three times greater than the weight of each HW.
    Оcumulative includes the normalizaed grade of all assignments during the study period.
    Final course mark is obtained from the following formula:
    Оfinal = 0,6*Оcumulative+0,4*Оexam
Bibliography

Bibliography

Recommended Core Bibliography

  • Easley, D. et al. Networks, crowds, and markets. – Cambridge : Cambridge university press, 2010. – 744 pp.
  • Newman, M. (2010). Networks: An Introduction. Oxford University Press, 2010

Recommended Additional Bibliography

  • Newman, M., Watts, D. J., and Barabási, A. The Structure and Dynamics of Networks. – Princeton University Press, 2006. – 592 pp.