Graph Partitioning and Decomposition Techniques

Explore various graph partition problems and decomposition methods such as regularity partitions, representative sets, and 2-neighborhood representations. Learn about techniques to aggregate, scale down, sample, and divide graphs for efficient analysis and computation. Discover how nodes can be represented in small, similar sets and understand the concept of weak regularity lemma for measuring closeness in graph partitions.

• Graph Partitioning
• Decomposition Techniques
• Regularity Partitions
• Representative Sets
• 2-Neighborhood Representations

raffae Follow

Uploaded on Sep 26, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Partitioning and decomposing graphs L szl Lov sz Hungarian Academy of Sciences and E tv s Lor nd University, Budapest January 2018 1

2. Graph partition problems Aggragate and scale down Regularity partitions Representative sets Sampling Divide and conquer Components Blocks Tree-decomposition January 2018 2

3. Representative set of nodes Small size, (almost) every node is similar to one of the nodes in the set When are two nodes similar? For dense graphs, the right notion - Neighbors... - (Almost) same neighborhood... - (Almost) same second neighborhood 3

4. Representative set of nodes random edge set, with density 1/2 4

5. 2-neighborhood representation A=AG: adjacency matrix of G n=|V(G)|: number of nodes Columns of A: representation in Rn Columns of A2: representation in Rn October 2015 5

6. 2-neighborhood representation A: adjacency matrix of graph G ai: column i of A2 1 n d s t ( , ) a a = - s t 2 2 9/26/2024 6

7. 2-neighborhood representation number of 2-paths: highly concentrated around expectation probability of connecting f(distance) 2-neighborhood distance: ~ spherical distance 2-neighborhood representation: ~ sphere October 2015 7

8. Regularity partitions Weak Regularity Lemma (Szemer di) Frieze-Kannan Vi pij: edge density betweenViand Vj Vj replace edges between Vi and Vj by random edges with prob pij to get GP 8

9. Regularity partitions Weak Regularity Lemma (Szemer di) Frieze-Kannan Vi Is this a strong enough measure of closeness? Vj S k partition P with P k : " $ = 2 P 2 S ( ): V G ( [ ]) E G S E G S ( [ ]) n " - log k 9

10. Regularity partitions Weak Regularity Lemma (Szemer di) Frieze-Kannan Vi Vj # of triangles, pentagons, (almost) same in G and GP maximum cut, bisection, (almost) same in G and GP energies, entropies, (almost) same in G and GP 10

11. 2-neighborhood representation k random nodes Voronoi diagram = (weak) regularity partition 11

