Анализ сетевых структур
- 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
- HomeworksWeekly homeworks (labs).
- Research projects
- Mid Term ExamThe exam will consist of 10 problems, giving 10 points each, total 100 points for the exam.
- Final Exam
- Interim assessment (4 module)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 />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.