Online Social Networks and Media
This is the schedule for the project examination. The deadline for submitting your project report is Tuesday 11/2 12:00 noon.
Project Proposal Guidelines
You can find some guidelines for the project report here. Make sure that you start the report early!
Assignment 3 – Part 2
You can now download the second part of Assignment 3. It is due on Wednesday 22/01 in class.
Paper Presentation Guidelines
The presentations will be evaluated based on the quality of the presentation, and the comprehension of the material. The following are some guideline, tips and advice for preparing your presentation.
· You have 20 minutes for the presentation. We will enforce the time limit and cut you off if you have not completed on time. Ten more minutes will be allocated for questions. We may randomly pick someone from the audience to ask a question, so everyone should pay attention.
· You should prepare around 20 slides, given that a slide takes around a minute to talk about on average. Break you presentation into thematic units. The following flow is very common: 1. Motivate why the problem is important and give a high level idea; 2. Define clearly the problem; 3. Present the main idea and the fundamental algorithms; 4. Present the results (experimental or theoretical or both); 5. Conclusion.
· The talk should be self-contained. Do not assume that the audience has read the paper, or some previous work that you consider known. Define all the concepts you need and all the notation that you use. Refer only to related work that you know.
· Since the time for the talk is short, you will need to focus on the important parts of the paper and avoid going through all the details. The goal is to give a summary of the paper and have a clear message. Just because you read all the paper it does not mean that you should present everything. At the same time, you should not skip important information. Focusing on the right part to present is important since it shows that you understood the paper well.
· Prepare the slides carefully. Do not add too much text, and only the math symbols necessary. Do not use full sentences, but rather keywords and short phrases. Make sure the slides are readable and not too loaded. Never ever project parts of the paper pdf.
· Practice! Good talks are the result of a lot of practice even if they seem spontaneous and fun to the audience. Practice the talk several times, and time yourself to make sure you are within the time bounds.
Some fun advice on how to give a bad talk (and more) here.
Project Proposal Guidelines
The suggested length for the project proposal is 1-2 pages. In the header you should have the title of the project, the members of the project and the URL of the web page of the project.
The text body of the project should have three main parts:
1. Problem definition: Describe the goal of your project and the question that you want to answer. Write a few words to motivate why it is important.
2. Methodology: Describe how you will address the problem you defined. What are the steps you will take? Try to be as specific as possible.
3. Evaluation: Explain how you will evaluate your work. Describe the experiments you plan to do and the dataset that will be used.
At the end of the proposal write down the paper that you will present (full citation).
Although it is not mandatory, we suggest that you write the project proposal and the project report in English, so that it is accessible to anyone to read.
You can now download the list of project topics. Let us know of the topic you pick, and email or set up a meeting to discuss the details. If you have your own project proposal please contact us with your suggestion.
The timeline for the projects is as follows:
· Topic 1: Ερμιόνη Μάστορα, Δημήτρης Ζαβαντής
· Topic 2: Κωνσταντίνος Νούλης, Απόστολος Κούτρας
· Topic 3: Θωμαή Κόρκου, Παπαδημητρίου Κατερίνα
· Topic 4: Λάμπρος Βατσιλίδης
· Topic 5: Ελευθερία Λιούκα, Θανάσης Κουφούλης
· Topic 6: Μαρία Σπάη, Φάνης Γιάχος
· Topic 7: Μικέλα Κακαράντζα
· Topic 10: Δανιήλ-Δημήτριος Πρόσκος
· Topic 11: Νικόλαος Παροτσίδης
· Topic 13: (Distributed Community Detection at Different Time Scales) Δημήτριος Γεώργιος Ακεστορίδης
· Topic 13: (Time-Aware Link Prediction) Νικόλαος Χαλιάσος
Assignment 3 – Part 1
You can now download the first part of Assignment 3. The first part of Assignment 3 is due on Wednesday 08/01 in class.
Instructions for Presentation
The presentations will take place at the end of the lecture on 27/11 in class. We will start at 4:00pm exactly. Each presentation should not take more than 10 minutes + 5 minutes for questions. This will be strictly enforced.
The general structure for the presentation should be as follows:
· 1-2 slides for describing the model (this is known so you should just sketch it)
· 1-2 slides per measurement that you did with your comments/findings
· 1 slide for conclusion.
The assignment is due on Wednesday 27/11 in class. The goal of this assignment is for you to familiarize yourself with network generation models.
There will be 4 groups of 4 people working on one of the following models:
1. Configuration model (i.e., graphs following a given degree sequences)
Generate power law degree sequences, for different exponents α, where 2 £ α £ 3
2. Preferential attachment and copying model
3. Small world (using the caveman and Watts-Strogatz model)
4. Forest Fire Model
You should implement the model(s) and compute the following measures:
(a) the degree distribution
(b) the clustering coefficient
(c) the effective diameter
You should prepare the following:
1. A short write-up to be handed in at the beginning of the class. The write-up should include:
(a) A short report on your implementation of the model reporting any assumptions that you have made
(b) Plots of
(i) the degree distribution with the number N of nodes, for N = 1,000 to 10,000
(ii) the clustering coefficient with the number N of nodes for N = 100 to 1,000
(iii) the effective diameter with the number N of nodes for N = 100 to 1,000
For each of the above measures, draw at least three different plots for different values of the input parameters of the corresponding model (for example of parameters a and d for the copying model, or the exponent α of the power-law). You should choose carefully the values of these parameters, so that the plots show how each of them affects the corresponding measure. Provide a short explanation/justification of the plots.
2. A short presentation (5-10min) to be presented in class.
Form groups, and send us an email with the members of the group and a ranking of the models according to the group preference. Models will be handed out on First-Come-First-Serve basis.
1. Configuration Model: Μικέλα Κακαράντζα, Ερμιόνη Μάστορα, Δημήτρης Ζαβαντής, Λάμπρος Βατσιλίδης
2. Preferential Attachment and Copying Model: Θωμαή Κόρκου, Θανάση Κουφούλη, Ελευθερία Λιούκα, Κατερίνα Παπαδημητρίου
3. Small World Models: Γιάχος Θεοφάνης, Σπαή Μαρία, Κούτρας Απόστολος, Νούλης Κων/νος
4. Forrest Fire Model: Δημήτριος-Γεώργιος Ακεστορίδης, Νικόλαος Παροτσίδης, Δανιήλ-Δημήτριος Πρόσκος, Νικόλαος Χαλιάσος
The assignment is due on Wednesday 6/11 in class. The goal of this assignment is for you to apply the techniques we described in class for observing and computing power-laws.
1. Choose a graph dataset (you can find a list of such datasets at the Resources page). The graph should have at least a few thousand nodes.
2. Compute the degree distribution and produce the following plots:
i. The degree distribution in linear (not log-log) scale
ii. The degree distribution in log-log scale
iii. The degree distribution in log-log scale using exponential binning
iv. The cumulative degree distribution in log-log scale.
v. The Zipf plot (log-log scale) of the degree distribution
3. Compute the exponent of the power-law distribution
You can read more about the different methods of plotting the distribution and estimating the power-law exponent at:
· M. E. J. Newman, Power laws, Pareto distributions and Zipf's law, Contemporary Physics
Prepare a short write-up to be handed in at the beginning of the class. The write-up should include:
1. A short (1-2 sentences) description of the dataset
2. The plots (i) – (v) described above along with a few observations for each of them.
3. The value of the exponent and how you derive it (briefly)
4. Whether the distribution follows the power law and why.