=Paper= {{Paper |id=Vol-1353/paper_16 |storemode=property |title=Fast Dominating Set Algorithms for Social Networks |pdfUrl=https://ceur-ws.org/Vol-1353/paper_16.pdf |volume=Vol-1353 |dblpUrl=https://dblp.org/rec/conf/maics/CampanTB15 }} ==Fast Dominating Set Algorithms for Social Networks== https://ceur-ws.org/Vol-1353/paper_16.pdf

Fast Dominating Set Algorithms for Social Networks
Alina Campan, Traian Marius Truta, and Matthew Beckerich
Computer Science Department
Northern Kentucky University
Highland Heights, KY 41099, U.S.A.
campana1@nku.edu, trutat1@nku.edu, beckerichm1@mymail.nku.edu

Abstract ginning from the 1990s, other fields, in particular computer
In this paper we introduce two novel algorithms that are science and physics, brought a lot of new results to this
able to efficiently determine an approximation to the mini- field (Freeman 2011). With the advent of Myspace, Friend-
mum dominating set problem, and at the same time, they ster, and more recently, Facebook and LinkedIn, social
will preserve the quality of the solution to an acceptable
networks have grown to a new dimension -- the online so-
level. We compare these two algorithms with three existing
algorithms, for a large number of synthetic datasets, and for cial network -- which allows larger numbers of people to
several real world social networks. For experiments, we use participate. Many existing methods for social network
social network generators that create both power-law and analysis did not envision such a data explosion. Thus, de-
random networks, and a few real network datasets made veloping fast and accurate solutions for large social net-
available by the Stanford Network Analysis Project. Our
works is becoming more essential in present days.
experiments show that the proposed algorithms are viable,
and in many instances, preferable for determining the mini- An important feature in a social network is the ability to
mum dominating set of a social network. 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 indi-
Introduction viduals in the network can be contacted directly. However,
Today, online social networks are used by an ever increas- if all individuals from the network are connected to at least
ing number of people. For instance, Facebook has currently one such individual who can be contacted directly (or is
more than 1.35 billion users, LinkedIn has over 332 mil- one of those individuals) then the emergency message can
lion users, and 1 out of 4 people from the entire world is an be quickly sent to all network participants. This scenario
active user in at least one existing social network (Statista can be modeled by what is known as the dominating set
2014). It is not a surprise that researchers from various problem. This is formally described below.
domains such as sociology, economics, physics, mathemat- A set DS  N of nodes in a network G = (N, E) is a dom-
ics, and computer science are analyzing different problems inating set if every node x  N is either in DS or adjacent to
and proposing various solutions related to social networks. DS (Berge 1962). The dominating set with the smallest
While a lot of research has been performed in the past on numbers of elements is known as the minimum dominating
networks/graphs, nowadays the main focus is moving to- set (MDS). To find such a minimum dominating set is a
ward social issues (as the name implies, social networks well-known NP-complete problem, thus an exact efficient
usually represent relationships between people) and toward solution is unlikely to be found (Garey and Johnson 1979).
big social networks (as previously noted, these networks Approximation algorithms for determining the minimum
tend to be very large). dominating set exist in the literature, with the most com-
Social networks existed long before the Internet. As ear- mon one being an adaptation of the greedy algorithm for
ly as around 1200-1450 such social networks existed in determining a set cover (Lovasz 1975). However, as we
pre-Hispanic Southwest in the current United States. The will show in the following sections, this greedy algorithm
growth, collapse, and change of such social networks are is slow for large networks, and therefore more efficient so-
reflected in thousands of ceramic and obsidian artifacts lutions are needed. A very efficient algorithm has also been
(Mills et al. 2013). More recently, in the first half of the proposed (Eubank et al. 2004), but this algorithm has a low
20th century, the social network analysis discipline was result quality as we will show in the future sections.
started by the sociology community (Freeman 2011). Be- Extensive experimental results have been performed for
scale-free networks (that model social networks well) us- are white. W (v) denotes the set of white nodes among the
ing either the basic greedy algorithms for approximating direct neighbors of v, including v itself. w (v) = | W (v) | is
the minimum dominating set size (Molnar et al. 2013) or a called the span of v. Note that in the Alg. 1, we delete the
different algorithm based on a binary integer program- black nodes, and the next selected node is either gray or
ming-based method (Nacher et al. 2012). These works do white. This algorithm is named RegularGreedy in (Eubank
not compare the results of these algorithms with any other et al. 2004). Its pseudocode is presented next:
algorithms, and, in addition, they target social networks Algorithm 1 (G, DS) is
with low cardinality (up to 10,000 nodes), and therefore Input: G = (N, E) – a social network;
Output : DS – a dominating set for G;
they do not discuss how the used algorithms will scale to
large social networks. DS = ;
while ∃ white nodes do
In this paper we introduce two novel algorithms that are choose v ∈ {x ∈ N | w(x) = max u ∈ N |W(u)|};
able to determine efficiently an approximation to the min- DS := DS ∪ { v };
imum dominating set problem and, simultaneously, they // Delete the vertex v and
will preserve the quality of the solution to an acceptable // its adjacent edges from G.
G = (N \{v}, E \{(x, y) ∈ E| x = v or y = v)});
level. Those two algorithms: one extends the greedy algo- end while;
rithm mentioned earlier, and the other is an improvement end Algorithm 1.
of an algorithm that is also introduced in (Eubank et al. The second algorithm (Algorithm 2 or Alg. 2) starts by
2004). We compare those two algorithms with three exist- finding the set of all nodes of degree exactly one (D1).
ing algorithms for a large number of synthetic datasets, Then finds the set of nodes adjacent to D1 (Neighbors(D1)).
and for several real world social networks. For the exper- Obviously, any dominating set must contain Neigh-
imental part, we use social network generators that create bors(D1). Next, we run the Alg. 1 on the subgraph induced
both power-law and random networks, as well as real net- by N \ Neighbors(D1). This second algorithm is referred in
work datasets made available by the Stanford Network previous work as VRegularGreedy (Eubank et al. 2004).
Analysis Project (Leskovec and Krevl 2014). Its pseudocode is presented next:
The remaining of this paper is structured as follows.
Algorithm 2 (G, DS) is
Section “Dominating Set Algorithms” introduces the two Input: G = (N, E) – a social network;
new algorithms that we use in this paper. In addition, in Output : DS – a dominating set for G;
this section we also present three existing algorithms that D1 = { x ∈ N | degree(x) = 1};
we use for experimental evaluation. Section “Datasets” de- Neighbors(D1) = { x ∈ N |  y ∈ D1 and (x, y) ∈ E }
scribes how we generate the synthetic social networks, and DS = Neighbors(D1);
// E’ – contains all edges from E that have
provides a description of the used real datasets. In section // both ends in N \ {Neighbors(D1)  D1}.
“Experiments and Results” we perform a detailed experi- G’ = (N \ {Neighbors(D1)  D1}, E’);
mental evaluation of our algorithms using the datasets pre- Algorithm 1 (G’, DS’);
sented in the previous section. Section “Discussion and Fu- DS = Neighbors(D1)  DS’;
end Algorithm 2.
ture Extension” presents conclusions and a summary of fu-
ture extension for our work. 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 re-
Dominating Sets Algorithms ducing significantly at each step the size of the network.
In this section we describe the greedy algorithms we use to Since all the time the remaining nodes are white, the use of
approximate the minimum dominating set. Algorithms 3 node coloring is no longer useful. This algorithm is de-
and 4 are new, while the rest are existing algorithms scribed next:
against which we compare ours. Algorithm 3 (G, DS) is
The first algorithm (Algorithm 1 or Alg. 1) is the stand- Input: G = (N, E) – a social network;
Output : DS – a dominating set for G;
ard greedy algorithm that choses at each step, one node
DS = ;
that covers the maximum number of currently uncovered
while N   do
nodes (Eubank et al. 2004, Molnar et al. 2013). In this al- choose v ∈ {x ∈ N |
gorithm we start with an empty set, DS, which will at the degree(x) = max u ∈ N (degree(u))};
end store the nodes in the dominating set. Nodes from the DS := DS ∪ { v };
// Delete the vertex v, Neighbors({v}), and
network are colored according to their state during the exe-
// their corresponding edges.
cution of the algorithm. Nodes in DS are called black, // The remaining edges are labeled E’
nodes which are covered (because they neighbor one or G = (N \{v}\ Neighbors({v},E’ );
more nodes in DS) are called gray, and all uncovered nodes end while;
end Algorithm 3.
The fourth algorithm (Algorithm 4 or Alg. 4) combines configuration model (Molloy and Reed 1995, Britton et al.
the Algorithms 2 and 3, by including in the dominating set 2005) that generates a scale free network (Catanzaro et al.
all neighbors of nodes of degree 1, and then by applying 2005). Details about the generation algorithms as well as
Algorithm 3 to the remaining graph. This algorithm is de- the properties of the generated networks can be found in
scribed as: (Leskovec and Sosic 2014). We refer to those networks as
Algorithm 4 (G, DS) is ERNetworks and ConfNetworks respectively.
Input: G = (N, E) – a social network; To generate ERNetworks we chose the following param-
Output : DS – a dominating set for G;
eters. First we fix the size of the network, |N |, to 50,000,
while N   do and we generate ERNetworks for 10 different average de-
D1 = { x ∈ N | degree(x) = 1};
gree values (AVG = 5, 10, 15, 20, .., 50). Second we chose
Neighbors(D1) = { x ∈ N |  y ∈ D1 and (x, y) ∈ E }
DS = Neighbors(D1); a fixed AVG value (AVG = 10) and we use 10 distinct val-
// E’ – contains all edges in E with both ends ues for the size of N (|N | = 10K, 20K, …, 100K). For each
// in N \ {Neighbors(D1)  Neighbors (Neighbors(D1) )}. combination of |N | and AVG values we generate 5 distinct
G’ = (N \ {Neighbors(D1)  Neighbors (Neighbors(D1) ), E’); networks. The total number of ERNetworks generated is 95
Main step in Algorithm 3 (G’, v);
(19 combinations x 5 samples). Note that the size 50K and
DS = Neighbors(D1) { v };
end while; AVG = 10 is common between the two generation ap-
end Algorithm 4. proaches, and therefore it is considered only once.
Note that in the Alg. 4, we also delete all nodes domi- We generate the same number of ConfNetworks but we
nated by Neighbors(D1) prior to using Algorithm 3. This is change the parameters as follows. For the size of the net-
equivalent with deleting the gray nodes along with the works we use exactly the same values, but as a second pa-
black node which is executed in Alg. 3 and it is not per- rameter we use the power-law exponent γ from the power-
formed in Alg. 1. law distribution (P(k)  k-γ). For the fixed |N | value (50K)
The last algorithm known as FastGreedy in (Eubank et we use the values for γ = 1.7, 1.8, …, 2.6. When we vary
al. 2004) is a very simple and efficient algorithm for com- the size of networks, we use γ = 2.0. As before, for each
puting a dominating set. Consider the nodes in N in non- combination of |N | and γ we generate 5 district networks
increasing order of the degree v1, v 2, …, v |N |, with de- and the total number of generated ConfNetworks is 95.
gree(v 1) ≥ degree(v 2) ≥ … ≥ degree(v | N |), where degree() We also use 10 real networks in this work. These net-
is the given degree-sequence. Pick the smallest i such that works are from the SNAP datasets website (Leskovec and
|ji Neighbors (vj)| = |N | and take the subset {v1, v 2, …, Krevl 2014). The number of nodes and edges of these net-
vi } to be the dominating set of the graph. In this algorithm, works, as well as a short description, are shown in Table 1.
we do not take those vi nodes for which Neighbors (vi)  j For a full description of the networks and additional prop-
erties please consult (Leskovec and Krevl 2014).
< i Neighbors (vj). We refer to this algorithm as Algorithm
5 or Alg. 5. The pseudocode algorithm is presented next:
Table 1. Real Networks’ Characteristics.
Algorithm 5 (G, DS) is
Input: G = (N, E) – a social network;
Output : DS – a dominating set for G; Name |N | |E | Description

DS = ; ego-
4,039 88,234 Social circles from Facebook
Order vertices in N = {v 1, v 2, … v|N|)} Facebook
such that degree(v 1) ≥ degree(v 2) ≥ … ≥ degree(v | N |). Email communication net-
email-Enron 36,692 183,831
i = 1; work from Enron
while (|ji Neighbors (vj)| < |N |) do Collaboration network of
ca-AstroPh 18,772 198,110
if (not(Neighbors (vi)  j < i Neighbors (vj))) Arxiv Astro Physics
DS = DS  { v i}; Collaboration network of
ca-CondMat 23,133 93,497
i++; Arxiv Condensed Matter
end Algorithm 5. Collab.network of Arxiv
ca-GrQc 5,242 14,496
General Relativity
Collab. network of Arxiv High
ca-HepPh 12,008 118,521
Datasets Energy Physics
Collab. network of Arxiv High
In order to compare the size of dominating sets and execu- ca-HepTh 9,877 25,998
Energy Physics Theory
tion times for the above 5 algorithms, we use both synthet- com-
334,863 925,872 Amazon product network
ic and real network datasets. All synthetic graphs were Amazon

generated using the SNAP library (Leskovec and Sosic com-DBLP 317,080 1,049,866 DBLP collaboration network
2014). com-
1,134,890 2,987,624
Youtube online social net-
Youtube work
We generate synthetic datasets using the well-known
Erdos-Renyi random graph model (Bollobás 2001) and the
Experiments and Results lar than for low values of γ. This is expected since there are
fewer nodes with low degree and the degree distribution
To execute our experiments, we implemented the Algo- became more equal. In terms of running time (Figures 8
rithms 1 – 5 described in Section “Dominating Set Algo- and 10), Alg. 1 performs the worst by far, and all the other
rithms” and the graph random generators described Section algorithms run in a relatively small amount of time. Look-
“Datasets” in C++ using the SNAP framework (Leskovec ing more carefully at the data, Alg. 2, 3 and 4 perform very
and Sosic 2014). To allow a meaningful comparison be- similarly. Alg. 3 is slightly better; Alg. 2 and 4 are very
tween running times, all the experiments were performed close, while Alg. 5 outperforms them significantly. Alg. 5
on an Intel® Xeon® E5430@2.66 GHz dual CPU machine is between 20 times and 80 times faster than Alg. 3 in all
with 4 GB memory running on 32 bit Windows Server our experiments.
2007 operating system. In the experiments executed on the To summarize, for power-law networks, the best algo-
synthetic networks (ERNetworks and ConfNetworks), the rithm is Alg. 5. While this algorithm is sometime worse
reported results are the average between the 5 sample da- than Alg. 4 in terms of finding the minimum dominating
tasets. set size, it still performs best on average in this category. It
Figures 1 – 14 show the results of all our experiments. is by far the fastest algorithm to execute, thus being very
For figures that report the dominating set size, the y axis suitable for very large networks.
shows the number of nodes from the graph in the dominat- Figures 11 – 14 illustrate the results for RealNetworks.
ing set. For figures that report the running time, the y axis The smallest 7 datasets (shown in Figure 12) do not have
shows the number of seconds needed by our algorithms to any nodes of degree 1, and the results for Alg. 1 and Alg. 2
compute the dominating sets. are identical. This is also true of Alg. 3 and Alg. 4 results.
Figures 1 – 6 show the results for ERNetworks. These For those sets, Alg. 1 (and Alg. 2) outperform the other al-
networks gave predictable results in terms of both mini- gorithms and Alg. 5 is close behind. For the larger sets,
mum dominating set size and running time. For dominating Alg. 4 and 5 perform the best, while Alg. 1 performs the
set sizes, we notice that the size of the network does not in- worst. The reason for this sudden change is the distribution
fluence which algorithm performs best. However, the aver- of nodes’ degree; the large datasets have more of a power-
age degree is very important. When the average degree is law distribution, and the results are more similar to the re-
below 25, the best algorithm is Alg. 4, followed in order by sults obtained for ConfNetworks. In terms of running time,
Alg. 3, Alg. 5, Alg. 2, and Alg. 1. When the average degree Alg. 1 and 2 (and Alg. 3 and 4) are very similar for the
is over 25, Alg. 1 and Alg. 2 outperform the other 3 algo- smallest 7 datasets for the same reason as above. For the
rithms. Also it is worth noting that even in this case, Alg. 3 larger datasets, Alg. 1 performs the worst. As expected,
and, in particular, Alg. 4 find dominating sets of very close Alg. 5 is by far the fastest.
size with Alg. 1 and Alg. 2 (~15% more nodes in their To summarize, for real networks, determining the best
dominating sets). For running time, Alg. 1 and Alg. 2 per- algorithm to use is not as straight-forward. If the running
form very poorly, and they are not suitable for very large time is an important factor in this decision, then Alg. 5 is
networks. By comparing the other three algorithms (Fig- again the winner. If the time is not a factor, then Alg. 1 (or
ures 3 and 6), we draw the following two conclusions: Alg. 2) is the choice for datasets without high variance in
First, Alg. 5 is always the fastest algorithm. Second, Alg. the average degree, and with no nodes of degree 1 (such as
4 is faster than Alg. 5 when the average degree is lower the 7 smallest datasets); while Alg 4 or 5 is the choice for
than 20, and the order changes for higher average degrees. the datasets that follow a power-law distribution (com-
It is worth noting that these three algorithms are suitable amazon, com-dblp, com-youtube).
for very large networks. Based on these experiments, we The experiments performed in this paper show that Alg.
conclude that for Erdos-Renyi random graphs the best al- 4 is a viable algorithm to find a dominating set of a small
gorithm to use in most cases is Alg. 4. size in large networks of various types. Also, the experi-
Figures 7 – 10 illustrate the results for ConfNetworks. ments show that Alg. 5 is surprisingly accurate, and it can
The results are quite different compared to the ERNet- be used successfully, in particular when the running time is
works. In terms of finding small dominating sets (Figures 7 a very important factor. To our surprise, Alg. 1 and Alg. 2
and 9), Alg. 4 and 5 perform the best, with very similar re- (which are frequently used in the literature) do not rise to
sults. Alg. 2 was close behind. Alg. 1 and 3 perform the the expected level, being outperformed in terms of domi-
worst. The reason for those results is that there are many nating set size in most of the experiments by the other al-
vertices with degree = 1 that are identified early by Alg. 2 gorithms.
and 4, and their only neighbors are added to the dominat-
ing set in the beginning of these algorithm, thus reducing
the size of the graph. When power exponent values are in-
creased (Figure 9), the dominating set sizes are more simi-
50000 25000

40000 20000

30000 15000

20000 10000

10000 5000

0 0
|N |= |AVG |= 5 10 15 20 25 30 35 40 45 50

Alg. 1 Alg. 2 Alg. 3 Alg. 4 Alg. 5 Alg. 1 Alg. 2 Alg. 3 Alg. 4 Alg. 5

Figure 1. Dominating Set Size for ERNetworks when AVG = 10. Figure 4. Dominating Set Size for ERNetworks when |N | = 50K.

350 90
80
300
70
250
60
200 50
150 40
30
100
20
50 10
0 0
|N |= 5 10 15 20 25 30 35 40 45 50

Alg. 1 Alg. 2 Alg. 3 Alg. 4 Alg. 5 Alg. 1 Alg. 2 Alg. 3 Alg. 4 Alg. 5

Figure 2. Running Time for ERNetworks when AVG = 10. Figure 5. Running Time for ERNetworks when |N | = 50K.

7 2.5

6
2
5
1.5
4
3 1
2
0.5
1
0 0
|N |= 5 10 15 20 25 30 35 40 45 50

Alg. 3 Alg. 4 Alg. 5 Alg. 3 Alg. 4 Alg. 5

Figure 3. Running Time for ERNetworks when AVG = 10 (fastest Figure 6. Running Time for ERNetworks when |N | = 50K (fastest
algorithms only). algorithms only).
140
100000
120
80000
100

60000 80
60
40000
40
20000 20

0 0
|N |= |N |= 1.7 1.8 1.9 2 2.1 2.2 2.3 2.4 2.5 2.6

Alg. 1 Alg. 2 Alg. 3 Alg. 4 Alg. 5 Alg. 1 Alg. 2 Alg. 3 Alg. 4 Alg. 5

Figure 7. Dominating Set Size for ConfNetworks when γ = 2.0. Figure 10. Running Time for ConfNetworks when |N | = 50K.

450 1200000
400 1000000
350 800000
300 600000
250 400000
200 200000
150
0
100
50
0
|N |=

Alg. 1 Alg. 2 Alg.3 Alg. 4 Alg. 5 Alg. 1 Alg. 2 Alg. 3 Alg. 4 Alg. 5

Figure 8. Running Time for ConfNetworks when γ = 2.0. Figure 11. Dominating Set Size for RealData

50000
15000

40000 12000
9000
30000
6000
20000 3000
0
10000

0
|PE |= 1.7 1.8 1.9 2 2.1 2.2 2.3 2.4 2.5 2.6
Alg. 1 Alg. 2 Alg. 3 Alg. 4 Alg. 5
Alg. 1 Alg. 2 Alg. 3 Alg. 4 Alg. 5
Figure 9. Dominating Set Size for ConfNetworks when |N | =
50K. Figure 12. Dominating Set Size for RealData (smaller sets)
2009), and k-tuple dominating set (Klasing and Laforest
80000 2004).

60000
References
40000
Berge C. 1962, Theory of Graphs and its Applications. Methuen,
20000 London.
Bollobás B., 2001, Random Graphs (2nd ed.). Cambridge Univer-
0 sity Press. ISBN 0-521-79722-5.
Britton T,; Deijfen M; and Martin-Lof A. 2006. Generating Sim-
ple Random Graphs with Prescribed Degree Distribution. Journal
of Statistical Physics, Vol. 124, Issue 6, 1377-1397.
Catanzaro M.; Boguna M.; and Pastor-Satorras R., 2005, Genera-
Alg. 1 Alg. 2 Alg. 3 Alg. 4 Alg. 5 tion of Uncorrelated Random Scale-Free Networks. Physical Re-
Figure 13. Running Time for RealData view, E 71, 027103.
Cockayne E. J.; Dawes R. M.; and Hedetniemi S. T. (1980). Total
10 Domination in Graphs. Networks, Vol. 10, No 3, pp. 211-219.
8 Eubank S.; Anil Kumar V. S.; Marathe M.; Srinivasan A.; and
6 Wang N. 2004. Structural and Algorithmic Aspects of Massive
Social Networks. In Proceedings of the ACM-SIAM Symposium
4
on Discrete Algorithms, 718–727.
2
Fomin F. V.; Kratsch D.; and Woeginger G. J. (2005). Exact (Ex-
0 ponential) Algorithms for the Dominating Set Problem. In Graph-
Theoretic Concepts in Computer Science, pp. 245-256 Springer
Berlin Heidelberg.
Freeman L. C. 2011. The Development of Social Network Analy-
sis — with an Emphasis on Recent Events. In Sage Handbook of
Social Network Analysis edited by J. Scott and P. Carrington, 26–
Alg. 1 Alg. 2 Alg. 3 Alg. 4 Alg. 5 39.
Figure 14. Running Time for RealData (smaller sets) Garey, M. R. and Johnson, D. S. 1979. Computers and Intracta-
bility: A Guide to the Theory of NP-Completeness. W.H. Free-
man, ISBN 0-7167-1045-5, page 190.
Discussion and Future Extensions
Klasing R. and Laforest C. (2004). Hardness Results and Approx-
The experiments performed in this work show that the
imation Algorithms of k-Tuple Domination in
two new algorithms (and in particular Alg. 4) are viable
Graphs. Information Processing Letters, Vol. 89, No. 2, pp. 75-
options to determine a small dominating set for large net-
83.
works. In many experiments, Alg. 4 outperforms the exist-
ing algorithms, while being very efficient in terms of run- Leskovec J. and Krevl A. 2014a. SNAP Datasets: Stanford Large
ning time. Network Dataset Collection, Available at: http://snap.stanford.
This work is a preliminary work in the dominating sets edu/data.
for social network area. As part of our future work, we in-
Leskovec J. and Sosic R. 2014b. SNAP: A general purpose net-
tend to investigate how the two new algorithms can be
work analysis and graph mining library in C++, Available at:
used for more specific dominating set problems, such as
http://snap.stanford.edu/snap.
partial dominating sets (Formin et al. 2005), total dominat-
ing set (Cockayne at al. 1980), independent dominating Lovasz L. 1975. On the Ratio of Optimal Integral and Fractional
sets (Cockayne at al. 1980), connected dominating sets Covers. Discrete Mathematics, Vol. 13, 383–390.
(Wu and Li 1999), d-hop dominating set (Rieck et al.
Mills B.; Clark J.; Peeples M.; Haas W. R.; Roberts J.; Hill J. B.;
2002), positive influence dominating set (Wang et al.
Huntley D.; Borok L.; Breiger R.; Clauset A.; and Shackley M. S.
2013. Transformation of Social Networks in the Late Pre-
Hispanic US Southwest. In Proceedings of the National Academy
of Sciences of the United States of America, Vol. 110, No. 15,
April 9, 2013, 5785–5790.
Molloy M. and Reed B. 1995. A Critical Point for Random
Graphs with a Given Degree Sequence. Random Structures and
Algorithms, Vol. 6, 161-180.
Molnar F,; Sreenivasan S.; Szymanski K.; and Korniss G. 2013.
Minimum Dominating Sets in Scale-Free Network Ensembles,
Scientific Reports, No. 3, Nature Publishing Group.
Nacher J. C. and Akutsu T. 2012. Dominating Scale-free Net-
works with Variable Scaling Exponent: Heterogeneous Networks
are not Difficult to Control. New Journal of Physics, Vol. 14.
Rieck M. Q.; Pai S.; and Dhar S. (2002). Distributed Routing Al-
gorithms for Wireless Ad Hoc Networks using d-Hop Connected
d-Hop Dominating Sets. In Proc. 6th Int. Conf. High Perfor-
mance Computing Asia Pacific, Vol. 2, pp. 443-450.
Statista 2014. Available online at http://www.statista.com/topics/
1164/social-networks/.
Wang F.; Camacho E.; and Xu K. (2009). Positive Influence
Dominating Set in Online Social Networks. In Combinatorial Op-
timization and Applications, pp. 313-321, Springer Berlin Heidel-
berg.
Wu J. and Li H. (1999). On Calculating Connected Dominating
Set for Efficient Routing in Ad Hoc Wireless Networks.
In Proceedings of the ACM 3rd International Workshop on Dis-
crete Algorithms and Methods for Mobile Computing and Com-
munications, pp. 7-14.