Online Social Networks and Media Homework

Home Homework Slides & References Reading Material Resources

Project Proposal Guidelines You can find some guidelines for the project report here. Make sure that you start the report early! 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 25 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-25 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. Presentation Schedule: January 8: · Δανιήλ-Δημήτριος Πρόσκος, Γεωργία Παπασταύρου. · Πάρης Τσανταρλιώτης January 15: · Αντώνης Κουρσούμης, Μιχάλης Κολοζώφ · Κωνσταντίνος Τζιορτζιώτης, Βαγγέλης Καζάκος · Δημήτρης Μπέστας, Δημήτρης Σέρμπος 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. Projects The list of projects is available here. The assignment is First-Come-First-Serve. The timeline for the projects is as follows: Week before Christmas: Submit a ~2-page project proposal outlining what you plan to do. This should include the topic of your presentation January 8 and 15: Presentations. Present one or more papers or background material related to your project February 6: Submit full project. Project Assignments: · Topic 13 (Mining Greek Political Twitter): Κωνσταντίνος Τζιορτζιώτης, Βαγγέλης Καζάκος · Topic 3: Αντώνης Κουρσούμης, Μιχάλης Κολοζώφ · Topic 2: Πάρης Τσανταρλιώτης · Topic 4: Δανιήλ-Δημήτριος Πρόσκος, Γεωργία Παπασταύρου. · Topic 8: Δημήτρης Μπέστας, Δημήτρης Σέρμπος Assignment 3 The assignment is due on Thursday 27/11 in class. The assignment has two parts. a. In class we described a variety of algorithms and techniques that make use of the eigenvectors and eigenvalues of a matrix related to the adjacency matrix of the graph. Write a summary of all the different uses we have described. b. In slide 46 of Lecture 6 we describe an efficient procedure for computing the product of the full PageRank matrix with a vector x. Prove that the procedure correctly computes the product. (If it helps, you can assume that x is a probability vector, and hence the sum of all of its entries is 1, and that the vector v is the uniform vector). Assignment 2 The assignment is due on Thursday 20/11 in class. The goal of this assignment is for you to familiarize yourself with the community detection problem, algorithms and tools. For this assignment, you are asked to apply two community detection algorithms (e.g., based on spectral analysis, modularity, betweenness centrality, or some other algorithm that you can find in the graph community survey on the references by Fortunato). You should find one dataset for which the ground truth is available, and one dataset for which there is no ground truth and compare the results of the two algorithms that you selected using one metric appropriate for each case. You do not need to implement the algorithms yourselves; instead you are encouraged to use any of the many implementations available online. For information on datasets and algorithms, you can check the Fortunato’s survey, and the Resources page of the course. Using Gephi is inot advised since it has been observed to not work well in some case. The assignment should be done in groups of at most three people. Prepare a short report with your results. The report should include: · A short description of the algorithms you used · A short description of the tool/implementation that you used. · A description of the datasets that you considered. · The results of the comparison and your observations. Model Assignments: 1. Forrest Fire Model: Π,Τσανταρλιώτης, Α.Κουρσούμης, Β. Μπακάλης, Κ.Λιόντης 2. Small World Models: Δανιήλ-Δημήτριος Πρόσκος, Αικατερίνη Καρανάσιου, Γεωργία Παπασταύρου 3. Configuration Model: Κολοζώφ Μιχάλης, Μπέστας Δημήτρης και Σέρμπος Δημήτρης 4. Preferential Attachment and Copying Model: Ε. Καζάκος, Κ. Τζιορτζιώτης. Assignment 1 The assignment is due on Thursday 6/11 in class. The goal of this assignment is for you to familiarize yourself with network generation models. There will be 4 groups working on one of the following models: 1. Configuration model (i.e., graphs following a given degree sequences, and given expected degree sequences) [3 team members] Generate power law degree sequences, for different exponents α, where 2 £ α £ 3 2. Preferential attachment and copying model [3 team members] 3. Small world (using the caveman and Watts-Strogatz model) [2 team members] 4. Forest Fire Model (as described in the class slides) [3 team members] 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 also implement the Erdos-Renyi random graph model, and compute the above measures to make a comparison with your model. 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. For power-law distributions use the three different ways of plotting the distribution and compute the power-law exponent. 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. Compute the same for the random graph model. 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.