jagomart
digital resources
picture1_Algorithms For Optimization Pdf 86538 | 14cocoa2


 148x       Filetype PDF       File size 0.33 MB       Source: www.cise.ufl.edu


File: Algorithms For Optimization Pdf 86538 | 14cocoa2
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 ...

icon picture PDF Filetype PDF | Posted on 14 Sep 2022 | 3 years ago
Partial capture of text on file.
                  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.
The words contained in this file might help you see if this file matches what you are looking for:

...Approximation algorithms for optimization problems in random power law graphs yilin shen xiang li b and my t thai samsung research america san jose ca usa com cise department university of florida gainesville fl xixiang mythai ufl edu abstract manylarge scale real world networks are well known to have the distribution their degree sequences number ver some constant itisa tices with i is proportional commonbeliefthatsolvingoptimization easier unfortunately many been proven np hard along inapproximability factors therefore it great importance develop an algorithm framework such that these can be approximated provable theoretical ratios this paper we propose algorithmic called low percolation ldp solving minimum dominating set vertex cover maximum independent using further show a theoreti cal derive two our numerical analysis shows into near factor high probability proposed algo rithms exponential which belongs range most keywords probabilistic introduction large life discovered follow ra...

no reviews yet
Please Login to review.