Assignment 1 – Task B
Focus on Task B this week.
• Discuss aims of task B.
• Discuss experiment setup and scenarios for task B. • Discuss report structure.
Jeffrey Chan (RMIT University)
Assignment 1 Notes
Lecture 5 1 / 9
Task B Aims
• Empirically evaluate the graph representations and your implementions for the described scenarios.
• Experience with explaining observed results to what you understand of the representations and implementations.
• Communicate about it.
Jeffrey Chan (RMIT University)
Assignment 1 Notes
Lecture 5 2 / 9
Task B Experiments Setup
• Start with provided association graph or your own randomly generated graph of certain size.
• 3 Scenarios: • Removals
• k-nearest Neighbours • Update edge weights
• We want to experiment how density of the graph affects the results (L, M, H).
Jeffrey Chan (RMIT University)
Assignment 1 Notes
Lecture 5 3 / 9
Task B Experiments Generation – Density
• Start with provided association graph.
• To vary the density, you would need to add/remove edges to the
facebook graph to the required density.
• Three settings – Low, medium and high density.
• For each setting, generate a number of datasets.
Jeffrey Chan (RMIT University)
Assignment 1 Notes
Lecture 5 4 / 9
Task B Experiments Generation – Removals
• Start with a graph with tested density.
• Generate vertex removals, uniformly generating vertex labels from
existing labels in the graph.
• Generate, remove from graph and time how long it took. Do this over a large number of removals, then take the average.
• Repeat for other datasets of same density.
• Repeat for edge removals.
Jeffrey Chan (RMIT University)
Assignment 1 Notes
Lecture 5 5 / 9
Task B Experiments Generation – k-nearest neighbours
• Start with a graph with tested density.
• Generate vertex to do nearest neighbour, and compute and time. • Vary in/out and different k’s.
• Average across a number of nearest neighbour computations.
Jeffrey Chan (RMIT University)
Assignment 1 Notes
Lecture 5 6 / 9
Task B Experiments Generation – Weight updates
• Start with a graph with tested density.
• Generate random edges to update weights. Randomly generate
weights.
• Generate update operations and time how long it took. Do this over a large number of updates, then take the average.
• Repeat for other datasets of same density.
Jeffrey Chan (RMIT University)
Assignment 1 Notes
Lecture 5 7 / 9
Task B – Report Structure
General structure:
• Data Generation and Experimental Setup:
• experimental setup
• how scenarios are geneated
• how you measured the timing results
• described how you generated the data labels to add, remove and
compute neighbours/shortest paths. • Evaluation:
• Analyse, compare and discuss your results across different densities, representations and scenarios.
• Explain why you think the results are as you observed.
• Can compare with theoretical analysis.
• Summary: What you recommend for different scenarios, densities etc.
Jeffrey Chan (RMIT University)
Assignment 1 Notes
Lecture 5 8 / 9
Task B – Report Structure
General structure:
• Data Generation and Experimental Setup:
• experimental setup
• how scenarios are geneated
• how you measured the timing results
• described how you generated the data labels to add, remove and
compute neighbours/shortest paths. • Evaluation:
• Analyse, compare and discuss your results across different densities, representations and scenarios.
• Explain why you think the results are as you observed.
• Can compare with theoretical analysis.
• Summary: What you recommend for different scenarios, densities etc.
Hint: Use tables, plots, bar charts, to summaries your results.
Jeffrey Chan (RMIT University)
Assignment 1 Notes
Lecture 5 8 / 9
Extra Comments
• For printVertices(PrintWriter os) and printEdges( … ), use the PrintWriter. E.g. os.print(…);
• For the arrays, I suggest to dynamically resize, as we don’t know maximum sizes.
Jeffrey Chan (RMIT University)
Assignment 1 Notes
Lecture 5 9 / 9