Drawing power law graph - University of South Carolina
Contents
1. gt D i D 0 Y a k 1 3 k 1 Consider 3 min D w a w where the minimum is taken over all possible weight functions where a w 0 Since we can scale any such weight function by a w to obtain an 4 short fractional cut 8 is the optimum value of an short fractional cut Now consider the weight function w wo where the initial weights are subtracted from each edge that has been used to route flow in f We have D w wo D i D 0 and a w wo gt a i l Thus D w S4 wo D wi oo wo alwi wo S ali l BS and so D i D 0 gt G a t l We substitute this in equation 3 to obtain ali lt 66 Y a k 1 k 1 and since a i is as large as possible when a i 1 is as large as possible ali lt a i 1 1 D lt ali 1 e Since a 0 lt 6 we obtain l a i lt dle Also a t gt 1 by the stopping condition so 1 lt a t lt dle By taking logs we obtain Ja a In z7 4 D Every edge e has w e lt 1 since the last time e was increased it was on a path of length strictly less than 1 and its weight was increased by a factor of 1 Since wo e 6 it follows that the weight of e can be increased at most log ite times and thus the total flow through e is at most log Lte Scaling the flow f by the maximum congestion yields a feasible flow f of value at least can e 1lte 5 Therefore the appro2. be a random graph from the specified expected degree model with average weight d second order average weight d and maximum weight m Let H be the hybrid graph H GUL and let Ly H be the unique largest f local subgraph of H If d satisfies PNET d lt n lt 5 n 3 F for some constant a gt 0 Then with probability 1 O n7t 1 L L contains O d edges 2 dy x y gt dz x y for every pair x y E L The proof of this theorem is contained in 3 3 Fast Algorithms for Short Flow Problems Garg and K nemann 17 gave simple combinatorial algorithms for maximum multicommodity flow maxi mum concurrent flow and general fractional packing problems We present a simple primal dual approxi mation algorithm for the maximum short flow problem based on their techniques The number of iterations required by our algorithm is smaller than the number required by the algorithms for maximum multicommod ity flow or general fractional packing problems This is because the number of iterations in our algorithm can be bounded in terms of fe u v whereas the stated bounds for the multicommodity flow algorithm depends on M Since we are computing short flows our algorithms only need to consider the edges involved in some short u v path which are all contained in the subgraph Ne 2 u U Nes2 v Thus our running times will be bounded in terms of m the number of edges in the small subgraph Ny 2 u U Ne 2 v and not o
3. If the algorithm Extract uses an approximate local connectivity testing algorithm then Extract returns a graph L such that Lye G CLC Lya_ee G 4 2 An Approximate Extract Algorithm The algorithm Extract performs O M7 local connectivity tests where M is the number of edges in G The number of local connectivity tests used can be reduced by using a standard random sampling approach if we are willing to accept local graphs which are approximations in an additional sense We say L is an a approximate local subgraph of G with respect to some deterministic connectivity test T if L contains every edge of G that passes the test T and at most an a fraction of the edges in L fail the test T The following algorithm returns an a approximate local graph for a given local connectivity test with probability 1 Approximate Extract We are given a graph G a local connectivity test T and parameters a and 6 Pick an edge e u v from G uniformly at random If u and v fail the test T remove u v from G Repeat until no edge is removed for 4 log 4 consecutive attempts Then output the current graph Since at most m edges are removed from G and there are at most log a attempted removals for every edge removed Approximate Extract performs at most u log uM local connectivity tests Theorem 6 With probability at least 1 the algorithm Approximate Extract returns an a approximate local subgraph of G with respect to the local connectivity
4. We will also state a theorem showing that local graphs are robust to the addition of random edges Throughout the paper the graphs we consider are undirected and unweighted 2 1 Short Flows and Local Connectivity There are a number of ways to define local connectivity between two given vertices u and v A natural approach is to consider the connectivity through paths whose length is at most some fixed constant which we will call short paths or simply short paths The path connectivity ag u v is the maximum size of an short collection of edge disjoint u v paths The cut connectivity celu v is the minimum size of an L short u v cut a set of edges whose removal leaves no short u v paths The analogous version of Menger s theorem does not hold when we restrict to short paths ag u v and ce u v are not necessarily equal However it is easy to see that the trivial relations ag lt ce lt a still hold Both ag u v and ce u v are difficult to compute In particular computing the maximum number of short disjoint paths is NP hard if gt 4 19 In light of this result we will define local connectivity based on maximum short flow which we will define shortly and which can be efficiently computed as we will show in Section 3 An short flow is a linear combination of short paths where each edge has congestion at most 1 If we let A be the incidence matrix where each column represents a short path from u t
5. and S Kawai An algorithm for drawing general undirected graphs Information Processing Letters 31 1 715 April 1989 J Kleinberg The small world phenomenon An algorithmic perspective Proc 32nd ACM Symposium on Theory of Computing 2000 J Kleinberg S R Kumar P Raghavan S Rajagopalan and A Tomkins The web as a graph Mea surements models and methods Proceedings of the International Conference on Combinatorics and Computing 1999 15 24 25 26 27 28 29 30 S R Kumar P Raghavan S Rajagopalan and A Tomkins Extracting large scale knowledge bases from the web Proceedings of the 25th VLDB Conference Edinburgh Scotland 1999 K J Lang Finding good nearly balanced cuts in power law graphs Preprint 2004 L Lovasz V Neumann Lara M Plummer Mengerian theorems for paths of bounded length Periodica Mathematica Hungaria 9 1978 M E J Newman The structure of scientific collaboration networks Proc Natl Acad Sci USA vol 98 no 2 2001 404 409 S C North Drawing graphs with NEATO NEATO User Manual April 26 2004 S Plotkin D B Shmoys and E Tardos Fast approximation algorithms for fractional packing and covering problems FOCS 1991 pp 495 504 D J Watts and S H Strogatz Collective dynamics of small world networks Nature 393 440 442 16
6. test T Proof We say the algorithm is in phase i if i 1 edges e e _ have been removed so far Say that the algorithm has reached phase 7 If the algorithm halts before phase i 1 and outputs a graph that is not a approximate for T then log 4 edges were tested and passed the local connectivity test in phase i but at least an a fraction of the edges remaining in phase 7 do not pass the local connectivity test The probability that this occurs is bounded by 1 a LEF lt e7 ls S Since there are at most M phases of the algorithm the probability that this occurs in any phase is at most Note that we never remove an edge which passes the local connectivity test The result follows Corollary 2 If we run the algorithm Approximate Extract with an e approximate connectivity test then with probability 1 6 we obtain a graph L which contains Ly and where at most an a fraction of edges are not f 1 connected in L In some applications it may also be sufficient to create a local global partition by simply letting L be the edges which are f connected in G In this case L will not be a local graph but the subgraph L still has the robustness properties described in Section 2 5 This approach eliminates the recursive part of Extract and requires only M local connectivity tests It should be considered for large graphs We remark that for a few limited choices of parameters testing local connectivity can be so
7. 7 After obtaining a local global partition we use it by modifying a standard force directed algorithm to emphasize local edges We demonstrate that this method produces improved drawings for graphs that contain underlying geometric graphs augmented with random edges This is theoretically supported since the robustness of the local graph implies that most of the edges in the underlying geometric graph will be classified as local while most of the edges from the random graph will be classified as global We also present a drawing method based on a more sophisticated partition that reflects other aspects f the structure of power law graphs For example it was shown in 11 that a random power law graph has roughly an octopus shape with a dense core and a myriad of tentacles attached While the core tself may be a dense graph that is not amenable to most drawing methods our algorithm takes advantage of the local subgraph and the sparse tree like structures in the tentacles yielding improved drawings This partition extends the class of graphs for which the local global partition is useful to many realistic networks where some notion of closeness between vertices is reflected in the edge set O m 2 Preliminaries In 3 the authors introduced local graphs which are graphs where the endpoints of each edge are highly locally connected by a large short flow In this section we introduce short flows and define local graphs
8. Drawing Power Law Graphs using a Local Global Decomposition Reid Andersen Fan Chung Linyuan Lu University of California San Diego University of California San Diego University of South Carolina Abstract It has been noted that many realistic graphs have a power law degree distribution and exhibit the small world phenomenon We present drawing methods influenced by recent developments in the modeling of such graphs Our main approach is to partition the edge set of a graph into local edges and global edges and to use a force directed method that emphasizes the local edges We show that our drawing method works well for graphs that contain underlying geometric graphs augmented with random edges and demonstrate the method on a few examples We define edges to be local or global depending on the size of the maximum short flow between the edge s endpoints Here a short flow or alternatively an short flow is one composed of paths whose length is at most some constant We present fast approximation algorithms for the maximum short flow problem and for testing whether a short flow of a certain size exists between given vertices Using these algorithms we give a fast approximation algorithm for determining local subgraphs of a given graph The drawing algorithm we present can be applied to general graphs but is particularly well suited for numerous small world networks with power law degree distribution 1 Introduction Although
9. Lu Average distances in random graphs with given expected degree sequences Pro ceedings of National Academy of Science 99 2002 Fan Chung and Linyuan Lu Connected components in a random graph with given degree sequences Annals of Combinatorics 6 2002 125 145 C Cooper and A Frieze On a general model of web graphs Random Structures and Algorithms Vol 22 2003 311 335 P Erd s and T Gallai Gr fok el rt fok pontokkal Graphs with points of prescribed degrees in Hungarian Mat Lapok 11 1961 264 274 M Faloutsos P Faloutsos and C Faloutsos On power law relationships of the Internet topology Proceedings of the ACM SIGCOM Conference Cambridge MA 1999 G W Flake R E Tarjan and K Tsioutsiouliklis Graph Clustering and Minimum Cut Trees N Garg J Konemann Faster and simpler algorithms for multicommodity flow and other fractional packing problems Technical Report Maz Planck Institut fur Informatik Saarbrucken Germany 1997 Jerry Grossman Patrick Ion and Rodrigo De Castro Facts about Erd s Numbers and the Collaboration Graph http www oakland edu grossman trivia html A Itai Y Perl and Y Shiloach The complexity of finding maximum disjoint paths with length constraints Networks 12 1982 S Jain and S Krishna A model for the emergence of cooperation interdependence and structure in evolving networks Proc Natl Acad Sci USA vol 98 no 2 2001 543 547 T Kamada
10. The graph in figures 12 and 13 is a random induced subgraph on the vertices in the collaboration graph with degree at least 18 The graph in figures 10 and 11 is a subgraph of a biological network which encodes protein DNA interactions In these figures the local edges are drawn in a darker color than the other edges 12 LA p N TN iD N ai KA Si N NEA i 1 Figure 6 The grid graph P29 xX P29 plus a random Figure 7 The same graph with target lengths set by graph with p 1 with all target lengths equal the Local Global partition using f 1 3 SEK TS STRAT IN Z RS RAM AUN qd N N SNA ae A AON LAURA ESAN NTD DOI TaN VY DL Figure 8 The hypercube Qs plus a random graph with Figure 9 The same graph with target lengths set by p l with all target lengths equal the Local Global partition using f 6 3 13 d Figure 10 Subgraph of a biological network with all Figure 11 Subgraph of a biological network using target lengths equal T L S C partition ration graph with Figure 13 A subgraph of the collaboration graph us all target lengths equal ing T L S C partition References 1 L A Adamic and B A Huberman Growth dynamics of the
11. World Wide Web Nature 401 September 9 1999 pp 131 i W Aiello F Chung and L Lu A random graph model for massive graphs Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing 2000 171 180 3 R Andersen F Chung and L Lu Analyzing the small world phenomenon using a hybrid model with local network flow Proceedings of the Third Workshop on Algorithms and Models for the Web Graph 2004 14 10 11 12 13 14 15 16 17 18 19 20 21 22 23 R B R Azevedo and A M Leroi A power law for cells Proc Natl Acad Sci USA vol 98 no 10 2001 5699 5704 Albert Laszl6 Barab si and R ka Albert Emergence of scaling in random networks Science 286 1999 509 512 A Barabasi R Albert and H Jeong Scale free characteristics of random networks the topology of the world wide web Physica A 272 1999 173 187 B Bollob s Random Graphs Academic New York 1985 S Boyles G Exoo On line disjoint paths of bounded length Discrete Math 44 1983 A Broder R Kumar F Maghoul P Raghavan S Rajagopalan R Stata A Tompkins and J Wiener Graph Structure in the Web proceedings of the WWW9 Conference May 2000 Amsterdam Paper version appeared in Computer Networks 33 1 6 2000 309 321 K Calvert M Doar and E Zegura Modeling Internet topology IEEE Communications Magazine 35 6 1997 160 163 F Chung and L
12. at distance logn from the core 11 This octopus structure is also found in real examples for example the Yahoo Instant Messenger Graph 25 In the simple Local Global partition the tentacle edges are likely to be classified as global edges We should treat the tentacles separately from global edges near the core since the tentacles contain sparse tree like structures which can be drawn well We separate the edges of G into tentacle edges T and core edges K Specifically we let K be the k core of G for some appropriate k the maximum induced subgraph with minimum degree k We let T G K A better way to identify tentacles is a direction for future work We then divide the core into local and global edges with the Extract algorithm to obtain the partition of K into L and G In real examples unlike in the examples from the hybrid model the local graph L is likely to be disconnected with a large number of connected components We further divide the global edges into two sets depending on whether the endpoints lie in a single local component or have endpoints in different local components Edges whose endpoints lie in the same local component of L are placed into the set S of Shortcut edges We will set the target lengths of shortcut edges very high since they are the analogues of the global edges in the examples from the hybrid model Those global edges whose endpoints lie in different connected components of the local graph L are placed int
13. fied expected degree sequence w w1 W2 Wn is formed by including each edge v v independently with probability p w w jp where p gt w It is easy to check that vertex v has expected degree w We assume that max w lt gt k Wr so that pij lt 1 for all and j This condition also implies that the sequence w is graphical 14 if the w are integers This model has a non zero probability of self loops but the expected number of loops is of lower order than the total number of edges The typical random graph G n p on n vertices with edge probability p is a random graph with expected degree sequence w pn pn pn For a subset S of vertices we define Vol S Sow and Vola S w nEs vies Let d denote the average degree Vol G n and let d denote the second order average degree Vol2 G Vol G We also let m denote the maximum weight among the w 2 5 Robustness of Local Graphs We consider how the local graph Ly G changes with the addition of random edges In particular we consider the addition of the edge set of a random graph G w with a specified expected degree sequence The following theorem states that local graphs are robust to the addition of these edge sets provided the random graph is not too dense Graphs formed by the union of a local graph L and a random graph G w were considered in 3 and were there called hybrid graphs Theorem 2 Let L be an f local graph with mazimum degree M Let G w
14. graph theory has a history of more than 250 years it was only recently observed that many realistic graphs from disparate areas satisfy the so called power law where the fraction of nodes with degree k is proportional to k for some positive exponent 3 Graphs with power law degree distribution are prevalent in the Internet in communication networks social networks and in biological networks 1 2 4 5 6 9 10 13 15 20 23 24 27 Many real examples of networks also exhibit a so called small world phenomenon consisting of two distinct properties small average distance between nodes and a clustering effect where two nodes sharing a common neighbor are more likely to be adjacent It was shown in 11 that a random power law graph has small average distance and small diameter However random power law graphs do not adequately capture the clustering effect In 3 the authors introduced a hybrid graph model where a random power law graph called the global graph is added to an underlying local graph A local graph is a graph where the endpoints of each edge are highly locally connected by large short flows In particular a graph is said to be f local if the endpoints of each edge are connected by an f short flow of size f Random geometric graphs and d dimensional grid graphs are good examples of local graphs for various parameters Given an arbitrary graph G we can choose parameters f and and define the local graph of G t
15. han or equal to k Let p x k be its predecessor on one path achieving this minimum Compute the values of w e amp 1 and p e k 1 from the values of w e k Once all the w x k and p x k are computed we can obtain the minimum weight path backward from v to u by letting xo p v 2 and x p zi 1 l i until we reach u Thus we obtain a minimum weight short path in time Tmwp O m Theorem 3 The algorithm Maximum Short Flow produces a feasible flow fe u v which is a 1 approximation to the maximum short flow fe u v The algorithm runs in time fe u v 5llog l Twp where Tmwp O m is the time required to find a minimum weight short path in a weighting of the subgraph Gyv 2 and m is the number of edges in Ne2 u U Neja v The analysis of the approximation guarantee for the maximum short flow algorithm is nearly identical to the analysis for the maximum multicommodity flow algorithm in Garg and K nemann 17 but the analysis of the number of iterations required contains a significant difference For completeness we include the full analysis here Proof of the approximation guarantee Let D w 97 w e be the total amount of weight in the weight function w and let a w miny gt 7 lt w e be the minimum weight of any short path with the weight function w Let D i D w and a t a w At each step i gt 1 Di wle So wii e 5 w e e p i Di 1 e a i 1 and thus
16. he Extract algorithm with appropriate parameters f and to an input graph H to obtain the local subgraph L and let G H L be the global subgraph We assign target length 1 to edges in L and target length 100 to edges in G In the figures the local edges are displayed in a darker color All the examples described in this section consist of an underlying local graph augmented with random edges as in the hybrid model In all the examples the underlying graph is highly locally connected and the Kamada Kawai algorithm on its own will produce good drawings of the local graph However the Kamada Kawai algorithm will not necessarily produce good drawings of the augmented graphs even though the local graph may still be easily recoverable from the augmented graph with the Extract algorithm Combined with our partitioning scheme the Kamada Kawai algorithm produces drawings of the augmented graph similar to those of the local graph This is arguably the best that can be hoped for with a graph from the hybrid model The first example is a modified random geometric graph G n d p A random geometric graph is created by choosing n points x 2 uniformly from the unit square and creating an edge between each pair xxj if and only if d x x lt d We then augment this graph with the edge set of a random graph G n p We also consider the hypercube Qn and the grid graph P x P augmented with a random graph G n p Note that Qn is an n 3 local gra
17. is dominated by the time to run Max Short Flow and the result follows 4 Separating Local and Global Edges In this section we present approximation algorithms for computing L G the largest f local subgraph in G These algorithms for computing Ly G will be used to create our graph decompositions in Section 5 4 1 The Extract Algorithm We first present a simple greedy algorithm Extract for computing Ls G This basic version of the Extract algorithm appeared previously in 3 Extract f We are given an input graph G and parameters f 8 Initially set H G For each edge e u v in H check if u and v are f connected in H If not remove edge e Repeat until no further edges can be removed then output H Theorem 5 For any graph G and any f the algorithm Extract f returns Ls e G Proof Given a graph G let L be the graph output by the Extract algorithm A simple induction argument shows that each edge removed by the algorithm is not part of any f local subgraph of G Since no further edges can be removed from L by the Extract algorithm L is f l local It follows that L Ly G The immediate corollary below describes what happens if we replace the exact local connectivity testing in Extract with an e approximate local connectivity testing algorithm which accepts all vertex pairs that are f connected and rejects all vertex pairs that are not 1 e f 2 connected Corollary 1
18. lved more easily With the parameters f 2 testing local connectivity can be accomplished by determining the distance between u and v in G uv For the parameters f 3 testing local connectivity can be accomplished by computing a maximum bipartite matching 5 Applying Local Global Partitions in Graph Drawing We combine a local global partition with a standard force directed layout method to produce improved drawings for a variety of graphs The force directed method we use is the neato software package from AT amp T 28 which implements a version of the Kamada Kawai algorithm 21 Our basic approach is to partition the edge set of the graph into local and global edges and assign shorter target lengths to local edges This partitioning method can conceivably be combined with any force directed layout method which allows the user to specify either the target lengths or spring constants of edges To provide motivation we first demonstrate this approach on a few examples from the hybrid model We will then present a more complicated partition and length assignment rule to be used on real world examples and show the results for certain biological networks and collaboration graphs 5 1 A Simple Partition and Motivating Examples from the Hybrid Model Here we demonstrate the application of a straightforward local global partition to a few idealized examples from the hybrid model To obtain the results depicted in the figures we apply t
19. n M the number of edges in the entire graph In our applications we will be repeatedly testing whether two given vertices are f connected for some constants f and which we call the local connectivity testing problem We combine our maximum short flow algorithm with a greedy path selection algorithm to obtain an algorithm for local connectivity testing where the number of iterations required depends on the constant f rather than felu v Thus in many cases we can test local connectivity much faster than we can compute the maximum short flow 3 1 Computing the Maximum Short Flow Maximum Short Flow The algorithm produces an short flow f by routing one unit of flow at each time step Initially Let wo be a weight function wo E gt Rt assigning weight to every edge in Ngy2 u U Ne o v Let fo be the empty flow At each time step i Let p z be an short path of minimum weight with respect to the current weight function wi Let a i be the weight of this path Modify f by routing 1 unit of flow on p i Modify the weight function by setting wj 1 e w e 1 for each edge e p t The procedure stops at the first time step t when a t gt 1 The flow f t is then scaled by the maximum edge congestion to obtain a feasible short flow f Finding a minimum weight short path can be done easily For each k 0 and each vertex zx Let w x k be the minimum weight of a path from u to x of length less t
20. nectivity Approximate Local Connectivity Test We wish to test whether u and v are f 2 connected First greedily choose a collection A of short disjoint paths until either A has size f or A is maximal If A reaches size f then we accept Otherwise we compute filu v using Maximum Short Flow We accept if and only if fe u v gt 1 f Theorem 4 The algorithm Approximate Local Connectivity Test accepts all vertex pairs that are f connected and rejects all vertex pairs that are not 1 f connected The algorithm runs in time fe log L Trup where Tmwp O m is the time required to find a minimum weight L short path in a weighting of the subgraph Gu v e and m is the number of edges in Neja u U Ne 2 v Proof If A reaches size f then we correctly accept since fe u v gt f If A is maximal then the edges used in A form an amp short u v cut since every short path must intersect some path in A This cut has fewer than fl edges since A contains fewer than f paths which are all 4 short This cut implies that ce u v lt f and combining this with equation 5 implies that the algorithm Max Short Flow computes an 1 approximation felu v in 4 fllog iterations At this point if fe u v gt f then f gt 1 f by the approximation guarantee and so we accept If fe u v lt 1 f then filu v lt felu v lt 1 f and so we reject The running time
21. o be its largest f local subgraph providing a way to partition G into local and global edges The main result of 3 is that the local graph of a hybrid graph is Research supported in part by NSF Grants DMS 0100472 and ITR 0205061 1A conference version appeared in Proceedings of the Twelfth Annual Symposium on Graph Drawing 2004 equal to the original local graph up to a small error indicating that local graphs are robust to the addition of random edges In this paper we demonstrate that partitioning a graph into local and global edges based on local connec tivity can be done quickly and can be useful in graph drawing To obtain local global partitions for large graphs we present an approximation algorithm for computing the local graph We also give a new algorithm for the fundamental problem of computing the maximum short flow between given vertices The number of iterations required in our maximum short flow algorithm depends on the value fop of the maximum short flow We also give a new algorithm for the problem of local connectivity testing where we wish to determine whether there exists a short flow of a certain size ftest between given vertices The number of iterations required by our testing algorithm is determined by fies and not fopt so testing local connectivity can be done significantly faster than computing the maximum short flow Our algorithms are based on the maximum multicommodity flow algorithm of Garg and K nemann 1
22. o the set C of connector edges It is crucial to set the target lengths of the connector edges to ensure that the local components are separated in the resulting drawing but are not placed extremely far apart We will set the target lengths of the connector edges to 11 moderate values which depend on the sizes of the components being bridged The result is a partition of the edges of G into four sets Tentacle Local Shortcut Connector We use the following length assignment The edges in T are given target length 1 The edges in L are given target length c some small constant which determines the relative size of the tentacles The shortcut edges in S are given target length 100 c A connector edge in C bridging components of size a and b is assigned target length ab e Figure 4 The T L C S partition Figure 5 Two local components in the collaboration graph with shortcut edges and connector edges 6 Examples We have implemented the Extract algorithm and produced several examples using both the simple L G partition and the T L C S partition Figures 6 9 are the grid and hypercube examples described in Section 5 1 In these figures the edges in L are drawn in darker blue or black and the edges of G in red or gray Jerry Grossman 18 has graciously provided data from a collaboration graph of the second kind where each vertex represents an author and each edge represents a joint paper with two authors
23. o v and each row represents an edge in the graph then finding fe u v the maximum short flow between u and v can be viewed as the following linear program felu v max 17x Ax lt I x gt 0 1 The linear programming dual of the maximum short flow problem is a fractional cut problem An short fractional cut is a weight function w E gt R such that X ep c e gt 1 for every short u v path P The dual of the short maximum flow problem is to find an short fractional cut that minimizes cle We let we u v denote the size of a minimum short fractional cut and note that LP duality implies ag u v lt felu v welu v lt celu v 2 Definition 1 Two vertices u and v are f l connected if felu v gt f Since all the coefficients in the incidence matrix cost vector and constraint vector in the problem formulation 1 are nonnegative the maximum short flow problem belongs to a special subset of linear programs called fractional packing problems for which there exist general techniques that often lead to polynomial time algorithms 29 In Section 3 we present a fast primal dual algorithm for computing the maximum short flow We will also present an algorithm to test whether two vertices are f connected which can be significantly faster than computing the maximum short flow 2 2 Mengerian Theorems for Short Paths It was mentioned previously that ae u v and ce u v are not necessaril
24. ph The grid graph P x P is a 1 3 local graph and all edges not on the border are 3 3 connected The infinite grid graph and the toroidal grid graph Cn x Cn are 3 3 connected The random geometric graph is displayed in the figures below with the local edges displayed in a darker color than the global edges The other examples are included in section 6 10 Figure 2 The modified geometric graph G n d p with Figure 3 The same graph with target lengths set by all target lengths equal the Local Global partition using f 3 3 5 2 A More Sophisticated Partition for Real World Examples The simple local global partition H L G and length assignment scheme presented in the previous section will not produce good results for real examples We will present a different partition which attempts to address the main problems that arise Some of the modifications are motivated solely by practical concerns in order to produce reasonable drawings while still incorporating the local global partition but many of the obstacles to adapting the local global partition to real examples are predicted by models of random power law graphs We expect a random power law graph to have an octopus structure In particular a random power law graph with exponent 3 where 2 lt 8 lt 3 contains a dense subgraph called the core with n s s vertices Almost all vertices are within distance log log n of the core although there are vertices
25. t proceeds from x to x 41 by taking a base edge whenever possible has length at most 4n 2 n 3n 2 Thus ce u v gt n and so n 4 GS 3n 2 f23 celu v It is not hard to modify the above construction to obtain examples for 3n 1 and 3n with ce u v gt We can increase l by 1 or 2 without changing ay u v or ce u v if we add a vertex xo let u zo and connect xo to x with 2n paths of length 1 or 2n paths of length 2 2 3 Local Graphs Definition 2 A graph L is f local if for each edge u v in L the endpoints u and v are f connected in L For example the toroidal grid graph Ch x Chn is 3 3 local This graph is also 4 5 local which is slightly less obvious and highlights the difference between ag u v and fe u v A 4 short flow of size 5 between the endpoints of a grid edge is shown in the figure below The correct combination to take is 1 of the path in the grid on the left and 1 2 of each path in the remaining grids Figure 1 A 5 bounded flow of size 4 between endpoints of a grid edge The union of two f local graphs is f 2 local and so there is a unique largest f 2 local subgraph of G which we denote Ls G In Section 4 we will present approximation algorithms for computing L G It is important to note that Ly G is not necessarily connected 2 4 Random Graphs with Specified Expected Degree Sequence A random graph G w with speci
26. ximation ratio y is Bp lt e F lt 7 logie 5 Substitute the bound on t from equation 4 to obtain 1l e e nts y lt log In 4 t 6 In 1 e ln ite site The ratio eas is 1 1 if we set 6 1 1 Ve With this 6 we have l Ce o Gee AS ee Analysis of the running time Each edge can have its weight multiplied by 1 at most log H times until it s weight reaches 1 and it can not be further increased If C u v is an short cut then at every time step some edge in C u v has its weight multiplied by 1 Thus the algorithm performs at most celu v logy 4 ite iterations before terminating To obtain the stated approximation ratio the initial weight 6 is set to 1 1 6 71 4 Thus the number of iterations required is at most 1l e 1 2 celu v logy 4 er lt celu v z log 1 lt celu va logs 5 The number of iterations can also be bounded in terms of the flow by applying the bound c u v lt felu v which was mentioned in Section 2 1 The number of iterations required is then fe u v 5 log The result follows It should be noted that our bound on the number of iterations depends crucially on the fact that all edge capacities are equal to 1 It is not hard to modify our algorithm to work in the case of arbitrary edge capacities see 17 but the running time may then depend on m 3 2 Testing Local Con
27. y equal It is an open problem to determine how much these quantities can differ with respect to It was shown by Lov sz Neumann Lara and Plummer 26 that cp lt ap Boyles and Exoo 8 have given a family of graphs where cg gt ag Their results were stated for the case of vertex disjoint paths but the results convert easily to the edge disjoint case which we are considering We now present a simple construction showing that cg gt ag for infinitely many improving the best known lower bound We conjecture that ce lt 4 o 1 a for all graphs Theorem 1 For every there exists a graph such that ag u v 1 and ce u v gt Proof Consider a path P z1 n of length 2n 1 We add 2n disjoint paths of length 2 between each pair of adjacent vertices x and x 4 Call this graph G n and let u x and v r We refer to the edges of P as base edges It is easy to see that an s t path using at most k base edges has length at least 4n 2 k If we set 3n 2 then every short path must use at least n base edges so that its length is at most 4n 2 n 3n 2 Since there are only 2n 1 base edges any two short paths must intersect in a base edge so a u v 1 We now consider the size of a minimum short cut C Without loss of generality we can assume that C cuts only base edges If C cuts n 1 or fewer base edges then n base edges remain and the path tha
Download Pdf Manuals
Related Search