Sampling Analysis using DNA

In this repo, we provide a set of scripts that allow for the analysis of dynamic graphs generated by sampling a given network with DNA (Dynamic Network Analyzer).

These analyses include an attempt to find the best solution for the MCNC (Maximum Connected Netwrork Coverage) problem, determine properties of sampled graphs as they grow, understand the impact of parameters on the sampling performance, and visualizations of sampled graphs while growing.

Java Code

The java code used for the execution can be found in the java/ directory. The three main execution classes (Analysis.java, Plot.java, and Visualization.java) are all located in the package dna.sampling.

Ant Build File

To build jars for the three main Java classes (analysis.jar, plot.jar, and vis.jar), an ant build file is provided in analysis/build.xml.

Bash Scripts

In analysis/, we provide a set of bash scripts that can be used for performing the afforementioned analyses and generate html files for displaying the results.

Execution

For the execution of analysis and the following plotting, we use the JOBS scripts.

analysis.sh

Performing the analyses using analysis.jar.

plot.sh

Combining the results of multiple sampling algorithms into single plots using plot-jar.

vis.sh

Generation of animated gifs while sampling a given graph using vis.jar.

HTML Generation

html-analysis.sh

Generation of html/php files for the analysis results. Here, the results from a "category" are grouped into a single page to allow for an easy comparison.

html-vis.sh

Generation of html/php files for the visualization results. For each sampled graph, a separate html/php page is generated displaying a visualization for each sampling algorithm.

Results

A set of these results, including the generated html files can be found on dynamic-networks.org.

jar Parameters

analysis.jar

Expecting 15 parameters:
   0: main data dir
   1: main plot dir
   2: graph type (RANDOM, BA, READ, READ_EDGE_LIST, GRID2d, GRID3d)
   3: graph parameters (separated by __)
   4: sampling type (BFS, DFS, DFS_JUMP, DFS_RANDOM_JUMP, DFS_RANDOM, FOREST_FIRE, FOREST_FIRE_NR, FRONTIER_SAMPLING, GREEDY_ORACLE, MOD, RANDOM_WALK, RANDOM_WALK_NR_JUMP, RANDOM_WALK_NR, RESPONDENT_DRIVEN, SNOWBALL, UNIFORM)
   5: sampling parameters (separated by __)
   6: start node strategy (HIGHEST_DEGREE, HIGHEST_RANDOM_DEGREE, HIGHEST_RANDOM_DEGREE_SUM, RANDOM)
   7: sampling stop (Seeing, Visiting)
   8: cost per batch
   9: resource
  10: runs
  11: batches
  12: metrics (DD, ASS, APSP, MOD, CC, M, EXT) separated by __
  13: connectivity type (WeaklyConnected, StronglyConnected)
  14: walking type (AllEdges, InEdges, OutEdges)

plot.jar

Expecting at least 3 arguments:
  0: main data dir
  1: plot dir
  2: type (ALL_IN_DIR, LIST_OF_NAMES)
  [3,4,...: list of names]

vis.jar

Expecting 10 parameters:
   0: main plot dir
   1: graph type (RANDOM, BA, READ, READ_EDGE_LIST, GRID2d, GRID3d)
   2: graph parameters (separated by __)
   3: sampling type (BFS, DFS, DFS_JUMP, DFS_RANDOM_JUMP, DFS_RANDOM, FOREST_FIRE, FOREST_FIRE_NR, FRONTIER_SAMPLING, GREEDY_ORACLE, MOD, RANDOM_WALK, RANDOM_WALK_NR_JUMP, RANDOM_WALK_NR, RESPONDENT_DRIVEN, SNOWBALL, UNIFORM)
   4: sampling parameters (separated by __)
   5: start node strategy (HIGHEST_DEGREE, HIGHEST_RANDOM_DEGREE, HIGHEST_RANDOM_DEGREE_SUM, RANDOM)
   6: sampling stop (Seeing, Visiting)
   7: cost per batch
   8: resource
   9: delay for gif video