Information networks are effective representations of pairwise relationships between objects. Examples include technological networks (e.g., World Wide Web), online social networks (e.g., Facebook), biological networks (e.g., Protein-to-Protein interactions), and more. The study of information networks is an emerging discipline of immense importance that combines graph theory, probability and statistics, data mining and analysis, and computational social science. This course provides students with both theoretical knowledge and practical experience of the field by covering models and algorithms of information networks and their basic properties. In addition, analysis of information networks provides the means to explore large, complex data coming from vastly diverse sources and to inform computational problems and better decisions.
Lectures: Tue and Thu, 11:30 - 14:30 ACE 005 (Accolade East Building)
Office Hours: Tue, 14:30 – 15:30 at LAS3050 (or right after class)
The course will rely mainly on the following textbooks.
Download the syllabus (v1.0)
Introduction, administrivia, introduction to main problems about networks, basic mathematical concepts, bow-tie structure of the Web.
Readings:
Optional readings:
Degree distributions, shortest paths, clustering coefficient, measuring power-laws.
Readings:
Optional readings:
Erdos-Renyi random graph model, small-world model, configuration model, power-law distributions, scale-free networks, the anatomy of the long-tail, mathematics of power-laws, preferrential attachment model, microscopic evolution of networks, macroscopic evolution of networks, forest-fire model.
Readings:
Optional readings:
Web search, Hubs and Authorities (HITS), PageRank, topic-sensitive PageRank, personalised PageRank.
Readings:
Optional readings:
Link prediction, neighborhood-based prediction methods, node proximity based prediction methods, supervised learning models, Facebook's "PYMK" algorithm, Twitter's "WtF" algorithm.
Readings:
Optional readings:
Strength of weak ties, structural holes, network communities, community detection, Girvan-Newman algorithm, modularity, modularity optimization.
Readings:
Optional readings:
Graph partitioning, graph cuts, conductance, spectral graph theory, spectral graph clustering.
Readings:
Optional readings:
Overlapping communities, cliques, clique percolation method, modeling networks with communities, community-affiliation graph model.
Readings:
Optional readings:
Spreading through networks, Granovetter’s model of collective action, decision based model of diffusion, game theoretic model of cascades.
Readings:
Optional readings:
Epidemic model based on trees, models of disease spreading (SIR, SIS, SIRS), independent cascade model, modeling interactions between contagions.
Readings:
Optional readings:
Epidemic modeling, mobility, trajectory network, individual variability, risk of infection, SEIR model, COVID-19.
Readings:
Optional readings:
In-class team project presentations, the age of networks, review of key topics covered (your superpowers), applying your superpowers, what's next?
node embeddings, graph convolutional networks (GNNs), knowledge graphs (KG).
Slides based on WWW2018 tutorial on network representation learning by Jure Leskovec, William L. Hamilton, Rex Ying, Rok Sosic (Stanford University).
The Influence Maximization Problem (IMP), IMP hardness, IMP approximation, submodularity.
Readings:
Optional readings:
The outbreak detection problem, greedy hill-climbing approx. algorithm, cost-effective lazy forward-selection (CELF) algorithm.
Readings:
Optional readings:
Recommender systems, content-based systems, collaborative filtering.
Readings:
Optional readings:
Latent factor models for recommender systems, The Netflix challenge.
Readings:
Optional readings:
Project handouts:
Sample past project deliverables (thanks to Gian Alix, Jing Li and Baoqi Yu):
(Titles of) Past Projects:
Online resources for mining and exploration of graphs/networks.
A list of useful online tutorials relating to the course material.
Similar courses about information networks and network analysis.