Анализ сетевых структур
Статус: Курс обязательный (Науки о данных)
Направление: 01.04.02. Прикладная математика и информатика
Где читается: Факультет компьютерных наук
Когда читается: 1-й курс, 3, 4 модуль
Формат изучения: Full time
Прогр. обучения: Науки о данных
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 scienceIntroduction to new science of networks. Complex networks theory. Basic network properties and metrics. Networks examples.
- Power laws and scale-free networksPower law distribution. Scale-free networks. Pareto distribution, normalization, moments. Zipf’s law. Rank-frequency plot.
- Models of network formationErdos-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 analysisNode 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 communitiesNetwork 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 predictionNetwork 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.