Social Network Analysis for Computer Scientists

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:
source snacsenv/bin/activate
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

1. Take some time to do the NetworkX tutorial.
2. Have a look at functionality to read and write graphs from/to disk, and in particular learn how to import an edge list.
3. A lot of the common network metrics you may want to compute are implemented as NetworkX function or NetworkX algorithm. Become familiar with these, for example by computing measures such as degree assortativity, clustering, density, diameter and average distance.
4. Try to load the network from the first lab session (/vol/share/groups/liacs/scratch/SNACS/small-gephiready.tsv) into NetworkX, and investigate some characteristic properties of the network, such as the degree distribution. Use the read_edgelist function and remember to select the correct separator (tab).
5. Get the Epinions network from the SNAP repository. Compute some common characteristics such as the degree distribution, and visualize them using appropriate figures of distributions, for example using Matplotlib.
6. What are the differences between NetworkX and Gephi in terms of visualization and analysis capabilities?
7. Proceed with Exercise 2 of Assignment 1.

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

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:

• Giving a 30-minute presentation (+15 minutes for questions) of the paper corresponding to the topic. At least a Powerpoint/PDF presentation and some demonstration of an implementation or visualization has to be given. Teams are also expected to provide feedback on some of the presentations given by their fellow students during the lectures.
• Gathering and implementing the algorithms and/or techniques from the different papers, and running experiments on at least five large real-world network datasets. Thus, some programming has to be done. Teams will also give feedback on the code produced by other teams in the code review session. Some papers introduce multiple techniques. In that case, choose a logical subset to compare, and motivate your choice.
  Datasets can for example be found at SNAP, KONECT, BigDND, Networks Repository, ICON, LASAGNE and ASU. Certain topics need particular datasets (e.g. with timestamps, signed links, etc.), which should of course be taken into account when selecting datasets.
  As a rule, the course project paper should always have one novel (new) aspect compared to the papers on which it is based. For example, a new tweak to an existing algorithm, a large number of datasets to test the algorithms to find a relation between the network characteristics and the performance, a new performance metric to evaluatie the algorithms, a new type of visualization of the algorithm or results, an improvement of a proof related to the algorithm, etc. In case of doubt about the contribution, contact the course staff; you can always ask for help.
• Writing one 6 to 10 page paper. In the paper the different techniques are analyzed and compared in detail using extensive experiments. The paper, to be written in LaTeX, has to follow the format of an actual scientific paper. Students will also give feedback on the paper produced by another team in the peer review session.

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 f.w.takes@liacs.leidenuniv.nl 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.

1. [Chosen] Anomaly detection in networks
2. [Chosen] Betweenness centrality 1
3. Betweenness centrality 2
4. [Chosen] Closeness centrality 1
5. [Chosen] Closeness centrality 2 (top-k)
6. [Chosen] Community detection 1
7. [Chosen] Community detection 2
8. [Chosen] Community detection 3
9. [Chosen] Community detection 4
10. [Chosen] Data errors in networks
11. Diameter computation
12. [Chosen] De-Anonymization of networks
13. Graph compression
14. [Chosen] Influence spread and virality 1
15. [Chosen] Influence spread and virality 2
16. [Chosen] Link prediction
17. [Chosen] Link prediction in signed networks
18. [Chosen] Motifs in networks
19. Motifs in multilayer networks
20. [Chosen] Motifs in temporal networks
21. [Chosen] Neighborhood approximation
22. [Chosen] Network embeddings 1
23. Network embeddings 2
24. [Chosen] Personalized PageRank
25. [Chosen] Resilience of networks
26. [Chosen] Sampling networks
27. [Chosen] Shortest paths 1
28. [Chosen] Shortest paths 2
29. Triangle counting
30. Visualization algorithms 1
31. [Chosen] Visualization algorithms 2
32. Visualization algorithms 3

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.

• To brush up on your Python programming skills, you could do Lecture 0, 1 and 4 of these Scientific Python Lectures.
• To freshen up your LaTeX skills, you could do for example this tutorial.
• MIT has a nice online course on discrete mathematics. Relevant chapters: 5, 6 and 7.
• The (Dutch) Leiden courses Algoritmiek (Algorithms) and Datastructuren (Data structures) might be also interesting to browse through.
• Basic knowledge of the concepts in machine learning and data mining are provided, for example, at the Wikipedia machine learning page.

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.

The course was also given in 2014, 2015, 2016, 2017 and 2018.