Sustained Vertex Cover on Temporal Graphs

Results

All of the raw results are placed in the file result.txt.

Dataset

Descriptions

We consider three types of datasets, including real-world and generated temporal graphs, each of which is processed in a certain way or follows specific rules for generation. The details of our processing rules and generation rules are placed in Appendix E. Our implementations are placed in build/ (including data_shrink.cpp, gen_fail.py, and gen_random.py)

Due to the file size constraint, we only upload part of datasets with (relatively) small sizes. The dataset can be found as follows.

• SNAP temporal networks (https://snap.stanford.edu/data/index.html#temporal)
  • msg (https://snap.stanford.edu/data/CollegeMsg.html)
  • email (https://snap.stanford.edu/data/email-Eu-core-temporal.html)
  • mathoverflow (https://snap.stanford.edu/data/sx-mathoverflow.html)
  • askubuntu (https://snap.stanford.edu/data/sx-askubuntu.html)
  • superuser (https://snap.stanford.edu/data/sx-superuser.html)
  • wiki (https://snap.stanford.edu/data/sx-superuser.html)
  • stackoverflow (https://snap.stanford.edu/data/sx-superuser.html)
• SNAP Internet peer-to-peer networks (https://snap.stanford.edu/data/index.html#p2p)
  • p2p-Gnutella04 (https://snap.stanford.edu/data/p2p-Gnutella04.html)
  • p2p-Gnutella08 (https://snap.stanford.edu/data/p2p-Gnutella08.html)
  • p2p-Gnutella24 (https://snap.stanford.edu/data/p2p-Gnutella24.html)
  • p2p-Gnutella30 (https://snap.stanford.edu/data/p2p-Gnutella30.html)
  • p2p-Gnutella31 (https://snap.stanford.edu/data/p2p-Gnutella31.html)
• E-R random graphs

Compile and Run for Data Processing/Generation

• Processing for the first type of data: data_shrink.cpp. The original data should be placed in data/temporal, and the processed data should be placed in the same directory.

  • Compile:

  cd build
  make data_shrink

  • Run:

  ./data_shrink 86400 <original instance dir> <processed graph dir>

  • Example:

  ./data_shrink 86400 ../data/temporal/CollegeMsg.txt ../data/temporal/day_CollegeMsg.txt

• Processing for the second type of data: gen_fail.py. The original data should be placed in data/p2p, and the processed data would be placed in the same directory.

  • Run:

  cd build
  python3 gen_fail.py

• Generating the third type of data: gen_random.py. The generated data would be placed in data/random.

  • Run:

  cd build
  python3 gen_random.py <lifetime T> <number of vertices n> <connecting probability p> <instance index i>

  • Example:

  python3 500 100 0.1 1

Dependencies

• One of our VC algorithms (mini) uses Gurobi Optimizer version 9.5.1

Compile

Please modify the INC and CPPLIB in the Makefile according to your Gurobi location

cd build
make main

If you just want a version without the dependecy of Gurobi (which only includes algorithms edge and maxd), then you can try

cd build
make main_no_mini

Run

./main <instance> <lifespan d> <VC-alg>

or

./main_no_mini <instance> <lifespan d> <VC-alg>

• instance: Path to instance
• lifespan d: Vaule of lifespan d
• VC alg: Which vertex cover algorithm to run. Valid values: edge/maxd/mini for main; edge/maxd for main_no_mini.

Output: The result would be wrote in build/result.log, including the results for both online algorithms and offline algorithms.

Example

./main_no_mini ../data/temporal/day_CollegeMsg.txt 5 edge