• A
• A
• A
• ABC
• ABC
• ABC
• А
• А
• А
• А
• А
Regular version of the site
Master 2018/2019

## Network Science

Type: Elective course (Data Science)
Area of studies: Applied Mathematics and Informatics
When: 1 year, 3, 4 module
Mode of studies: Full time
Master’s programme: Data Science
Language: English
ECTS credits: 6

### 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 #### Interim Assessment

• 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> #### 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