148x 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.