TSKS11 Networks: Models, Algorithms and Applications
TSKS11 Networks: models, algorithms and applications is an
inter-disciplinary course on network science. Network science has
applications in the analysis of, for example, social networks,
information networks, computer/communication networks and biological
- Models and representations of networks, adjacency matrix, degree distribution, modularity, Laplacian
- Weighted and signed networks, structural balance ("friends and foes"), homophily, betweenness
- Centrality metrics: "who is most influential" (Google PageRank, Katz, hub/authority, closeness)
- Algorithms for network partitioning and detection of communities
- Network models, random (Poisson) networks, scale-free networks, degree correlations
- Power laws, growth models, information cascades and viral phenomena
- Network formation and growth, preferential attachment, percolation
- World-is-small phenomena, searchability and reachability ("six-degrees-of-separation")
- Diffusion, random walks and cascades on networks
- Collaborative filtering on bipartite graphs (recommendation system)
The course consists of a series of lectures, tutorials, and a number of hands-on computer sessions. In these sessions we will:
- Analyze and visualize large networks using software tools, especially Gephi and SNAP. We will be using synthetic data and real data from social networks, among others SNAP datasets, and the DBLP database. The focus is on the interpretation and understanding of the results.
- Implement and experiment with some algorithms for network analysis, specifically centrality metric (incl. Google PageRank) computation, and network partitioning. The purpose is to obtain a deeper understanding for how these algorithms work.
- Implement a recommendation system that uses collaborative filtering to suggest movies to viewers based on grades given by other viewers (similar to what is being used by services such as NetFlix). We will train and evaluate the performance of this system using real data from the "Movielens" project, consisting of millions of grades set by real (but anonymized) users on real movies. The focus is on the ability to implement a basic algorithm, and propose and evaluate improved algorithms.
For prospective students, to get a more detailed idea of the course contents:
- You may watch this short video.
- I teach much of the lectures on the whiteboard, but there is also a set of Powerpoint slides with diagrams and examples. These Powerpoints, along with some other, supplementary course notes, and material for the computer labs can be accessed here (from 2018). Note that the parts of the lab series will be revised in 2019, but the labs from 2018 give an indication of what type of work that is involved. You may also look at previous year's written exams.
Documents and files:
- Lecture and tutorial plan. (From 2018, to be revised.)
- ZIP file with lecture slides, answers to the tutorial problems, and supplementary course notes. (From 2018, to be updated.)
- ZIP file with material for the hands-on sessions. (From 2018, to be revised.)
Main course textbook (compulsory):
- A. Barabasi, Network Science, Cambridge University Press, 2016.
Available online and in print from various bookshops, for example here
We will also be using some material from the following texts:
- D. Easly and J. Kleinberg: Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press, 2010.
Available online at the authors' website.
- M. Chiang, Networked Life, Cambridge University Press, 2012.
Available as e-book via this link (LiU-logon required).
Here are some other books that also are relevant for the course:
- M. Newman, Networks: An Introduction, Oxford University Press, 2010.
- E. Estrada and P. A. Knight, A First Course in Network Theory, Oxford University Press, 2015.
- V. Latora, V. Nicosia, G. Russo, Complex networks, Cambridge University Press, 2017.
- E. Estrada, The Structure of Complex Networks: Theory and Applications, Oxford University Press, 2011.
- Gephi, software for the analysis of large networks
- Stanford Network Analysis Project (Python/C++ library for analysis of large networks, and data sets)
- Course description in the LiTH study guide
Erik G. Larsson
Last updated: 2019 02 28 08:05