News
 The textual comments from the 2016 evaluation forms are available here.
 As announced, all course projects have been graded. Thank you all for your participation! There is an opportunity to come collect feedback on January 10 or 13.
Lectures: Fridays from 11:15 to 13:00 in the fall semester of 2015 in
Snellius room 402 403 313
Lab sessions (not every week): Fridays from 9:00 to 10:45 in
Snellius room 302/304
Lecturer: dr. Frank Takes  f.w.takes@liacs.leidenuniv.nl, room 157b
Teaching assistant: Govert Brinkmann  g.g.brinkmann@umail.leidenuniv.nl
Prerequisites: a CS(related) bachelor; in particular basic knowledge of Algorithms 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)
Study points: 6 ECTS
Network with 1458 nodes and 1948 edges.
Date  First slot (9:0010:45)  Second slot (11:1513:00)  

1.  Sep 9, 2016  Lecture 1: Introduction and small world phenomenon  
2.  Sep 16, 2016  Lab session: Gephi and Assignment 1  Lecture 2: Network topology and centrality  
3.  Sep 23, 2016  10.00: Lecture 3: Guest lecture by prof. dr. P. Cresenzi (University of Florence)  11.15: Lab session: NetworkX and Assignment 1  
4.  Sep 30, 2016  Lab session: work on Assignment 1  Lecture 4: Network formation and community detection Presentation 0 

Oct 5, 2016  Deadline for Assignment 1  
5.  Oct. 7, 2016  Lab session: work on Assignment 2  Lecture 5: Network evolution and models  
Oct. 14, 2016  Lab session: work on Assignment 2  No lecture  
6.  Oct. 21, 2016  Lab session: work on Assignment 2  Lecture 6: Structure of the web and network visualization  
7.  Oct. 28, 2016  Lab session: Course project framework and work on Assignment 2 
Presentation 1: Sampling methods (LR) Presentation 2: Virality & Outbreak detection 2 (HR) 

Nov 2, 2016  Deadline for Assignment 2  
8.  Nov. 4, 2016  Presentation: Graph compression/representation (EZ) Presentation: Shortest paths 1 (BB) 
Presentation: Shortest paths 2 (KL) Presentation: Signed link prediction (FW) 

9.  Nov. 11, 2016  We start at 10.00. Presentation: Betweenness centrality (HP) 
Presentation: Link prediction (DG) Presentation: Community detection 1 (QR) 

10.  Nov. 18, 2016  Peer review session  Guest lecture by André Vermeij (Kenedict Innovation Analytics)  
11.  Nov. 25, 2016  Presentation: Graph Partitioning (DH) Presentation: Network dissolution (GJ) 
Presentation: Network motifs (DS) Presentation: Diameter computation (SZ) 

Nov. 29, 2016  Deadline for Intermediary Paper Check  
12.  Dec. 2, 2016  Presentation: Network deanonymization (PH) Presentation: Closeness centrality 2 (RH) 
Code review session  
13.  Dec. 9, 2016  Presentation: Closeness centrality 1 (SB) Presentation: Virality & Outbreak detection 1 (BK) 
Presentation: Advances in community detection (TnT) Presentation: Personalized PageRank (GR) 

Dec. 14, 2016  Deadline for Course Project Paper  
Dec. 16, 2016 
Evaluation sessions


Dec. 22, 2016  Course end. Grades will be submitted to the student administration 
Some hints:
We will work on a framework for the course project.
The idea is that this session will help you set up your experimental pipeline for the project.
As a final step, consider glueing the above together, for example using some simple bash scripts that read all network datasets from a particular data/ folder, then run these datasets on some executables in a bin/ folder, storing the results for each dataset in a results folder or file. Here you can heavily rely on standard input/output redirection.
Recall that the above is meant as a guideline; other setups are also possible.
We will use the UNIX/Linux workstations in Snellius room 302/304 for this lab session.
If you really must, you can attempt to use Windows, fully at your own risk (you will at least need to edit gephi.conf so that it points to the correct Windows JRE version 6 or 7 (and not 8)).
Some information on the workstations is provided by the ISSC, see their pages on the
workstations and
SSH access. Also see this
ICT FAQ.
There is no deliverable for this lab session. The main goal of this lab session is to become familiar with Gephi (experimental betasoftware to visualize networks for research purposes) and its input format.
At the end of this session you should be able to 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.
Some students with nonCS backgrounds have expressed interest in additional reading material to help freshen up on skills and knowledge required for this course.
Teams work on a course project for 60% of the course grade. For this project they pick one of the topics listed below. Each topic has an associated list of papers which have to be studied. Papers on a particular topic all consider different algorithms or methods for solving roughly the same problem. The goal of the project is to make a comparison of at least two of these papers based on experiments using real social network data. So the project consists of:
Suggestions for topics are listed below, and you are encouraged to pick one of these topics (as a team). You are also allowed to suggest your own problem (topic) in the field of social network analysis, assuming you are have found at least two scientific CS papers that suggest different techniques or algorithms for solving this problem (so, addressing this same topic). If you choose a topic, then you are also encouraged to look up additional papers in this problem domain to study and compare to the paper that you presented, as the papers to study are merely "simple" suggestions. For some topics, there exists an overview/review paper that discusses many more papers that study the same (type of) problem.
Note: scientific papers (ACM, Elsevier, etc.) can often only be opened from within the university domain (or from home via SSH/nxClient/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.
Instructions for the course project paper » (2015 version still)
See the eStudyguide 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 (forcebased 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).