Магистратура 2020/2021

Анализ сетевых структур

Статус: Курс по выбору (Науки о данных)

Направление: 01.04.02. Прикладная математика и информатика

Кто читает: Департамент анализа данных и искусственного интеллекта

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Преподаватели: Жуков Леонид Евгеньевич, Киселёв Дмитрий Андреевич, Макаров Илья Андреевич

Прогр. обучения: Науки о данных

Язык: английский

Кредиты: 6

Контактные часы: 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

• 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

• 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

• 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

• Homeworks
  Weekly homeworks (labs).
• Research projects
• Mid Term Exam
  The exam will consist of 10 problems, giving 10 points each, total 100 points for the exam.
• 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 (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

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.