Hide menu

TSKS11 Networks: Models, Algorithms and Applications

Erik G. Larsson
Erik G. Larsson

Course Director

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 networks.

Course themes:

  • 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, and three computer projects:

  1. Analysis of large networks using software tools. The purpose of this laboratory is to use software tools (Gephi and SNAP) to analyze and visualize networks. We will be using synthetic data and real data from social networks, especially the DBLP database. Focus is on the interpretation and understanding of the analysis.
  2. Algorithms for network analysis. The purpose of this project is to implement and experiment with algorithms for network analysis. Specifically, we will implement calculations of centrality metrics (incl. PageRank) and algorithms for network partitioning.
  3. Collaborative filtering on bipartite graphs (recommendation system). In this project, we will implement a recommendation system that suggests movies to viewers based on grades given by other viewers (similar to what is being used by, e.g., 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.

  • Course textbook (compulsory):
  • Supplementary reading/other relevant books:
    1. M. Newman, Networks: An Introduction, Oxford University Press, 2010.
    2. V. Latora, V. Nicosia, G. Russo, Complex networks, Cambridge University Press, 2017.
    3. 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.
    4. M. Chiang, Networked Life, Cambridge University Press, 2012.
      Available as e-book via this link (LiU-logon required).
  • Relevant links:

  • Page responsible: Erik G. Larsson
    Last updated: 2018 01 21   10:13