Дискретная математика и анализ социальных графов

2026/2027

Статус: Маго-лего

Кто читает: Институт медиа

Где читается: Факультет креативных индустрий

Когда читается: 1 модуль

Онлайн-часы: 38

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Переяслов Алексей Денисович

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

Кредиты: 3

Контактные часы: 6

Full Syllabus Ask Question

Abstract

This course introduces the basics of discrete mathematics — combinatorics, discrete probability, and graph theory — and shows how these tools are used to analyze the structure of social network graphs. Students learn counting techniques, the classical definition of probability, and the main parameters used to describe graphs, and apply this knowledge, including with Python and NetworkX, to real social network data.

Learning Objectives

To use methods of combinatorics to count objects.
To calculate probabilities of events using the definition and properties of probability.
To analyze the structure of graphs using graph parameters.
To apply knowledge of discrete mathematics to the analysis of social network graphs.

Expected Learning Outcomes

Uses methods of combinatorics (rules of sum and product, tuples, permutations, combinations, binomial coefficients) to count objects and solve counting problems.
Calculates probabilities of events based on their definition and properties, including with combinatorial methods.
Analyzes the structure of a graph using its basic parameters (degree, distance, clustering coefficient, connectivity, vertex covers).
Applies methods of discrete mathematics and graph theory, including Python and NetworkX, to the analysis of social network graphs.

Course Contents

Basic Combinatorics
Advanced Combinatorics
Discrete Probability
Basic Graph Parameters
Introduction to Graphs
Graphs of Social Networks

Assessment Elements

Week 1 Quizzes
This element combines all 10 automatically graded quizzes of Week 1 (Basic Combinatorics). Composition of the element (weight of each quiz within the overall course grade):
Week 2 Quizzes
Week 3 Quizzes
Week 4 Quizzes
Week 5 Quizzes
Programming Assignment
A single programming assignment (“Programming task | Clustering: Real vs. Random”, week 6) in which students compute the average clustering coefficient (ACC) of a real social network graph and compare it to the ACC of a randomly generated (Erdős–Rényi) graph with the same number of vertices and edge probability.

Interim Assessment

2026/2027 1st module
0.18 * Week 2 Quizzes + 0.2 * Week 5 Quizzes + 0.28 * Week 1 Quizzes + 0.04 * Programming Assignment + 0.14 * Week 4 Quizzes + 0.16 * Week 3 Quizzes

Bibliography

Recommended Core Bibliography

Discrete mathematics and its applications, Rosen, K. H., 2013
Introduction to probability models, Ross, S. M., 2010

Recommended Additional Bibliography

Networks : an introduction, Newman, M. E. J., 2013
Networks, crowds, and markets : reasoning about a highly connected world, Easley, D., 2010

Course Syllabus