Filetype PDF | Posted on 14 Sep 2022 | 3 years ago
Authentication
digital resources
149x Filetype PDF File size 0.33 MB Source: www.cise.ufl.edu
Approximation Algorithms for Optimization
Problems in Random Power-Law Graphs
1 2( ) 2( )
Yilin Shen , Xiang Li B , and My T. Thai B
1 Samsung Research America, San Jose, CA 95134, USA
yilin.shen@samsung.com
2 CISE Department, University of Florida, Gainesville, FL 32611, USA
{xixiang,mythai}@cise.ufl.edu
Abstract. Manylarge-scale real-world networks are well-known to have
the power law distribution in their degree sequences: the number of ver-
−β for some constant β.Itisa
tices with degree i is proportional to i
commonbeliefthatsolvingoptimization problems in power-law graphs is
easier. Unfortunately, many problems have been proven NP-hard, along
with their inapproximability factors in power-law graphs. Therefore, it is
of great importance to develop an algorithm framework such that these
optimization problems can be approximated in power-law graphs, with
provable theoretical approximation ratios.
In this paper, we propose an algorithmic framework, called Low-Degree
Percolation (LDP) Framework, for solving Minimum Dominating Set,
Minimum Vertex Cover and Maximum Independent Set problems in
power-law graphs. Using this framework, we further show a theoreti-
cal framework to derive the approximation ratios for these optimization
problems in two well-known random power-law graphs. Our numerical
analysis shows that, these optimization problems can be approximated
into near 1 factor with high probability, using our proposed LDP algo-
rithms, in power-law graphs with exponential factor β ≥ 1.5, which
belongs to the range of most real-world networks.
Keywords: Power-law graphs · Random graphs · Approximation algo-
rithms · Probabilistic analysis
1 Introduction
A great number of large-scale networks in real life are discovered to follow a
power-law distribution in their degree sequences, ranging from the Internet [8],
the World-Wide Web (WWW)[3]tosocial networks [15]. That is, the number of
−β
vertices with degree i is proportional to i for some constant β in these graphs,
which is called power-law graphs. The observations show that the exponential
factor β ranges between 1.5 and 3 for most real-world networks [4].
This work was finished when Yilin Shen was with CISE Department, University of
Florida.
c
Springer International Publishing Switzerland 2014
Z. Zhang et al. (Eds.): COCOA 2014, LNCS 8881, pp. 343–355, 2014.
DOI: 10.1007/978-3-319-12691-3 26
344 Y. Shen et al.
There are many papers studying the computational complexity of optimiza-
tion problems in power-law networks. Ferrante et al. [9] had an initial attempt
on power-law graphs to show the NP-hardness of Maximum Clique and Min-
imum Graph Coloring by constructing a bipartite graph to embed a general
graph into a power-law graph and NP-hardness of Minimum Dominating Set
(MDS), Minimum Vertex Cover (MVC) and Maximum Independent Set (MIS)
problems based on their optimal substructure properties. Recently, Shen et al.
[16] proposed two new techniques on optimal substructure problems to further
show the APX-hardness and the inapproximability result of MIS, MDS, and
MVCproblems on general power-law graphs and simple power-law graphs.
Fromalgorithmic perceptive, some experiments had been developed to evalu-
ate the simple algorithms for optimization algorithm in power-law graphs [7,14].
Later on, the upper bound of flow problem was provided in random power-law
graphs in [10] and an 1 − o(1) approximation algorithm for maximum clique
problem was proposed in [12]. However, these works did not provide a algo-
rithm framework for solving a set of problems in power-law graphs with degree
distribution property, let alone a theoretical analysis framework for analyzing
approximation ratios.
In this paper, we focus on addressing the following questions: Can the prop-
erty of power-law degree distribution help us to design an effective algorithm
framework for NP-hard optimization problems? How can we provide a theoret-
ical framework for analyzing approximation ratios of these problems using this
power-law degree property? Will these approximation ratios change dramati-
cally for different exponential factors β, i.e. in power-law graphs with different
densities?
Our Contributions: We propose an algorithm framework, called Low-Degree
Percolation (LDP), to approximate the optimization problems in power-law net-
works, including MIS, MDS, and MVC problems. The idea of LDP framework
is to percolate the graph starting from a large number of low-degree nodes in a
power-law graph, which allows us to develop a theoretical framework, which can
be used to analysis the approximation ratios via probabilistic analysis. In partic-
ular, we apply this theoretical framework to show the approximation ratios for
these problems on two well-known random power-law models in [2,5]. At last,
numerical analysis of our proposed approaches not only validates our theoretical
analysis but also illustrates the effectiveness of our approaches empirically.
Organization: In Sect.2, we present the two well-known random power-law
graph models, and the definitions of classic optimization problems. The Low-
Degree Percolation (LDP) algorithm framework is proposed in Sect.3, along
with two different versions for MDS/MVC and MIS problems respectively. In
Sect.4, using LDP framework, we provide a theoretical framework for analyzing
approximation ratios, and further extend to achieve the corresponding approxi-
mation factors for these two random models. Numerical analysis of our proposed
approaches are illustrated in Sect.5. Related work is presented in Sect.6 and
Sect.7 concludes the whole paper and provides further discussions.
Approximation Algorithms for Optimization Problems 345
2 Random Power-Law Models and Problem Definitions
In the section, we first present the two well-known random power-law models,
Expected Random Power-Law (ERPL) Graph and Structural Random Power-
Law(SRPL)Graph.Then,werecall the definitions of several classical optimiza-
tion problems.
2.1 Random Power-Law Graph Models
First, in order to represent the degree sequence property of power-law graphs,
we consider the following random graph, (α,β) graph G , with its power-law
(α,β)
degree distribution depending on two given values α and β.
Definition 2.1 ((α,β) Graph G ). Given an undirected graph G =(V,E)
(α,β)
having |V| = n nodes and |E| = m edges,itiscalleda(α,β) power-law graph if
α/β
its maximum degree is Δ = e and the number of nodes with degree i is
α α
⌊e ⌋,ifi>1or Δ ⌊e ⌋iseven
β i=1 β
yi = i i (2.1)
α
⌊e ⌋+1, otherwise
α α
Note that the number of nodes n = e ζ(β)+O(eβ −1) and the number of edges
α
α 2β ∞ 1
m = e ζ(β − 1) + O(e −1),whereζ(β)= i=1 β is the Riemann Zeta
i
function. For simplicity, since there is only a very small error o(1) w.r.t. n and
mwhen β>2 when counting the number of both nodes and edges, we denote
. α . α
them as n = e ζ(β) and edges m = e ζ(β −1).
The following two well-known models [2,5] were proposed in the literature to
construct the (α,β) graphs.
Expected Random Power-Law (ERPL) Graph. Given the parameters α
and β, the ERPL model is to construct an expected (α,β) power-law graph
according to its degree sequence d, which consists of a sequence of integers
(1,...,1,2,...,2,...,Δ) where the number of i is equal to yi defined in the
above Definition2.1.
Definition 2.2 (ERPL Graph). Given d =(d ,d ,...,d ) be a sequence of
1 2 n
integers (1,...,1,2,...,2,...,Δ) where the number of i is equal to yi, the ERPL
model generates a random graph in which edges are independently.assigned to
each pair of vertices (i,j) with probability d d ρ where ρ = 1 = 1 .
i j n d eαζ(β−1)
i=1 i
Structural Random Power-Law (SRPL) Graph. Given the parameters α
and β, the SRPL model is proposed as an structural approach to construct a
(α,β) power-law graph according to its degree sequence d, which consists of a
sequence of integers (1,...,1,2,...,2,...,Δ) where the number of i is equal to
yi defined in the above Definition2.1.
346 Y. Shen et al.
Definition 2.3 (SRPL Graph). Given d =(d ,d ,...,d ) be a sequence of
1 2 n
integers (1,...,1,2,...,2,...,Δ) where the number of i is equal to yi, the SRPL
model generates a random graph as follows. Consider D = n di mini-nodes
i=1
lying in n clusters of each size di where 1 ≤ i ≤ n, we construct a random
perfect matching among the mini-nodes and generate a graph on the n original
nodes as suggested by this perfect matching in the natural way: two original nodes
are connected by an edge if and only if at least one edge in the random perfect
matching connects the mini-nodes of their corresponding clusters.
2.2 Problem Definitions
Definition 2.4 (Minimum Dominating Set (MDS)). Given an undirected
graph G =(V,E), find a subset S ⊆ V with the minimum size such that for each
vertex vi ∈ V \ S, at least one neighbor of vi belongs to S.
Definition 2.5 (Minimum Vertex Cover (MVC)). Given an undirected
graph G =(V,E),findasubsetS ⊆ V with the minimum size such that for
each edge E at least one endpoint belongs to S.
Definition 2.6 (Maximum Independent Set (MIS)). Given an undirected
graph G =(V,E), find a subset S ⊆ V with the maximum size such that no two
vertices in S are adjacent.
3 Low-Degree Percolation (LDP) Algorithm Framework
In this section, we propose an algorithm framework to solve optimization prob-
lems based on the degree sequence property in power-law graphs. As one can see,
the most fundamental property of power-law graphs is that they contain a large
number of low-degree nodes, while only a small number of high-degree nodes.
Therefore, the idea of our proposed Low-Degree Percolation (LDP) algorithm
framework is to sort the nodes by their degrees and percolate the graph from
the nodes of lowest degree. The process continues in residual graph iteratively
until no more nodes, which are surely in optimal solution, can be detected. At
last, we apply existing approximation approaches in the remaining graph.
For MDS and MVC problems, as shown in Algorithm 1, since the node inci-
dent to a node of degree 1 certainly belongs to an optimal solution, we percolate
the graph by adding all the neighbors of nodes with degree 1 in each itera-
tion. Until no more nodes of degree 1 exists in residual graph, we apply existing
approximationalgorithmin[17]forMDS(or[13]forMVC)toobtainthesolution
in this residual graph.
Ontheotherhand,Algorithm2showsthealgorithmforMIS.Inthiscase,the
nodes of degree 1 will belong to the optimal solution, and in the meanwhile, it is
certain that their neighbors cannot be in optimal solution any more. Therefore,
in order to obtain MIS, we select all nodes of degree 1 into the solution in each
iteration. At last, we apply the approximation algorithm in [11] to obtain the
MIS in the remaining graph.
Here, we note that in a special case that two nodes of degree 1 are connected,
the optimal solution of MDS (or MVC, MIS) contains either one of them.
no reviews yet
Please Login to review.
