• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Магистратура 2019/2020

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

Статус: Курс обязательный (Науки о данных)
Направление: 01.04.02. Прикладная математика и информатика
Когда читается: 1-й курс, 3, 4 модуль
Формат изучения: Full time
Прогр. обучения: Науки о данных
Язык: английский
Кредиты: 6

Программа дисциплины

Аннотация

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.
Цель освоения дисциплины

Цель освоения дисциплины

  • To familiarize students with a new rapidly evolving filed of network science, and provide practical knowledge experience in analysis of real world network data.
Результаты освоения дисциплины

Результаты освоения дисциплины

  • 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.
Содержание учебной дисциплины

Содержание учебной дисциплины

  • 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
Элементы контроля

Элементы контроля

  • 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 (неблокирующий)
Промежуточная аттестация

Промежуточная аттестация

  • Промежуточная аттестация (4 модуль)
    The weight of a project is three times greater than the weight of each HW.<br />О<sub>cumulative</sub> includes the normalizaed grade of all assignments during the study period.<br />The grade formula: <br />Final course mark is obtained from the following formula: <br />О<sub>final</sub> = 0,6*О<sub>cumulative</sub>+0,4*О<sub>exam</sub>
Список литературы

Список литературы

Рекомендуемая основная литература

  • 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

Рекомендуемая дополнительная литература

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