12. Using a representative set 1/2 ( ) 2 d s t = ( , ) E (P ( su uv , ( ) E G P ( w tw wv , ( )) E G - v u 2 w t u s v This is a metric, computable by sampling. Service - query from node: which class am I in? - reply: index of closest representative node 12

13. A graph partition problem k-edge-separator: T E(G), component of G-T has k nodes Finite graph: | T n | = sep ( ) k G min : T k -edge-separa tor January 2018 13

14. A graph partition problem Polynomially solvable (but difficult) Edmonds Matching Algorithm k=2: matching problem k=3: triangle matching problem NP-hard Approximation? January 2018 14

15. Very large graphs with bounded degree Find a perfect matching in G. distributed algorithm: Nguyen and Onak January 2018 15

16. Very large graphs with bounded degree distributed algorithms local algorithms January 2018 16

17. Very large graphs with bounded degree distributed algorithms local algorithms property testing January 2018 17

18. Fractional graph partition problem = X ( ): V G G X connected, X k R k T: optimal k-edge-separator = G T R ( ): V H H comp't of F k January 2018 18

19. Fractional graph partition problem Y n , if Y , F = ( Y ) 0, if Y \ R F k Y = ( ) Y 1 probability distribution R k ( ) Y Y 1 n = marginal uniform Y x Y Y Y = ( ) Y 2sep ( ) G expected expansion k R k January 2018 19

20. Fractional graph partition problem Y Y 1 2 kG = Define sep ( ) min E probability distribution on Rk with uniform marginal 8 D sep ( ) sep ( ) k G G sep ( ) logsep ( ) G k k G k no dependence on k or n January 2018 20

21. Proof sketch 8 D sep ( ) k G sep ( ) logsep ( ) G k G k Greedy algorithm: For j=1,2,..., select Y1,Y2,... so thatYjis the minimizer of k Y for small k and large graph: very many steps! Phases, whose number is Y \( Y ... Y ) 1 j 1 Output: X= Y1 Y2 ... O(1/sepk*) January 2018 21

22. Very large graphs with bounded degree distributed algorithms local algorithms property testing The infinite is a good approximation of the large finite. January 2018 22

23. Graphing Bounded degree ( D) Borel graph on [0,1] with double counting condition: = A B = ( ) deg( , ) deg( , ) x B dx x A dx A B Extends to measure on Borel subsets of V2. edge measure January 2018 23

24. Why graphings? Ergodic theory Finitely generated groups Limits of convergent graphs sequences with bounded degree January 2018 24

25. Graphing, examples January 2018 25

26. Graphing, examples unit circumference irrational components: 2-way infinite paths January 2018 26

27. Graphing, examples unit circumference , irrational, lin. indep 1x1 torus , irrational components: grids components: grids January 2018 27

28. Penrose tilings rhombic icosahedron de Bruijn - B r sz January 2018 28

29. Why graphings? distributed algorithms local algorithms (on bounded degree graphs) property testing (on bounded degree graphs) local algorithms on graphings January 2018 29

30. Graphing partition problem k-edge-separator: T E(G), component of G-T has k nodes Finite graph: | | min : -edge-separa sep ( ) k T k n T = G tor Graphing: sep ( k = ( ): T G ) min T k -edge-separato r Graphing G hyperfinite: sepk(G) 0 (k ) January 2018 30

31. Hyperfinite graphings, examples Diophantine approximation January 2018 31

32. Hyperfinite graph families Family G of finite graphs is hyperfinite: max sep (G) k 0 ( k 0). G G Hyperfinite: paths, trees, planar graphs, every non-trivial minor-closed property Non-hyperfinite: expanders January 2018 32

33. Hyperfinite graph sequences If Gn G, then {Gn} is hyperfinite G is hyperfinite Schramm (Benjamini-Shapira-Schramm) January 2018 33

34. Hyperfinite graph families Every graph property is testable in any family of hyperfinite graphs. Newman Sohler (Benjamini-Schramm-Shapira, Elek) graphs with bounded tree-width. Many graph properties are polynomial time testable for January 2018 34

35. January 2018 35

36. Local equivalence, definition x V Gx: component of x uniform random x Gx: random connected rooted (countable) graph unimodular random network Benjamini - Schramm January 2018 36

37. Hyperfinite graphings If G1and G2are locally equivalent, then G1is hyperfinite G2is hyperfinite G G1 G2 January 2018 37

38. Local equivalence, definition x V Gx: component of x G1, G2locally equivalent: for random uniform x V, distributions of (G1)xand (G2)x are the same January 2018 38

39. Local isomorphism, definition : V(G1) V(G2) local isomorphism: measure preserving and ( x) isomorphism between (G1)xand (G2) (x) Existence of local isomorphism proves local equivalence. January 2018 39

40. Local isomorphism, example components: grids components: grids (x,y) x+y mod 1 January 2018 40

41. Local equivalence G1and G2are locally equivalent G and local isomorphisms G G1, G G2. G G1 G2 January 2018 41

42. Hyperfinite graphings If G1and G2are locally equivalent, then G1is hyperfinite G2is hyperfinite G ? G1 G2 January 2018 42

43. Local isomorphism forward (x,y) x+y mod 1 Diophantine approximation January 2018 43

44. Pushing forward and pulling back measure preserving subset linear relaxation measure January 2018 44

45. Fractional separation duality If G1and G2are locally equivalent, then sep ( ) k G = sep ( G ) 1 k 2 G2 easy G1 ) sep ( sep ( G G ) k 1 k 2 ) sep ( sep ( G G ) ? k 1 k 2 Duality! January 2018 45