First, we implement an existing algorithm by Rai et al. for constructing a connected DS of graph G(V ,E) that is commonly used in telecommunications [57] . We call this algorithm ''DS-RAI''. It consists of three phases: (1) constructing an independent DS named S, (2) finding a set of nodes C(V \S to connect nodes in S by constructing the Steiner tree between the nodes in S, and (3) pruning the DS defined on nodes S|C to reduce the number of nodes in the DS. More specifically, the algorithm works as follows. In phase 1, each node is colored white. A white node u that is connected to most other white nodes is taken from V , colored black meaning that it is a ''dominator,'' and added to S. All neighboring nodes of u are colored gray meaning that they are ''dominatees'' and added to V \S. Previous steps are repeated on the remaining white nodes in V until all nodes of V are either colored black and added to S, or colored gray and added to V \S. In phase 2, a gray node from V \S that is connected to the largest number of black nodes in S is selected, colored dark gray meaning it is a ''connector,'' and added to C. The algorithm then checks whether node set S|C is connected and if so, it stops; otherwise, the algorithm selects the next gray node from V \S that is connected to the largest number of black nodes in S and repeats the entire process until node set S|C becomes connected. In phase 3, ''redundant'' nodes are deleted from the connected DS defined on S|C to reduce its size as follows. Let G½V ' denote a subgraph of G induced on a subset of nodes V '(V . The algorithm selects a node u with the minimum degree in G½S|C and checks whether the DS defined on S|C\fug remains a Figure 3 . Graphlets, automorphism orbits, and GDVs. (A) All 9 graphlets with 2, 3 and 4 nodes, denoted by G 0 , G 1 ,…,G 8 ; they contain 15 topologically unique node types, called automorphism orbits, denoted by 0, 1, 2, …, 14. In a particular graphlet, nodes belonging to the same orbit are of the same shade (see [47] for details). (B) An illustration of the GDV of node v; it is presented in the table for orbits 0 to 14: v is touched by 4 edges (orbit 0), end-nodes of 2 graphlets G 1 (orbit 1), etc. The figure is taken from [53] . doi:10.1371/journal.pone.0023016.g003 connected DS of G. If so, the node u is removed from S|C. Otherwise, it remains in S|C. This is repeated for all nodes in S|C, in the order of their increasing degrees. The node set resulting from node removals from S|C in step 3 is the final DS produced by DS-RAI algorithm. An illustration is presented in Figure 4 A.