Execution time (in seconds) of CTD p-value bounds compared to using permutation testing for a variety of network and subset sizes.

In the following timing experiments, each network was approximately 20% connected. Times for CTD’s p-value bounds estimation are reported as the average execution time observed in a sampling of 100 node sets of a given size. In the permutation testing execution times, the overhead time (in seconds) for pre-computing the node ranks is listed separately, and the additional time to perform permutation testing for one node set is denoted by a plus sign, for various subgraph sizes and network sizes.