About
This course is an introduction to the network science and machine learning problems on graphs. Next session will be held at Spring 2022 at BigData Academy MADE by VK.
Team
Schedule
Lecture 1. Introduction to Network Analysis
Lecture slides / Seminar notebook
Terminology. Properties and descriptive statistics of real-world networks. Power-law and scale-free networks. Zypf law. Six degrees of separation. Clustering coefficients.
Lecture 2. Network Formation Models
Lecture slides / Seminar notebook
Random graph model. Preferential attachment model. Small world model. Model properties comparison and connection to real-world graphs.
Lecture 3. Centrality Measures
Lecture slides / Seminar notebook
Graph-theoretic measures, Node centralities: degree, closeness, betwennees, eigenvector, Katz and Bonacich. Rank correlation.
Lecture 4. Link Analysis and Structural Similarity
Lecture slides / Seminar notebook
Web page ranking algorithms: PageRank, HITS. Node equivalence: structural, regular. Node similarity. Assortative mixing.
Lecture 5. Network Structure
Lecture slides / Seminar notebook
Graph cores. Graph cliques. Network communities. Graph partitioning algorithms.
Lecture 6. Diffusion and Random Walks on Graphs, Epidemics.
Lecture slides / Seminar notebook
Random walks on graphs, diffusions. Spectral graph theory. Epidemics: contagion model, branching process. Compartmental models: SI, SIS, SIR, advanced models. Modelling SARS outbreak. Vaccination strategies.
Lecture 7. Cascades in Networks and Agent Based Modeling
Lecture slides / Seminar notebook
Diffusion of innovation. Influence propagation models. Influence maximization problem. Spatial segregation.
Lecture 8. ML on Graphs. Node Classification
Lecture slides / Seminar notebook
Label propagation and iterative classification. Semi-supervised methods: random walks, regulatization. Matrix factorization.
Lecture 9. ML on Graphs. Link prediction
Lecture slides / Seminar notebook
Similarity-based. Matrix Factorization. Random walks. Other methods. Graph Embeddings: problem statement, structural models (simple cases).
Lecture 10. ML on Graphs. Structural Graph Embeddings
Lecture slides / Seminar notebook
Continuation of previous lecture. Mixed-hop models. Accounting for attributes.
Lecture 11. ML on Graphs. Graph Neural Networks
Lecture slides / Seminar notebook
Recap on graph embeddings. Graph Convolutional Networks, Graph Attention, GraphSAGE and inductive learning. PinSAGE and large-scale recommendations. Open problems. Modern models. Applications to other CS domains.
Lecture 12. Information Retrieval and Knowledge Graphs. The Semantic Web Technology
Lecture slides / Seminar notebook
Knowledge graphs basics. Problems on knowledge graphs: completion, reasoning, applications.
Programming environment
- Python, iPython Notebooks (e.g. Anaconda distribution)
- Python libraries: NetworkX, pytorch and dgl (only last two seminars)
- Visualization: yEd, Gephi
Recommended books
- Network Science, Albert-Laszlo Barabasi, Cambridge University Press, 2016.
- “Networks: An Introduction”. Mark Newman. Oxford University Press, 2010.
- “Social Network Analysis. Methods and Applications”. Stanley Wasserman and Katherine Faust, Cambridge University Press, 1994
- “Networks, Crowds, and Markets: Reasoning About a Highly Connected World”. David Easley and John Kleinberg, Cambridge University Press 2010.