近似超图划分及其应用：算法与理论进展

42 浏览量更新于2024-07-14 收藏 350KB PDF 举报

"这篇论文《Approximate Hypergraph Partitioning and Applications》由Eldar Fischer、Arie Matsliah和Asaf Shapira合著，主要探讨了图的近似超图划分及其在计算机科学中的应用。Szemerédi的正则性引理是极端组合数学中的一个基础性结果，它大致表明任何稠密图都可以被划分为有限数量的准随机图。这一引理在理论计算机科学中有许多应用，因此人们对其算法化版本进行了大量研究。" 在本文中，作者们提出了以下主要成果： 1. 他们引入了一种新的方法来解决图的正规划分问题，这导致了一个出乎意料的简单O(n)时间的算法化正则性引理，从而改进了先前的O(n^2)时间算法。值得注意的是，与之前的[3,10,14,15,21]等方法不同，这些方法只能保证找到塔型大小的划分，新算法能够在存在小型正规划分的情况下找到它。 2. 对于任何常数r（r≥3），他们提供了一个O(n)时间的随机化算法来构造r-均匀超图的正规划分，从而改进了先前的O(n^(2r-1))时间确定性算法。这在处理高维超图时显著提高了效率。超图分区是图论和计算复杂性理论中的一个重要主题，特别是在网络分析、数据聚类和优化问题中。通过近似超图划分，可以将复杂的网络结构简化为更易于处理的单元，这对于理解和操作大规模复杂系统非常有用。例如，在社交网络分析中，可以将用户群划分为具有相似交互模式的社区；在计算机科学中，这种划分技术可应用于并行计算任务的调度，以提高效率和资源利用率。 Szemerédi的正则性引理在算法设计中扮演了核心角色，因为它提供了一种对复杂图结构进行结构化的方法。通过算法化这个引理，可以为实际问题如图着色、图同构测试和最优化问题提供更有效的解决方案。论文中提出的O(n)时间复杂度算法不仅提高了计算效率，而且在寻找更小规模的正规划分方面也有所突破，这使得算法在处理大型图数据集时更具实用性。这项工作对理论计算机科学的贡献在于推进了正则性引理的算法化实现，以及在处理高维超图划分问题上的效率提升，这些进展对于实际应用如网络分析、数据挖掘和分布式计算等领域具有深远影响。

is crucial to us since we apply this algorithm to obtain the O(n) time algorithmic version of the

graph regularity lemma (stated in Theorem 1) as well as the O(n) time algorithmic version of the

hypergraph regularity lemma (see Section 4). However in itself the running time diﬀerence could

possibly be bridged by importing some arguments from our proof into the proofs of [5] or [13] rather

than proving the entire result from scratch.

1.4 Organization

The rest of the paper is organized as follows. In Section 2 we explicitly deﬁne the hypergraph partition

problems we consider here, and state the hypergraph partition algorithm we obtain. In Section 3

we prove Theorem 1 by reducing the task of ﬁnding a regular partition of a graph to the task of

ﬁnding an appropriate partition of a hypergraph. In Section 4 we obtain an algorithmic version of

the regularity lemma for r-uniform hypergraphs. In Section 5 we give an overview of the proof of the

hypergraph partition algorithm, and in Section 6 we give the full details of this algorithm. Section

7 contains some concluding remarks and open problems.

2 The Hypergraph Partition Algorithm

We now formally deﬁne the hypergraph problem that we will study in this paper.

2.1 General notation

We use [k] to denote the set {1, . . . , k}, and use a = b±c as a shorthand for b−c ≤ a ≤ b+ c. For two

(multivariate) functions f, g :

i=1

→ R

, we say that f = O(g) if there exist constants c, d > 0

such that for all x

∈ D

, . . . , x

∈ D

we have f(x

, . . . , x

) ≤ c · g(x

, . . . , x

) + d. Similarly we

write f = poly(g) is there exist constants c, d > 0 such that f(x

, . . . , x

) ≤ (g(x

, . . . , x

))

+ d for

all x

, . . . , x

, and write f = exp(g) if there exist constants for which f(x

, . . . , x

) ≤ 2

(g(x

,...,x

))

for all x

, . . . , x

. We also use the shorthand f = poly(g

, . . . , g

) for f = poly(

i=1

). In the

following we make no attempt to optimize the coeﬃcients involved, only the function types.

2.2 Hypergraphs

We consider directed hypergraphs H = (V, E

, E

, . . . , E

) with n vertices and s directed edge sets.

Every edge set E

⊆ V

is a set of ordered r

-tuples

(ordered sets with possible repetitions) over

V . That is, for every edge set E

(H) we think of any of the edges e ∈ E

as a length r

sequence of

members of V (H). We say that a hypergraph H is of type (s, r

, . . . , r

) if it has exactly s edge sets

