This course deals with computer science (CS) aspects of social network analysis (SNA), and is open to all students in the master computer science programme at Leiden University.
Lectures: Fridays from 11:15 to 13:00 (Sep. 6 - Dec. 13)
Snellius room 174
Lab sessions: Fridays from 9:15 to 11:00 in room 306/308 (not on Sep. 6)
Prerequisites: a CS bachelor with courses on Algorithms, Data Structures and Data Mining
Literature: provided papers and book chapters (free and digitally available)
Examination: based on presentation, paper, programming, peer review and participation (no exam)
Blackboard course code: 4343SNACS-1920FWN
Study points: 6 ECTS
Lecturer: dr. Frank Takes - firstname.lastname@example.org, room 157b
Assistant lecturer: Anna Latour MSc - email@example.com, room 123
Course assistant: Antonio Barata MSc - firstname.lastname@example.org, room 126
Student assistants: Hanjo Boekhout Bsc - email@example.com and Jeroen Rook BSc - firstname.lastname@example.org.
Network with 1458 nodes and 1948 edges.
|Date||First slot (9:15-11:00)||Second slot (11:15-13:00)|
|1.||Sep 6, 2019||No activities||Lecture 0: Course organization
Lecture 1: Introduction and small world phenomenon
|2.||Sep 13, 2019||Gephi tutorial
Work on Assigment 1
|Lecture 2: Advanced concepts and centrality|
|3.||Sep 20, 2019||NetworkX tutorial
Work on Assigment 1
|Lecture 3: Network projection and community detection
Presentation 0: Diameter computation
|4.||Sep 27, 2019||Work on Assigment 1||Lecture 4: Web structure and propagation-based centrality|
|Sep 30, 2019||Deadline for Assignment 1 (hand in via Blackboard)|
|Oct 3, 2019||No lecture||No lecture|
|5.||Oct 11, 2019||Course project planning
Work on Assigment 2
|Lecture 5: Network dynamics & Processes on networks|
|6.||Oct 18, 2019||Work on Assigment 2||Two parallel sessions of two presentations each:
Presentation 1 (405, 11:15): Sampling networks
Presentation 2 (405, 12:15): Influence spread and virality 2
Presentation 3 (174, 11:15): Community detection 4
Presentation 4 (174, 12:15): Link prediction in signed networks
|7.||Oct 25, 2019||Course project paper
Work on Assigment 2
Presentation 5 (405, 11:15): Community detection 2
Presentation 6 (405, 12:15): De-Anonymization of networks
Presentation 7 (174, 11:15): Shortest paths 1
Presentation 8 (174, 12:15): Data errors in networks
||Deadline for Assignment 2 (hand in via Blackboard)|
|8.||Nov 1, 2019||Work on course project||
Presentation 9 (405, 11:15): Motifs in multilayer networks
Presentation 10 (405, 12:15): Community detection 1
Presentation 11 (174, 11:15): Anomaly detection in networks
Presentation 12 (174, 12:15): Community detection 3
|Nov 7, 2019||Deadline for bringing (printed, in two fold) a first version of the course project paper|
|9.||Nov 8, 2019||Work on course project||Peer review session|
|10.||Nov 15, 2019||Work on course project||
Presentation 13 (405, 11:15): Link prediction
Presentation 14 (174, 11:15): Closeness centrality 2 (top-k)
Presentation 15 (174, 12:15): Motifs in temporal networks
|Nov 18, 2019||Deadline (optional) for handing in a preliminary version of the course project paper (via
|11.||Nov 22, 2019||Work on course project||Code review session
Final collaborative document
A still editable version (visit at own risk)
|12.||Nov 29, 2019||Work on course project
Presentation 16 (402, 10:15): Network embeddings 1
Presentation 25 (403, 10:15): Motifs in networks
Presentation 17 (174, 11:15): Shortest paths 2
Presentation 18 (405, 12:15): Closeness centrality 1
Presentation 19 (174, 11:15): Influence spread and virality 1
Presentation 20 (174, 12:15): Resilience of networks
|13.||Dec 6, 2019||Finalize course project||
Presentation 21 (405, 11:15): Personalized PageRank
Presentation 22 (405, 12:15): Betweenness centrality 1
Presentation 23 (174, 11:15): Neighborhood approximation
Presentation 24 (174, 12:15): Visualization algorithms 2
|Dec 9, 2019||Deadline for Course Project|
|Dec 16, 2019||Retake deadline for assignments|
|Dec 16, 2019||Deadline for filling in the individual Course Project Evaluation Form (hand in via Blackboard)|
|Dec. 20, 2018||Course end. Grades will be submitted to the student administration|
The main goal of this lab session is to get started with the course project paper.
Course project paper
During the lab session of two weeks ago, you have made a project planning. One upcoming deadline is the first version of your paper for the peer review session.
Continue with Assignment 2.
The main goal of this lab session is to get started with both the course project and with Assignment 2, and to get to know the data science lab.
Data Science Lab
The data science lab website provides necessary information and documentation. Become familiar with the lab and how to run code on it, and how to place data within the lab. Remember: your homedirectory is for your own code, /local is for local storage on the current machine you are are on, and /data is for storing data across data science lab machines. You may want to use the lab's facilities for course assignments and your course project.
Below are some topics you can discuss and investigate together with your project team partner.
Get started with the practical part of Assignment 2.
The main goal of this lab session is to become familiar with NetworkX (a Python package to analyze networks for research purposes).
All relevant information on NetworkX can be found in the NetworkX online documentation.
We will again use the UNIX/Linux workstations for this lab session, and there is again no deliverable.
Installation.. To use Python in your own environment, first go (or make) the directory where you will work in for the course. For example ~/Documents/SNACS
Next, create a virtual environment with the following command:
virtualenv -p /usr/bin/python3.5 snacsenv
You can activate this environment with the following command:
You can install the packages you want with the pip command:
pip install numpy matplotlib networkx
Now you should be able to run your code from the command line. Next time you log in and need to use the environment, you only need to use the source command
Bonus: If you want to use a jupyter notebook instead, this is possible with the following commands:
pip install jupyter
jupyter notebook --ip=127.0.0.1 —port=8888
Looking for a challenge? Check out Graph-Tool, a python graph analysis toolkit that leaves the hard computation to parallel (OpenMP) C++ code. Or snap, which is entirely written in C++ (although there is now also a Python plugin).
We will use the UNIX/Linux Ubuntu workstations in the Snellius computer rooms for this lab session. This ICT FAQ may provide links to more information on how to use these workstations. Download Gephi 0.9.2 for windows or Gephi 0.9.2 for Linux (mirrors provided because of slow speed of gephi.org downloads).
The main goal of this lab session is to become familiar with Gephi (experimental beta-software to visualize networks for research purposes) and its input format. At the end of this session you should be able to import and visualize raw network data with labeled nodes and labeled and/or weighted edges (directed or undirected), and you should understand how to map edge and node size and color to structural network properties such as the node degree. You should be able to export computed node data and be able to export a vector graphic PDF of your network. There is no deliverable for this lab session.
Teams work on a course project for 60% of the course grade. The project is about a certain topic related to social network analysis, and the project consists of:
Instructions for the course project paper are available.
This list of projects is shown below. Take a look at the paper, before choosing a topic. E-mail the lecturer at email@example.com with your topic preference and names of the two team members. First come, first serve. Your topic is not confirmed until you receive an e-mail from me. You have until September 26 to e-mail your preferred topic. After that, a final division of topics and formation of teams will be made on September 27 during the lecture. Prefix [Chosen] indicates a topic is no longer available.
This list is still updated regularly as teams are formed and topics are chosen.
Note: scientific papers (ACM, Elsevier, etc.) can often only be opened from within the university domain (or from home via SSH/VPN/etc.). IEEE Explore papers can often be opened by looking them up via computer.org. Alternative links and preprints of papers can often be found through Google Scholar by searching for "title of the paper".
Some students have expressed interest in additional reading material to help freshen up on skills and knowledge required for this course.
See the e-Studyguide for a more general description.
Topics include: SNA from a CS perspective (graph representation, complexity issues, examples), Graph Structure (power law, small world phenomenon, clustering coefficient, hierarchies), Paths and Distances (neighborhoods, radius, diameter), Spidering and Sampling (BFS, forest fire, random walks), Graph Compression (graph grammars, bitwise tricks, encryption, hashing), Centrality (degree centrality, closeness centrality, betweenness centrality, rating and ranking), Centrality and Webgraphs (HITS, PageRank, structure of the web), Community Detection (spectral clustering, modularity), Visualization (force-based algorithms, Gephi, NodeXL), Graph Models (random graphs, preferential attachment), Link Prediction (structure, semantics, prediction algorithms, graph mining), Contagion (diffusion of information, spreading activation, gossipping) and Privacy and Anonymity ((de-)anonymizing graphs, ethical aspects, privacy issues) and various other topics that have been added over the years but are not yet in the list above.