In this paper we introduce two novel algorithms that are able to efficiently determine an approximation to the minimum dominating set problem, and at the same time, they will preserve the quality of the solution to an acceptable level. We compare these two algorithms with three existing algorithms, for a large number of synthetic datasets, and for several real world social networks. For experiments, we use social network generators that create both power-law and random networks, and a few real network datasets made available by the Stanford Network Analysis Project. Our experiments show that the proposed algorithms are viable, and in many instances, preferable for determining the minimum dominating set of a social network.
Today, online social networks are used by an ever
increasing number of people. For instance, Facebook has currently
more than 1.35 billion users, LinkedIn has over 332
million users, and 1 out of 4 people from the entire world is an
active user in at least one existing social network
Social networks existed long before the Internet. As
early as around 1200-1450 such social networks existed in
pre-Hispanic Southwest in the current United States. The
growth, collapse, and change of such social networks are
reflected in thousands of ceramic and obsidian artifacts
(Mills et al. 2013). More recently, in the first half of the
20th century, the social network analysis discipline was
started by the sociology community
An important feature in a social network is the ability to communicate quickly within the network. For instance, in an emergency situation, we may need to be able to reach to all network participants, but only a small number of individuals in the network can be contacted directly. However, if all individuals from the network are connected to at least one such individual who can be contacted directly (or is one of those individuals) then the emergency message can be quickly sent to all network participants. This scenario can be modeled by what is known as the dominating set problem. This is formally described below.
A set DS N of nodes in a network G = (N, E) is a
dominating set if every node x N is either in DS or adjacent to
DS
Approximation algorithms for determining the minimum
dominating set exist in the literature, with the most
common one being an adaptation of the greedy algorithm for
determining a set cover
Extensive experimental results have been performed for
scale-free networks (that model social networks well)
using either the basic greedy algorithms for approximating
the minimum dominating set size
In this paper we introduce two novel algorithms that are
able to determine efficiently an approximation to the
minimum dominating set problem and, simultaneously, they
will preserve the quality of the solution to an acceptable
level. Those two algorithms: one extends the greedy
algorithm mentioned earlier, and the other is an improvement
of an algorithm that is also introduced in
The remaining of this paper is structured as follows. Section “Dominating Set Algorithms” introduces the two new algorithms that we use in this paper. In addition, in this section we also present three existing algorithms that we use for experimental evaluation. Section “Datasets” describes how we generate the synthetic social networks, and provides a description of the used real datasets. In section “Experiments and Results” we perform a detailed experimental evaluation of our algorithms using the datasets presented in the previous section. Section “Discussion and Future Extension” presents conclusions and a summary of future extension for our work.
In this section we describe the greedy algorithms we use to approximate the minimum dominating set. Algorithms 3 and 4 are new, while the rest are existing algorithms against which we compare ours.
The first algorithm (Algorithm 1 or Alg. 1) is the
standard greedy algorithm that choses at each step, one node
that covers the maximum number of currently uncovered
nodes
Input: G = (N, E) – a social network; Output : DS – a dominating set for G; DS = ; while ∃ white nodes do choose v ∈ {x ∈ N | w(x) = max u ∈ N |W(u)|}; DS := DS ∪ { v }; // Delete the vertex v and // its adjacent edges from G.
G = (N \{v}, E \{(x, y) ∈ E| x = v or y = v)}); end while; end Algorithm 1.
The second algorithm (Algorithm 2 or Alg. 2) starts by
finding the set of all nodes of degree exactly one (D1).
Then finds the set of nodes adjacent to D1 (Neighbors(D1)).
Obviously, any dominating set must contain
Neighbors(D1). Next, we run the Alg. 1 on the subgraph induced
by N \ Neighbors(D1). This second algorithm is referred in
previous work as VRegularGreedy
Input: G = (N, E) – a social network; Output : DS – a dominating set for G; D1 = { x ∈ N | degree(x) = 1}; Neighbors(D1) = { x ∈ N | y ∈ D1 and (x, y) ∈ E } DS = Neighbors(D1); // E’ – contains all edges from E that have // both ends in N \ {Neighbors(D1) D1}.
G’ = (N \ {Neighbors(D1) D1}, E’); Algorithm 1 (G’, DS’);
DS = Neighbors(D1) DS’; end Algorithm 2.
The third algorithm (Algorithm 3 or Alg. 3) improves the running time of Algorithm 1 by removing both the black and gray nodes from the remaining network, thus reducing significantly at each step the size of the network. Since all the time the remaining nodes are white, the use of node coloring is no longer useful. This algorithm is described next: Algorithm 3 (G, DS) is
Input: G = (N, E) – a social network; Output : DS – a dominating set for G; DS = ; while N do choose v ∈ {x ∈ N |
degree(x) = max u ∈ N (degree(u))}; DS := DS ∪ { v }; // Delete the vertex v, Neighbors({v}), and // their corresponding edges. // The remaining edges are labeled E’
G = (N \{v}\ Neighbors({v},E’ ); end while; end Algorithm 3.
The fourth algorithm (Algorithm 4 or Alg. 4) combines the Algorithms 2 and 3, by including in the dominating set all neighbors of nodes of degree 1, and then by applying Algorithm 3 to the remaining graph. This algorithm is described as: Algorithm 4 (G, DS) is
Input: G = (N, E) – a social network; Output : DS – a dominating set for G; while N do
D1 = { x ∈ N | degree(x) = 1}; Neighbors(D1) = { x ∈ N | y ∈ D1 and (x, y) ∈ E } DS = Neighbors(D1); // E’ – contains all edges in E with both ends // in N \ {Neighbors(D1) Neighbors (Neighbors(D1) )}. G’ = (N \ {Neighbors(D1) Neighbors (Neighbors(D1) ), E’); Main step in Algorithm 3 (G’, v);
DS = Neighbors(D1) { v }; end while; end Algorithm 4.
Note that in the Alg. 4, we also delete all nodes dominated by Neighbors(D1) prior to using Algorithm 3. This is equivalent with deleting the gray nodes along with the black node which is executed in Alg. 3 and it is not performed in Alg. 1.
The last algorithm known as FastGreedy in
Input: G = (N, E) – a social network; Output : DS – a dominating set for G; DS = ; Order vertices in N = {v 1, v 2, … v|N|)}
such that degree(v 1) ≥ degree(v 2) ≥ … ≥ degree(v | N |). i = 1; while (|ji Neighbors (vj)| < |N |) do if (not(Neighbors (vi) j < i Neighbors (vj)))
DS = DS { v i}; i++; end Algorithm 5.
In order to compare the size of dominating sets and
execution times for the above 5 algorithms, we use both
synthetic and real network datasets. All synthetic graphs were
generated using the SNAP library
We generate synthetic datasets using the well-known
Erdos-Renyi random graph model (
To generate ERNetworks we chose the following parameters. First we fix the size of the network, |N |, to 50,000, and we generate ERNetworks for 10 different average degree values (AVG = 5, 10, 15, 20, .., 50). Second we chose a fixed AVG value (AVG = 10) and we use 10 distinct values for the size of N (|N | = 10K, 20K, …, 100K). For each combination of |N | and AVG values we generate 5 distinct networks. The total number of ERNetworks generated is 95 (19 combinations x 5 samples). Note that the size 50K and AVG = 10 is common between the two generation approaches, and therefore it is considered only once.
We generate the same number of ConfNetworks but we change the parameters as follows. For the size of the networks we use exactly the same values, but as a second parameter we use the power-law exponent γ from the powerlaw distribution (P(k) k-γ). For the fixed |N | value (50K) we use the values for γ = 1.7, 1.8, …, 2.6. When we vary the size of networks, we use γ = 2.0. As before, for each combination of |N | and γ we generate 5 district networks and the total number of generated ConfNetworks is 95.
We also use 10 real networks in this work. These
networks are from the SNAP datasets website
To execute our experiments, we implemented the
Algorithms 1 – 5 described in Section “Dominating Set
Algorithms” and the graph random generators described Section
“Datasets” in C++ using the SNAP framework
Figures 1 – 14 show the results of all our experiments. For figures that report the dominating set size, the y axis shows the number of nodes from the graph in the dominating set. For figures that report the running time, the y axis shows the number of seconds needed by our algorithms to compute the dominating sets.
Figures 1 – 6 show the results for ERNetworks. These networks gave predictable results in terms of both minimum dominating set size and running time. For dominating set sizes, we notice that the size of the network does not influence which algorithm performs best. However, the average degree is very important. When the average degree is below 25, the best algorithm is Alg. 4, followed in order by Alg. 3, Alg. 5, Alg. 2, and Alg. 1. When the average degree is over 25, Alg. 1 and Alg. 2 outperform the other 3 algorithms. Also it is worth noting that even in this case, Alg. 3 and, in particular, Alg. 4 find dominating sets of very close size with Alg. 1 and Alg. 2 (~15% more nodes in their dominating sets). For running time, Alg. 1 and Alg. 2 perform very poorly, and they are not suitable for very large networks. By comparing the other three algorithms (Figures 3 and 6), we draw the following two conclusions: First, Alg. 5 is always the fastest algorithm. Second, Alg. 4 is faster than Alg. 5 when the average degree is lower than 20, and the order changes for higher average degrees. It is worth noting that these three algorithms are suitable for very large networks. Based on these experiments, we conclude that for Erdos-Renyi random graphs the best algorithm to use in most cases is Alg. 4.
Figures 7 – 10 illustrate the results for ConfNetworks. The results are quite different compared to the ERNetworks. In terms of finding small dominating sets (Figures 7 and 9), Alg. 4 and 5 perform the best, with very similar results. Alg. 2 was close behind. Alg. 1 and 3 perform the worst. The reason for those results is that there are many vertices with degree = 1 that are identified early by Alg. 2 and 4, and their only neighbors are added to the dominating set in the beginning of these algorithm, thus reducing the size of the graph. When power exponent values are increased (Figure 9), the dominating set sizes are more similar than for low values of γ. This is expected since there are fewer nodes with low degree and the degree distribution became more equal. In terms of running time (Figures 8 and 10), Alg. 1 performs the worst by far, and all the other algorithms run in a relatively small amount of time. Looking more carefully at the data, Alg. 2, 3 and 4 perform very similarly. Alg. 3 is slightly better; Alg. 2 and 4 are very close, while Alg. 5 outperforms them significantly. Alg. 5 is between 20 times and 80 times faster than Alg. 3 in all our experiments.
To summarize, for power-law networks, the best algorithm is Alg. 5. While this algorithm is sometime worse than Alg. 4 in terms of finding the minimum dominating set size, it still performs best on average in this category. It is by far the fastest algorithm to execute, thus being very suitable for very large networks.
Figures 11 – 14 illustrate the results for RealNetworks. The smallest 7 datasets (shown in Figure 12) do not have any nodes of degree 1, and the results for Alg. 1 and Alg. 2 are identical. This is also true of Alg. 3 and Alg. 4 results. For those sets, Alg. 1 (and Alg. 2) outperform the other algorithms and Alg. 5 is close behind. For the larger sets, Alg. 4 and 5 perform the best, while Alg. 1 performs the worst. The reason for this sudden change is the distribution of nodes’ degree; the large datasets have more of a powerlaw distribution, and the results are more similar to the results obtained for ConfNetworks. In terms of running time, Alg. 1 and 2 (and Alg. 3 and 4) are very similar for the smallest 7 datasets for the same reason as above. For the larger datasets, Alg. 1 performs the worst. As expected, Alg. 5 is by far the fastest.
To summarize, for real networks, determining the best algorithm to use is not as straight-forward. If the running time is an important factor in this decision, then Alg. 5 is again the winner. If the time is not a factor, then Alg. 1 (or Alg. 2) is the choice for datasets without high variance in the average degree, and with no nodes of degree 1 (such as the 7 smallest datasets); while Alg 4 or 5 is the choice for the datasets that follow a power-law distribution (comamazon, com-dblp, com-youtube).
The experiments performed in this paper show that Alg. 4 is a viable algorithm to find a dominating set of a small size in large networks of various types. Also, the experiments show that Alg. 5 is surprisingly accurate, and it can be used successfully, in particular when the running time is a very important factor. To our surprise, Alg. 1 and Alg. 2 (which are frequently used in the literature) do not rise to the expected level, being outperformed in terms of dominating set size in most of the experiments by the other algorithms.
0 |N |= 350 300 250 200 150 100 50
0 |N |= 7 6 5 4 3 2 1 0 |N |= 5 10 15 20 25 30 35 40 45 50
0 |AVG |= 5 10 15 20 25 30 35 40 45 50 90 80 70 60 50 40 30 20 10
0 2.5 1.5
0 |N |= 450 400 350 300 250 200 150 100 50
0 |N |= 50000 40000 30000 20000 10000 2 2.1 2.2 2.3 2.4 2.5 2.6
Discussion and Future Extensions
The experiments performed in this work show that the two new algorithms (and in particular Alg. 4) are viable options to determine a small dominating set for large networks. In many experiments, Alg. 4 outperforms the existing algorithms, while being very efficient in terms of running time.
This work is a preliminary work in the dominating sets
for social network area. As part of our future work, we
intend to investigate how the two new algorithms can be
used for more specific dominating set problems, such as
partial dominating sets (Formin et al. 2005), total
dominating set