, . . . , E

, and for each i ∈ [s], the set E

contains edges of size exactly r

. Note that the usual notion

The readers with a background in Logic would recognize these as arity r

relations.

of a directed graph corresponds to hypergraphs of type (1, 2). For an r

-tuple e = (v

, . . . , v

) ∈ E

we say that v

is in the j

place of e (or is simply the j

vertex of e). We also set r = max

For the algorithms that we develop here, we generalize the usual edge queries used in the dense

graph model of [16] as follows. Given a hypergraph H = (V, E

, . . . , E

) of typ e (s, r

, . . . , r

), an

edge oracle for H is a function Q : [s] × V

≤r

→ {0, 1} such that Q(i, v

, . . . , v

) = 1 if and only if

, . . . , v

) ∈ E

When analysing our testing algorithm we assume throughout that a uniformly random choice of

a vertex v ∈ V , as well as an edge query, can all be done in constant time.

2.3 The partition property

Let H be a hypergraph of type (s, r

, . . . , r

) and let Π = {V

, . . . , V

} be a partition of V (H). Let

us introduce a notation for counting the number of edges of E

(H) with a speciﬁc placement of their

vertices within the partition classes of Π (remember that the edges are ordered). For every i ∈ [s] we

denote by Φ

the set of all possible mappings φ : [r

] → [k]. We think of every φ ∈ Φ

as mapping the

vertices of an r

-tuple to the components of Π. We denote by E

i,φ

⊆ E

the following set of r

-tuples:

i,φ

= {(v

, . . . , v

) ∈ E

: ∀j ∈ [r

], v

∈ V

φ(j)

}

For example, let G = (V, E) be a hypergraph of type (1, 2), that is a usual directed graph. For

some partition Π = {V

, V

} of V and the identity function φ : [2] → [2], φ(i) , i, the set E

1,φ

⊆ E

contains all edges (u, v) ∈ E directed from u ∈ V

to v ∈ V

We now introduce a notion that generalizes the partition instances that were discussed in [16] in

the context of graphs.

Deﬁnition 2.1 (Density tensors) A density tensor of order k and type (s, r

, . . . , r

) is a se-

quence ψ =



hρ

j∈[k]

, hµ

i,φ

i∈[s],φ∈Φ

of reals (between 0 and 1), specifying the presumed normal-

ized sizes of |V

| and |E

i,φ

| of a k-wise partition of a hypergraph of type (s, r

, . . . , r

) (whenever

k and (s, r

, . . . , r

) are clear from the context, we call ψ simply a density tensor). In particu-

lar, given a partition Π = {V

, V

, . . . , V

} of a hypergraph H, we set ψ

to be the density ten-

sor

hρ

j∈[k]

, hµ

i,φ

i∈[s],φ∈Φ

with the property that for all j, ρ

· |V

| and for all i and φ,

i,φ

· |E

i,φ

Deﬁnition 2.2 (Partition properties induced by density tensors) For a ﬁxed hypergraph H

of type (s, r

, . . . , r

), a set Ψ of density tensors (of order k and type (s, r

, . . . , r

)) deﬁnes a property

of V (H)’s k-wise partitions as follows. We say that a partition Π of V (H) (exactly) satisﬁes Ψ if

there exists a density tensor ψ =



hρ

j∈[k]

, hµ

i,φ

i∈[s],φ∈Φ

∈ Ψ, such that ψ and the density tensor

of Π are equal. Namely, Π satisﬁes Ψ if there is ψ =



hρ

j∈[k]

, hµ

i,φ

i∈[s],φ∈Φ

∈ Ψ such that

• for all j ∈ [k], ρ

= ρ

剩余36页未读，继续阅读

weixin_38721652

粉丝: 3
资源: 935

近似超图划分及其应用：算法与理论进展

The Longest Common Extension Problem Revisited and Applications to Approximate String Searching (2010)-计算机科学

ApEn.rar_apen_approximate_approximate entropy_non-stationary

Cache, Hash and Space-Efficient Bloom Filters-计算机科学

On the k-Independence Required by Linear Probing and Minwise Independece - December 25th, 2014 (1302.5127)-计算机科学

Approximate affine linear relationship between L-1 norm objective function values and L-2 norm constraint bounds

Theory of Locality Sensitive Hashing - CS246 Stanford (Slides)-计算机科学

Improved Fast Similarity Search in Dictionaries - 2010 (1008.1191v2)-计算机科学

流形正则化matlab代码-Approximate-Manifold-Regularization-Scalable-Algorithm-an

A Locality-Sensitive Hash for Real Vectors (10.1.1.215.7690)-计算机科学

ist的matlab代码-Fast-Approximate-Energy-Minimization-via-Graph-Cuts:最大限度地减

最新资源