論文の概要、ライセンス

# (参考訳) 密結合クラスタ探索のための局所アルゴリズム [全文訳有]

Local Algorithms for Finding Densely Connected Clusters ( http://arxiv.org/abs/2106.05245v1 )

ライセンス: CC BY 4.0
Peter Macgregor and He Sun(参考訳) 局所グラフクラスタリングは大規模グラフを解析するための重要なアルゴリズム手法であり、多くのデータサイエンスの分野で広く応用されている。 ほとんどの(ローカルな)グラフクラスタリングアルゴリズムの目的は、低コンダクタンスの頂点集合を見つけることであるが、現実のデータセットを分析する際にクラスタ間の相互接続の重要性を強調する最近の一連の研究がある。 この研究の行に続いて、我々は、その相互接続とグラフの他の部分との関係に関して定義された頂点集合のペアを見つけるための局所アルゴリズムについて研究する。 我々の分析の鍵は、多重集合の構造を縮小グラフ内の1つの頂点集合に関連付ける新しい還元手法である。 多くの潜在的なアプリケーションの中で、我々のアルゴリズムは、interstate Disputes Dataset と US Migration Dataset の密結合クラスタを復元することに成功した。

Local graph clustering is an important algorithmic technique for analysing massive graphs, and has been widely applied in many research fields of data science. While the objective of most (local) graph clustering algorithms is to find a vertex set of low conductance, there has been a sequence of recent studies that highlight the importance of the inter-connection between clusters when analysing real-world datasets. Following this line of research, in this work we study local algorithms for finding a pair of vertex sets defined with respect to their inter-connection and their relationship with the rest of the graph. The key to our analysis is a new reduction technique that relates the structure of multiple sets to a single vertex set in the reduced graph. Among many potential applications, we show that our algorithms successfully recover densely connected clusters in the Interstate Disputes Dataset and the US Migration Dataset.
公開日: Wed, 9 Jun 2021 17:40:45 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
1 2 0 2 n u J 1 2 0 2 n u J 0.85
9 ] S D . s c [ 9 ] S D。 sc [ 0.69
1 v 5 4 2 5 0 1 v 5 4 2 5 0 0.85
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
Local Algorithms for Finding Densely Connected Clusters 密結合クラスタ探索のための局所アルゴリズム 0.76
Peter Macgregor* Peter Macgregor 0.56
He Sun† Abstract Local graph clustering is an important algorithmic technique for analysing massive graphs, and has been widely applied in many research fields of data science. 日光。 概要 局所グラフクラスタリングは大規模グラフを解析するための重要なアルゴリズム手法であり、多くのデータサイエンスの分野で広く応用されている。 0.56
While the objective of most (local) graph clustering algorithms is to find a vertex set of low conductance, there has been a sequence of recent studies that highlight the importance of the inter-connection between clusters when analysing real-world datasets. ほとんどの(ローカルな)グラフクラスタリングアルゴリズムの目的は、低コンダクタンスの頂点集合を見つけることであるが、現実のデータセットを分析する際にクラスタ間の相互接続の重要性を強調する最近の一連の研究がある。 0.81
Following this line of research, in this work we study local algorithms for finding a pair of vertex sets defined with respect to their inter-connection and their relationship with the rest of the graph. この研究の行に続いて、我々は、その相互接続とグラフの他の部分との関係に関して定義された頂点集合のペアを見つけるための局所アルゴリズムについて研究する。 0.76
The key to our analysis is a new reduction technique that relates the structure of multiple sets to a single vertex set in the reduced graph. 我々の分析の鍵は、多重集合の構造を縮小グラフ内の1つの頂点集合に関連付ける新しい還元手法である。 0.80
Among many potential applications, we show that our algorithms successfully recover densely connected clusters in the Interstate Disputes Dataset and the US Migration Dataset. 多くの潜在的なアプリケーションの中で、我々のアルゴリズムは、interstate Disputes Dataset と US Migration Dataset の密結合クラスタを復元することに成功した。 0.75
1 Introduction Given an arbitrary vertex u of a graph G = (V, E) as input, a local graph clustering algorithm finds some low-conductance set S ⊂ V containing u, while the algorithm runs in time proportional to the size of the target cluster and independent of the size of the graph G. Because of the increasing size of available datasets, which makes centralised computation too expensive, local graph clustering has become an important learning technique for analysing a number of large-scale graphs and has been applied to solve many other learning and combinatorial optimisation problems [1, 5, 11, 16, 25, 29, 30, 32]. はじめに Given an arbitrary vertex u of a graph G = (V, E) as input, a local graph clustering algorithm finds some low-conductance set S ⊂ V containing u, while the algorithm runs in time proportional to the size of the target cluster and independent of the size of the graph G. Because of the increasing size of available datasets, which makes centralised computation too expensive, local graph clustering has become an important learning technique for analysing a number of large-scale graphs and has been applied to solve many other learning and combinatorial optimisation problems [1, 5, 11, 16, 25, 29, 30, 32]. 0.72
1.1 Our Contribution We study local graph clustering for learning the structure of clusters that are defined by their inter-connections, and present two local algorithms to achieve this objective in both undirected graphs and directed ones. 1.1 私たちのコントリビューションでは, 相互接続によって定義されるクラスタの構造を学習するための局所グラフクラスタリングについて検討し, この目的を達成するための2つの局所アルゴリズムを提案する。
訳抜け防止モード: 1.1 コントリビューション ローカルグラフクラスタリングの研究 相互接続によって定義されるクラスタの構造を学ぶ。 2つのアルゴリズムを 無向グラフと有向グラフの両方で この目的を達成するためです
0.81
Our first result is a local algorithm for finding densely connected clusters in an undirected graph G = (V, E): given any seed vertex u, our algorithm is designed to find two clusters L, R around u, which are densely connected to each other and are loosely connected to V \ (L ∪ R). 最初の結果は、非向グラフ g = (v, e): 任意のシード頂点 u に対して、u の周りの二つのクラスター l, r を見つけるための局所的なアルゴリズムである。
訳抜け防止モード: 最初の結果は、無向グラフ G = (V,) 内の密結合クラスタを見つけるための局所アルゴリズムである。 E)任意の種子頂点u, 我々のアルゴリズムは 2 つのクラスタ L, R を u の周りに見つけるように設計されている 互いに密結合であり、V \ (L ) R と疎結合である。
0.84
The design of our algorithm is based on a new reduction that allows us to relate the connections between L, R and V \ (L ∪ R) to a single cluster in the resulting graph H, and a generalised analysis of Pagerank-based algorithms for local graph clustering. アルゴリズムの設計は、L, R と V の接続を結果のグラフ H の単一クラスタに関連付けることのできる新しい還元法と、局所グラフクラスタリングのための Pagerank ベースのアルゴリズムを一般化した解析に基づいている。 0.75
The significance of our designed algorithm is demonstrated by our experimental results on the Interstate Dispute Network from 1816 to 2010. 提案アルゴリズムの意義は1816年から2010年までの州間紛争ネットワークの実験結果によって実証された。 0.77
By connecting two vertices (countries) with an undirected edge weighted according to the severity of their military disputes and using the USA as the seed vertex, our algorithm recovers two groups of countries that tend to have conflicts with each other, and shows how the two groups evolve over time. 2つの頂点(国)を軍事紛争の深刻度に応じて重み付けされた無向エッジで接続し、アメリカを種頂点として使用することにより、我々のアルゴリズムは互いに対立する傾向にある2つの国のグループを復元し、その2つのグループが時間とともにどのように進化していくかを示す。 0.67
In particular, as shown in Figures 1(a)-(d), our algorithm not only identifies the changing roles of Russia, Japan, and eastern Europe in line with 20th century geopolitics, but also the reunification of east and west Germany around 1990. 特に、図1(a)-(d)に示すように、我々のアルゴリズムは、20世紀におけるロシア、日本、東欧の役割の変化だけでなく、1990年頃の東ドイツと西ドイツの再統一も示している。
訳抜け防止モード: 特に、図1(a)-(d)に示すように、我々のアルゴリズムは20世紀の地政学に沿ってロシア、日本、東欧の役割の変化を識別するだけではない。 また、1990年頃に東ドイツと西ドイツが再統一された。
0.70
We further study densely connected clusters in a directed graph (digraph). さらに、有向グラフ(グラフ)における密結合クラスタについて研究する。 0.68
Specifically, given any vertex u in a digraph G = (V, E) as input, our second local algorithm outputs two disjoint vertex sets L and R, such that (i) there are many edges from L to R, and (ii) L ∪ R is loosely connected to V \ (L ∪ R). 具体的には、ダイアグラム g = (v, e) の任意の頂点 u を入力として与えると、第2の局所アルゴリズムは 2 つの非連結な頂点集合 l と r を出力し、(i) l から r への多くの辺が存在し、(ii) l から r は v に疎連結である。 0.72
The design of our algorithm is based on the following two techniques: (1) a new reduction that allows us to relate the edge weight from L to R, as well as the edge connections between L ∪ R and V \ (L ∪ R), to a single vertex set in the resulting undirected graph H; (2) a refined analysis of the ESP-based algorithm for local graph clustering. このアルゴリズムの設計は,(1)l から r へのエッジ重み関係,および l と v の間のエッジ接続を,結果として得られる非向グラフ h 内の単一の頂点集合に関連付ける新しい還元,(2)局所グラフクラスタリングのための esp ベースのアルゴリズムの洗練された解析,という2つの手法に基づいている。 0.74
We *University of Edinburgh, peter.macgregor@ed.a c.uk †University of Edinburgh, h.sun@ed.ac.uk 私たち ※エディンバラ大学・ピーター・マクグレゴール大学・エディンバラ大学・h.sun@ed.ac.uk 0.67
1 1 0.85
英語(論文から抽出)日本語訳スコア
(a) 1816-1900 (a)1816-1900 0.62
(b) 1900-1950 (b)1900-1950 0.79
(c) 1950-1990 (c)1950-1990 0.79
(d) 1990-2010 (d)1990-2010 0.81
(e) Ohio Seed (f) New York Seed (e)オハイオ種子 (f)ニューヨーク種 0.58
(g) California Seed (g)カリフォルニアの種 0.85
(h) Florida Seed Figure 1: (a)-(d) Clusters found by LocBipartDC on the interstate dispute network, using the USA as the seed vertex. (h)フロリダ種子 図1:(a)-(d)クラスタ locbipartdcが州間高速道路紛争ネットワークで見つけ、米国をシード頂点として使用します。
訳抜け防止モード: (h)フロリダ種子 図1 : (a)-(d ) 状態間紛争ネットワーク上でLocBipartDCが発見したクラスタ。 米国を種子頂点として使用すること。
0.69
In each case, countries in the yellow cluster tend to enter conflicts with countries in the blue cluster and vice versa. いずれの場合も、黄星団の国は青星団の国と対立する傾向があり、その逆である。 0.51
(e)-(h) Clusters found by EvoCutDirected in the US migration network. (e)-(h) 米国のマイグレーションネットワークでEvoCutDirectedによって発見されたクラスタ。 0.77
There is a large net flow from the red counties to the green counties. 赤い郡から緑の郡まで大きな水が流れている。 0.52
show that our algorithm is able to recover local densely connected clusters in the US migration dataset, in which two vertex sets L, R defined as above could represent a higher-order migration trend. 我々のアルゴリズムは、上記のような2つの頂点集合 L, R が高次移動傾向を示す可能性のある、USマイグレーションデータセット内の局所的に密結合されたクラスタを復元可能であることを示す。 0.71
In particular, as shown in Figures 1(e)–(h), by using different counties as starting vertices, our algorithm uncovers refined and more localised migration patterns than the previous work on the same dataset [10]. 特に、図1(e)–(h)に示すように、異なる郡を出発頂点として使うことで、同じデータセットの以前の作業よりも洗練された、よりローカライズされたマイグレーションパターンを明らかにする [10]。 0.69
To the best of our knowledge, our work represents the first local clustering algorithm that achieves a similar goal. 我々の知る限りでは、我々の研究は同様の目標を達成する最初のローカルクラスタリングアルゴリズムを表している。 0.71
1.2 Related Work Li and Peng [15] study the same problem for undirected graphs, and present a random walk based algorithm. 1.2 関連作業 Li と Peng [15] は同じ問題を無向グラフで研究し,ランダムウォークに基づくアルゴリズムを提案する。 0.86
Andersen [1] studies a similar problem for undirected graphs under a different objective function, and our algorithm’s runtime significantly improves the one in [1]. Andersen [1] は、異なる目的関数の下で無向グラフの同様の問題を研究し、我々のアルゴリズムのランタイムは[1] のグラフを著しく改善する。 0.77
There is some recent work on local clustering for hypergraphs [25], and algorithms for finding higher-order structures of graphs based on network motifs both centrally [7, 8] and locally [30]. ハイパーグラフ [25] の局所クラスタリングに関する最近の研究や、[7, 8] と [30] の両方でネットワークモチーフに基づくグラフの高次構造を見つけるアルゴリズムがある。 0.77
These algorithms are designed to find different types of clusters, and cannot be directly compared with ours. これらのアルゴリズムは、異なるタイプのクラスタを見つけるように設計されており、私たちと直接比較することはできない。 0.66
Our problem is related to the problem of finding clusters in disassortative networks [22, 23, 31], although the existing techniques are based on semi-supervised, global methods while ours is unsupervised and local. 従来の手法は半教師付きグローバルな手法に基づいており,非教師付きかつ局所的な手法ではあるものの,異種ネットワーク(22, 23, 31)におけるクラスタの発見が問題となっている。 0.66
There are also recent studies which find clusters with a specific structure in the centralised setting [10, 14]. また、集中した設定 [10, 14] に特定の構造を持つクラスターを見つける最近の研究もある。 0.81
Our current work shows that such clusters can be learned locally via our presented new techniques. 我々の現在の研究は、そのようなクラスタを新しい技術を使ってローカルに学習できることを示しています。 0.55
2 Preliminaries volG(S) (cid:44)(cid:80) 予科2 volG(S) (cid:44)(cid:80) 0.68
Notation. For any undirected and unweighted graph G = (VG, EG) with n vertices and m edges, the degree of any vertex v is denoted by degG(v), and the set of neighbours of v is NG(v). 表記。 n 個の頂点と m 個の辺を持つ任意の無向グラフ G = (VG, EG) に対して、頂点 v の次数は degG(v) で表され、v の近傍の集合は NG(v) である。 0.65
For any S ⊆ V , its volume is v∈S deg(v), its boundary is ∂G(S) (cid:44) {(u, v) ∈ E : u ∈ S and v (cid:54)∈ S}, and its conductance is 任意の S {\displaystyle S} に対して、その体積は vinftyS deg(v) であり、その境界は ∂G(S) (cid:44) {(u, v) ∈ E : u ∈ S and v (cid:54)∂ S} であり、そのコンダクタンスである。 0.77
ΦG(S) (cid:44) シュG(S)(第44話) 0.63
|∂G(S)| min{volG(S), volG(V \ S)} . |∂g(s)| min{volg(s), volg(v \ s)} である。 0.79
head, respectively. For any S ⊂ VG, we define volout(S) =(cid:80) それぞれ頭。 任意の S > VG に対して、volout(S) =(cid:80) を定義する。 0.59
For disjoint S1, S2 ⊂ VG, e(S1, S2) is the number of edges between S1 and S2. 解離 S1 に対して、S2 は、e(S1, S2) は S1 と S2 の間の辺の数である。 0.67
When G = (VG, EG) is a digraph, for any u ∈ VG we use degout(u) and degin(u) to express the number of edges with u as the tail or the u∈S degin(u). g = (vg, eg) がディグラフであるとき、任意の u ∈ vg に対して、u を末尾とする辺の数や u الs degin(u) を表すために degout(u) と degin(u) を用いる。 0.75
For undirected graphs, we use DG to denote the n × n diagonal matrix with (DG)v,v = degG(v) for any vertex v ∈ V , and we use AG to represent the adjacency matrix of G defined by (AG)u,v = 1 if {u, v} ∈ EG, and (AG)u,v = 0 otherwise. 非方向グラフに対しては、任意の頂点 v ∈ V に対して (DG)v,v = degG(v) で n × n 対角行列を表すために DG を用い、 (AG)u,v = 1 if {u, v} ∈ EG, and (AG)u,v = 0 で定義される G の隣接行列を表すために AG を用いる。 0.85
The lazy random walk matrix of G is WG = (1/2) · (I + D−1 G AG). G の遅延ランダムウォーク行列は WG = (1/2) · (I + D−1 G AG) である。 0.78
For any set S ⊂ VG, χS is the indicator vector of S, i.e., χS(v) = 1 if v ∈ S, and χS(v) = 0 otherwise. 任意の集合 S {\displaystyle S} に対して、VG は S の指標ベクトル、すなわち v ∈ S のとき シュS(v) = 1 であり、そうでなければ シュS(v) = 0 である。 0.68
If the set consists of a single vertex v, we write χv instead of χ{v}. 集合が 1 つの頂点 v から成り立つなら、我々は .v の代わりに .v を書く。 0.64
Sometimes we drop the subscript G when the underlying graph is clear from the context. 基礎となるグラフがコンテキストから明確であるとき、サブスクリプトGをドロップすることもある。 0.58
For any vectors x, y ∈ Rn, we write x (cid:22) y if it holds for any v that x(v) ≤ y(v). 任意のベクトル x, y ∈ Rn に対して、x(v) ≤ y(v) を満たす任意の v に対して x (cid:22) y を記述する。 0.87
For u∈S degout(u), and volin(S) =(cid:80) のために u∂S degout(u) と volin(S) =(cid:80) 0.69
2 2 0.85
英語(論文から抽出)日本語訳スコア
p(v1) deg(v1) p(v1) deg(v1) 0.96
≥ p(v2) deg(v2) ≥ p(v2) deg(v2) 0.98
≥ . . . ≥ p(vn) deg(vn) ≥ . . . ≥ p(vn) deg(vn) 0.85
, any operators f, g : Rn → Rn, we define f ◦ g : Rn → Rn by f ◦ g(v) (cid:44) f (g(v)) for any v. For any vector p, we define the support of p to be supp(p) = {u : p(u) (cid:54)= 0}. , 任意の作用素 f, g : rn → rn に対し、任意のベクトル p に対して f: g(v) (cid:44) f (g(v)) によって f: g : rn → rn を定める: 任意のベクトル p に対して、p の支持を supp(p) = {u : p(u) (cid:54)= 0 と定義する。 0.86
The sweep sets of p are defined by (1) ordering all the vertices such that p のスイープ集合は、(1)すべての頂点を順序付けして定義される。 0.78
j = {v1, . j = {v1, . 0.97
. . , vj} for 1 ≤ j ≤ n. Throughout this paper, we will consider vectors to be and (2) constructing Sp row vectors, so the random walk update step for a distribution p is written as pW . . . 本論文を通じて, 1 ≤ j ≤ n に対して vj} が成立し,(2)sp 行ベクトルを構成するベクトルが成立すると考えられるので,分布 p のランダムウォーク更新ステップは pw と書く。 0.86
For ease of presentation we consider only unweighted graphs; however, our analysis can be easily generalised to the weighted case. 提示を容易にするため、未重み付きグラフのみを考えるが、解析は重み付きケースに容易に一般化できる。 0.71
The omitted proofs can be found in the Appendix. 省略された証明はAppendixで見ることができる。 0.70
Pagerank. Given an underlying graph G with the lazy random walk matrix W , the personalised Pagerank vector pr(α, s) is defined to be the unique solution of the equation Pagerank 遅延ランダムウォーク行列 W の基底グラフ G が与えられたとき、パーソナライズされたページランクベクトル pr(α, s) は方程式のユニークな解として定義される。
訳抜け防止モード: Pagerank 遅延ランダムウォーク行列 W を持つグラフ G が与えられたとき パーソナライズされたページランクベクトル pr(α , s ) は方程式のユニークな解として定義される
0.65
the personalised Pagerank vector can be written as pr(α, s) = α(cid:80)∞ パーソナライズされたページランクベクトルは pr(α, s) = α(cid:80)∞ と書くことができる 0.74
(1) where s ∈ Rn≥0 is a starting vector and α ∈ (0, 1] is called the teleport probability. 1) s ∈ Rn≥0 を始ベクトルとし、α ∈ (0, 1] をテレポート確率と呼ぶ。
訳抜け防止モード: ( 1 ) ここで s ∈ rn≥0 は始点ベクトルである そして α ∈ ( 0, 1 ] はテレポート確率と呼ばれる。
0.85
Andersen et al [4] show that t=0(1 − α)tsW t. Therefore, we could study pr(α, s) through the following random process: pick some integer t ∈ Z≥0 with probability α(1 − α)t, and perform a t-step lazy random walk, where the starting vertex of the random walk is picked according to s. Then, pr(α, s) describes the probability of reaching each vertex in this process. したがって、ある整数 t ∈ z≥0 を確率 α(1 − α)t で選択し、t ステップの遅延ランダムウォークを実行し、そこでランダムウォークの開始頂点を s に従って選択し、pr(α, s) はこの過程における各頂点に到達する確率を記述する。
訳抜け防止モード: Andersen et al [ 4 ] は t=0(1 − α)tsW t であることを示す。 以下のランダムな過程を通して pr(α, s ) を研究できる: 確率 α(1 − α)t の整数 t ∈ Z≥0 を選ぶ。 t ステップの遅延ランダムウォークを実行すると、ランダムウォークの開始頂点が s に従って選択され、次に pr(α, s ) は、このプロセスで各頂点に到達する確率を記述する。
0.85
pr(α, s) = αs + (1 − α)pr(α, s)W, pr(α, s) = αs + (1 − α)pr(α, s)w である。 0.92
Computing an exact Pagerank vector pr(α, χv) is equivalent to computing the stationary distribution of a Markov chain on the vertex set V which has a time complexity of Ω(n). 正確なページランクベクトル pr(α, sv) の計算は、 Ω(n) の時間複雑性を持つ頂点集合 V 上のマルコフ鎖の定常分布を計算することと等価である。 0.82
However, since the probability mass of a personalised Pagerank vector is concentrated around some starting vertex, it is possible to compute a good approximation of the Pagerank vector in a local way. しかし、パーソナライズされたページランクベクトルの確率質量はいくつかの開始頂点の周りに集中しているため、局所的にページランクベクトルのよい近似を計算することができる。
訳抜け防止モード: しかし、パーソナライズされたページランクベクトルの確率質量はいくつかの開始頂点の周りに集中している。 Pagerankベクトルのよい近似を局所的に計算することができる。
0.78
Andersen et al [4] introduced the approximate Pagerank, which will be used in our analysis. Andersen et al [4] は、我々の分析で使用される近似した Pagerank を導入した。 0.77
Definition 1. A vector p = apr(α, s, r) is an approximate Pagerank vector if p + pr(α, r) = pr(α, s). 定義1。 ベクトル p = apr(α, s, r) が近似ページランクベクトルであるとは、p + pr(α, r) = pr(α, s) が成り立つことである。 0.79
The vector r is called the residual vector. ベクトル r は残留ベクトルと呼ばれる。 0.76
The evolving set process. 進化するセットプロセス。 0.68
The evolving set process (ESP) is a Markov chain whose states are sets of vertices Si ⊆ V . 進化的集合過程 (ESP) はマルコフ連鎖であり、状態はSi > V の頂点の集合である。 0.71
Given a state Si, the next state Si+1 is determined by the following process: (1) choose t ∈ [0, 1] (cid:124) uniformly at random; (2) let Si+1 = {v ∈ V |χvW χ ≥ t}. 状態 Si が与えられたとき、次の状態 Si+1 は次のプロセスによって決定される: (1) t ∈ [0, 1] (cid:124) をランダムに一様に選ぶ; (2) Si+1 = {v ∈ V |\vW > ≥ t} とする。 0.83
The volume-biased ESP is a variant used to ensure that the Markov chain absorbs in the state V rather than ∅. 体積バイアス ESP は、マルコフ連鎖が s ではなく状態 V に吸収されることを保証する変種である。 0.76
Andersen and Peres [2] gave a local Si algorithm for undirected graph clustering using the volume-biased ESP. Andersen と Peres [2] は、ボリュームバイアス ESP を用いた非方向グラフクラスタリングのための局所Siアルゴリズムを与えた。 0.69
In particular, they gave an algorithm GenerateSample(u, T ) which samples the T -th element from the volume-biased ESP with S0 = {u}. 特に彼らは、体積バイアスESPからT-要素をS0 = {u} でサンプリングするGenerateSample(u, T )アルゴリズムを与えた。 0.68
3 The Algorithm for Undirected Graphs 3 非向グラフのアルゴリズム 0.74
Now we present a local algorithm for finding two clusters in an undirected graph with a dense cut between them. ここでは,2つのクラスタを,その間に密閉した非方向グラフで探索する局所アルゴリズムを提案する。 0.71
To formalise this notion, for any undirected graph G = (V, E) and disjoint L, R ⊂ V , we follow Trevisan [27] and define the bipartiteness ratio この概念を定式化するには、任意の非直交グラフ G = (V, E) および非随伴 L, R , V に対して、トレビサン[27] に従い、二部比を定義する。 0.66
β(L, R) (cid:44) 1 − 2e(L, R) vol(L ∪ R) β(L, R) (cid:44) 1 − 2e(L, R) vol(L, R) 0.95
. Notice that a low β(L, R) value means that there is a dense cut between L and R, and there is a sparse cut between L∪ R and V \ (L∪ R). . 低β(L, R) の値は、L と R の間に密度の高い切断が存在し、L と V の間には疎切断が存在することを意味する。
訳抜け防止モード: . 低い β(L, R ) の値がそれを意味することに注意。 L と R の間には密接な切断がある。 そして、L と V の間にスパースカット(L と R )がある。
0.83
In particular, β(L, R) = 0 implies that (L, R) forms a bipartite and connected component of G. We will describe a local algorithm for finding almost-bipartite sets L and R with a low value of β(L, R). 特に、β(L, R) = 0 は、(L, R) が G の二部および連結成分となることを意味する。
訳抜け防止モード: 特に、β(L, R ) = 0 は、(L, R ) が G の双部および連結成分となることを意味する。 Rはβ(L, R) の低い値である。
0.58
3.1 The Reduction by Double Cover The design of most local algorithms for finding a target set S ⊂ V of low conductance is based on analysing the behaviour of random walks starting from vertices in S. In particular, when the conductance ΦG(S) is low, a random walk starting from most vertices in S will leave S with low probability. 3.1 コンダクタンス φg(s) が低ければ、s のほとんどの頂点から開始されるランダムウォークの挙動を分析することにより、低コンダクタンスの目標集合 s 〜 v を求めるためのほとんどの局所アルゴリズムの設計を二重カバーする。
訳抜け防止モード: 3.1 二重化による削減は、ほとんどの局所アルゴリズムの設計をカバーする 低コンダクタンスの目標集合s,vを見つける 特にsの頂点から始まっているランダムウォークの挙動の分析に基づいています コンダクタンス φg(s ) が低ければ、s 内のほとんどの頂点から始まるランダムウォークは、s を低確率で残す。
0.72
However, for our setting, the しかし、私たちの設定では、 0.76
3 3 0.85
英語(論文から抽出)日本語訳スコア
target is a pair of sets L, R with many connections between them. 対象は、その間に多くの接続を持つ集合 L, R の対である。 0.72
As such, a random walk starting in either L or R is very likely to leave the starting set. したがって、L または R のいずれかから始まるランダムウォークは、開始集合を離れる可能性が非常に高い。 0.72
To address this, we introduce a novel technique based on the double cover of G to reduce the problem of finding two sets of high conductance to the problem of finding one of low conductance. そこで本研究では,Gの二重被覆に基づく新しい手法を導入し,低コンダクタンスの2つの高コンダクタンスの集合を見つける問題と低コンダクタンスの1つを見つける問題を減らす。 0.79
Formally, for any undirected graph G = (VG, EG), its double cover is the bipartite graph H = (VH , EH ) defined as follows: (1) every vertex v ∈ VG has two corresponding vertices v1, v2 ∈ VH; (2) for every edge {u, v} ∈ EG, there are edges {u1, v2} and {u2, v1} in EH. 形式的には、任意の無向グラフ G = (VG, EG) に対して、その二重被覆は二部グラフ H = (VH , EH ) と定義される: (1) すべての頂点 v ∈ VG は二つの対応する頂点 v1, v2 ∈ VH; (2) すべての辺 {u, v} ∈ EG に対して、EH に辺 {u1, v2} と {u2, v1} が存在する。 0.82
See Figure 2 for an illustration. a c 図2を参照。 あ c 0.61
b d =⇒ a1 a2 b d =⇒ a1 a2 0.81
b1 b2 c1 c2 b1 b2 c1 c2 0.78
d1 d2 Figure 2: An example of the construction of the double cover. d1 d2 図2: 二重被覆の構成例。 0.70
Now we present a tight connection between the value of β(L, R) for any disjoint sets L, R ⊂ VG and the conductance of a single set in the double cover of G. To this end, for any S ⊂ VG, we define S1 ⊂ VH and S2 ⊂ VH by S1 (cid:44) {v1 | v ∈ S} and S2 (cid:44) {v2 | v ∈ S}. このとき、G の二重被覆における一組のコンダクタンスと任意の解集合 L に対する β(L, R) の値と、G の双対被覆における単集合のコンダクタンスとの間の密接な接続を提示する。このために、任意の S > VG に対して、S1 (cid:44) {v1 | v ∈ S} と S2 (cid:44) {v2 | v ∈ S} によって S1 > VH と S2 > VH を定義する。 0.73
We formalise the connection in the following lemma. 次の補題で接続を形式化します。 0.61
Lemma 1. Let G be an undirected graph, S ⊂ V with partitioning (L, R), and H be the double cover of G. Then, it holds that ΦH (L1 ∪ R2) = βG(L, R). レマ1号。 G を非直交グラフとし、分割 (L, R) を持つ S を V とし、H を G の二重被覆とする。
訳抜け防止モード: レマ1号。 G を非直交グラフとし、分割 (L, V) を付す。 R) と H は G の二重被覆である。 L1 > R2 ) = βG(L, ) である。 R)。
0.65
Next we look at the other direction of this correspondence. 次に、この対応の別の方向を見てみよう。 0.63
Specifically, given any S ⊂ VH in the double cover of a graph G, we would like to find two disjoint sets L ⊂ VG and R ⊂ VG such that βG(L, R) = ΦH (S). 具体的には、グラフ G の二重被覆の任意の S > VH が与えられたとき、βG(L, R) = > H(S) となるような二つの非連結集合 L > VG と R > VG を求める。 0.75
However, such a connection does not hold in general. しかし、そのような接続は一般には成り立たない。 0.75
To overcome this, we restrict our attention to those subsets of VH which can be unambiguously interpreted as two disjoint sets in VG. これを解決するために、VG 内の2つの非随伴集合として曖昧に解釈できる VH の部分集合に注意を限定する。 0.68
Definition 2. We call S ⊂ VH simple if |{v1, v2} ∩ S| ≤ 1 holds for all v ∈ VG. 定義2。 すべての v ∈ VG に対して |{v1, v2} > S| ≤ 1 が成立すると、S は単純である。 0.75
Lemma 2. For any simple set S ⊂ VH, let L = {u : u1 ∈ S} and R = {u : u2 ∈ S}. レマ2号。 任意の単純集合 S に対して、L = {u : u1 ∈ S} と R = {u : u2 ∈ S} とする。 0.72
Then, βG(L, R) = ΦH (S). そして、βG(L, R) = >H(S) となる。 0.74
3.2 Design of the Algorithm So far we have shown that the problem of finding densely connected sets L, R ⊂ VG can be reduced to finding S ⊂ VH of low conductance in the double cover H, and this reduction raises the natural question of whether existing local algorithms can be directly employed to find L and R in G. However, this is not the case: even though a set S ⊂ VH returned by most local algorithms is guaranteed to have low conductance, vertices of G could be included in S twice, and as such S will not necessarily give us disjoint sets L, R ⊂ VG with low value of β(L, R). 3.2 Design of the Algorithm So far we have shown that the problem of finding densely connected sets L, R ⊂ VG can be reduced to finding S ⊂ VH of low conductance in the double cover H, and this reduction raises the natural question of whether existing local algorithms can be directly employed to find L and R in G. However, this is not the case: even though a set S ⊂ VH returned by most local algorithms is guaranteed to have low conductance, vertices of G could be included in S twice, and as such S will not necessarily give us disjoint sets L, R ⊂ VG with low value of β(L, R). 0.89
See Figure 3 for an illustration. ··· 図3を参照。 ··· 0.52
S ··· a1 a2 S ··· a1 a2 0.75
b1 b2 c1 c2 b1 b2 c1 c2 0.78
d1 d2 e1 e2 d1 d2 e1 e2 0.78
f1 f2 ··· ··· f1 f2 ··· ··· 0.69
Figure 3: The indicated vertex set S ⊂ VH has low conductance. 図3: 示される頂点集合 S: VH は導電率が低い。 0.81
However, since S contains many pairs of vertices which correspond to the same vertex in G, S gives us little information for finding disjoint L, R ⊂ VG with a low β(L, R) value. しかし、S には G の同じ頂点に対応する頂点の対が多数含まれているため、S は β(L, R) の値が低い不随伴 L, R, VG を見つけるための情報はほとんど得られない。 0.77
The simplify operator. To take the example shown in Figure 3 into account, our objective is to design a local algorithm for finding some set S ⊂ VH of low conductance which is also simple. 簡単なオペレータ。 図3に示す例を考慮に入れるために、我々の目標は低コンダクタンスの集合 s s vh を見つけるための局所アルゴリズムの設計であり、これも単純である。 0.71
To ensure this, we introduce the simplify operator, and analyse its properties. これを保証するため、簡易演算子を導入し、その特性を分析する。 0.69
Definition 3 (Simplify operator). 定義3(Simplify operator)。 0.74
Let H be the double cover of G, where the two corresponding vertices of any u ∈ VG are defined as u1, u2 ∈ VH. H を G の二重被覆とし、任意の u ∈ VG の二つの対応する頂点を u1, u2 ∈ VH と定義する。 0.86
Then, for any p ∈ R2n≥0, the simplify operator is a function σ : R2n≥0 → R2n≥0 このとき、任意の p ∈ R2n≥0 に対して、簡約作用素は σ : R2n≥0 → R2n≥0 である。 0.56
4 4 0.85
英語(論文から抽出)日本語訳スコア
defined by for every u ∈ VG. 定義する すべての u ∈ VG に対して。 0.73
(σ ◦ p)(u1) (cid:44) max(0, p(u1) − p(u2)), (σ ◦ p)(u2) (cid:44) max(0, p(u2) − p(u1)) (cid:44) max(0, p(u1) − p(u2)、(σ ) p)(u2) (cid:44) max(0, p(u2) − p(u1)) 0.83
Notice that, for any vector p and any u ∈ VG, at most one of u1 and u2 is in the support of σ ◦ p; hence, the support of σ ◦ p is always simple. 任意のベクトル p と任意の u ∈ VG に対して、u1 と u2 の少なくとも一方は σ > p の支持であるので、σ > p の支持は常に単純である。 0.79
To explain the meaning of σ, for a vector p one could view p(u1) as our “confidence” that u ∈ L, and p(u2) as our “confidence” that u ∈ R. Hence, when p(u1) ≈ p(u2), both (σ ◦ p)(u1) and (σ ◦ p)(u2) are small which captures the fact that we would not prefer to include u in either L or R. On the other hand, when p(u1) (cid:29) p(u2), we have (σ ◦ p)(u1) ≈ p(u1), which captures our confidence that u should belong to L. The following lemma summaries some key properties of σ. σ の意味を説明するために、ベクトル p に対して、p(u1) を u ∈ l と p(u2) を u ∈ r の「信頼」と見なすことができるので、p(u1) と p(u2) の両方が小さいとき、p(u2) は l または r に u を含むことを好まないという事実を捉える。
訳抜け防止モード: σ の意味を説明するために、ベクトル p に対して p(u1 ) を我々の「信頼」とみなすことができる。 u ∈ L, そして p(u2 ) が u ∈ R. Hence の「信頼」である。 p(u1 ) > p(u2 ) ならば、( σ ) p)(u1 ) と ( σ ) p)(u2 ) はともに小さく、L または R に u を含まないという事実を捉えている。 p(u1 ) ( cid:29 ) p(u2 ) とすると、(σ ) p)(u1 ) > p(u1 ) となる。 以下の補題は σ のいくつかの重要な性質をまとめたものである。
0.83
Lemma 3. The following holds for the σ-operator: 第3弾。 σ-operator は以下のようになる。 0.63
• σ ◦ (c · p) = c · (σ ◦ p) for p ∈ R2n≥0 and any c ∈ R≥0; • σ ◦ (a + b) (cid:22) σ ◦ a + σ ◦ b for a, b ∈ R2n≥0; • σ ◦ (pW ) (cid:22) (σ ◦ p)W for p ∈ R2n≥0. p ∈ r2n≥0 と任意の c ∈ r≥0 に対する σ (c · p) = c · (σ > p) と、a ∈ r2n≥0 に対する σ (a + b) (cid:22) σ (a + b) σ (a + σ ) b に対し、b ∈ r2n≥0; • σ (pw ) (cid:22) は p ∈ r2n≥0 に対して成立する。 0.75
While these three properties will all be used in our analysis, the third is of particular importance: it implies that, if p is the probability distribution of a random walk in H, applying σ before taking a one-step random walk would never result in lower probability mass than applying σ after taking a one-step random walk. これは、p が H におけるランダムウォークの確率分布であるなら、一段階のランダムウォークの前に σ を適用することは、1段階のランダムウォークを行った後に σ を適用するよりも低い確率質量をもたらすことはないことを意味する。
訳抜け防止モード: これら3つの性質はすべて分析に使用されるが、3つ目は特に重要である。 すなわち、p が H におけるランダムウォークの確率分布であるなら、 1歩歩く前にσを適用する - ステップランダムウォーク 確率の質量は 1歩歩いた後にσを適用する。
0.81
This means that no probability mass would be lost when the σ-operator is applied between every step of a random walk, in comparison with applying σ at the end of an entire random walk process. これは、σ-演算子をランダムウォークの各ステップ間で適用した場合、ランダムウォークプロセスの最後にσを適用する場合と比較して、確率質量は失われないことを意味する。 0.72
Description of the algorithm. アルゴリズムの説明。 0.58
Our proposed algorithm is conceptually simple: every vertex u of the input graph G maintains two copies u1, u2 of itself, and these two “virtual” vertices are used to simulate u’s corresponding vertices in the double cover H of G. Then, as the neighbours of u1 and u2 in H are entirely determined by u’s neighbours in G and can be constructed locally, a random walk process in H will be simulated in G. This will allow us to apply a local algorithm similar to the one by Anderson et al [4] on this “virtual” graph H. Finally, since all the required information about u1, u2 ∈ VH is maintained by u ∈ VG, the σ-operator will be applied locally. Our proposed algorithm is conceptually simple: every vertex u of the input graph G maintains two copies u1, u2 of itself, and these two “virtual” vertices are used to simulate u’s corresponding vertices in the double cover H of G. Then, as the neighbours of u1 and u2 in H are entirely determined by u’s neighbours in G and can be constructed locally, a random walk process in H will be simulated in G. This will allow us to apply a local algorithm similar to the one by Anderson et al [4] on this “virtual” graph H. Finally, since all the required information about u1, u2 ∈ VH is maintained by u ∈ VG, the σ-operator will be applied locally. 0.92
The formal description of our algorithm is given in Algorithm 1, which invokes Algorithm 2 as the key component to compute aprH (α, χu1, r). このアルゴリズムの形式的記述はアルゴリズム1で与えられ、アルゴリズム2を aprh (α, ]u1, r) を計算する鍵成分として呼び出す。 0.84
Specifically, Algorithm 2 maintains, for every vertex u ∈ G, tuples (p(u1), p(u2)) and (r(u1), r(u2)) to keep track of the values of p and r in G’s double cover. 具体的には、アルゴリズム2はすべての頂点 u ∈ G に対して、G の二重被覆における p と r の値を追跡するためにタプル (p(u1, p(u2)) と (r(u1, r(u2)) を維持する。 0.86
For a given vertex u, the entries in these tuples are expressed by p1(u), p2(u), r1(u), and r2(u) respectively. 与えられた頂点 u に対して、これらのタプルのエントリはそれぞれ p1(u)、p2(u)、r1(u)、r2(u) で表される。 0.69
Every dcpush operation (Algorithm 3) preserves the invariant p + prH (α, r) = prH (α, χv1), which ensures that the final output of Algorithm 2 is an approximate Pagerank vector. すべての dcpush 演算 (Algorithm 3) は不変 p + prH (α, r) = prH (α, sv1) を保持し、アルゴリズム2の最終出力が近似ページランクベクトルであることを保証する。 0.83
We remark that, although the presentation of the ApproximatePagerankD C procedure is similar to the one in Andersen et al [4], in our dcpush procedure the update of the residual vector r is slightly more involved: specifically, for every vertex u ∈ VG, both r1(u) and r2(u) are needed in order to update r1(u) (or r2(u)). ApproximatePagerankD C プロシージャのプレゼンテーションは Andersen et al [4] のプレゼンテーションと似ているが、我々の dcpush プロシージャでは、残余ベクトル r の更新はもう少し複雑である:具体的には、すべての頂点 u ∈ VG に対して r1(u) と r2(u) は r1(u) または r2(u)) を更新するために必要である。 0.78
That is one of the reasons that the performance of the algorithm in Andersen et al [4] cannot be directly applied for our algorithm, and a more technical analysis, some of which is parallel to theirs, is needed in order to analyse the correctness and performance of our algorithm. andersen et al[4]におけるアルゴリズムの性能が直接アルゴリズムに適用できない理由の一つであり、アルゴリズムの正確性と性能を分析するためには、それらのアルゴリズムと並行する技術分析が必要である。
訳抜け防止モード: これは,Andersen et al [ 4 ] におけるアルゴリズムの性能が,我々のアルゴリズムに直接適用できない理由の1つである。 技術的な分析も行います いくつかは彼らのものと平行しています 順番に必要です アルゴリズムの正しさと性能を分析します
0.86
3.3 Analysis of the Algorithm To prove the correctness of our algorithm, we will show two complementary facts which we state informally here: 3.3 アルゴリズムの分析 アルゴリズムの正しさを証明するために、ここで非公式に述べる2つの補完的な事実を示す。 0.76
1. If there is a simple set S ⊂ VH with low conductance, then for most u1 ∈ S, the simplified approximate 1. 低コンダクタンスを持つ単純集合 S > VH が存在するなら、ほとんどの u1 ∈ S に対して、単純化された近似が成立する。
訳抜け防止モード: 1. 低コンダクタンスな簡単な集合 s , vh が存在する場合 すると、ほとんどの u1 ∈ s に対して、単純近似は
0.79
Pagerank vector p = σ ◦ apr(α, χu1, r) will have a lot of probability mass on a small set of vertices. ページランクベクトル p = σ > apr(α, su1, r) は、小さな頂点の集合上で多くの確率質量を持つ。 0.73
2. If p = σ ◦ apr(α, χu1, r) contains a lot of probability mass on some small set of vertices, then there is a 2. p = σ > apr(α, su1, r) がいくつかの小さな頂点集合上に多くの確率質量を持つなら、a が存在する。 0.83
sweep set of p with low conductance. 導電率の低いpのスイープセット。 0.59
5 5 0.85
英語(論文から抽出)日本語訳スコア
Algorithm 1: LocBipartDC アルゴリズム1: LocBipartDC 0.71
20γ 378, and  = 1 20γ 378, および s = 1 0.79
Input: A graph G, starting vertex u, target volume γ, and target bipartiteness β Output: Two disjoint sets L and R Set α = β2 Compute p(cid:48) = ApproximatePagerankD C(u, α, ) Compute p = σ ◦ p(cid:48) for j ∈ [1,|supp(p)|] do j ) ≤ β then Set L = {u : u1 ∈ Sp return (L, R) 入力: グラフ G, start vertex u, target volume γ, and target bipartiteness β 出力: 2つの非結合集合 L と R をセット α = β2 Compute p(cid:48) = ApproximatePagerankD C(u, α, ) Compute p = σ p(cid:48) for j ∈ [1,|supp(p)|] do j ) ≤ β とし、L = {u : u1 ∈ Sp return (L, R) をセットする。 0.92
j }, and R = {u : u2 ∈ Sp j } j }, そして R = {u : u2 ∈ Sp j } 0.84
if Φ(Sp もし が(Sp) なら 0.62
end if end for Algorithm 2: ApproximatePagerankD C 終われば終われば アルゴリズム2:近似pagerankdc 0.68
Input: Starting vertex v, parameters α and  Output: Approximate Pagerank vector aprH (α, χv1, r) Set p1 = p2 = r2 = 0; set r1 = χv while max(u,i)∈V ×{1,2} ri(u) 入力: vertex v, パラメータ α と ~ 出力: Approximate Pagerank vector aprH (α, sv1, r) Set p1 = p2 = r2 = 0; set r1 = shv while max(u,i)~V ×{1,2} ri(u) 0.91
deg(u) ≥  do deg(u) ≥ ~ do 0.80
Choose any u and i ∈ {1, 2} such that ri(u) deg(u) ≥  (p1, p2, r1, r2) = dcpush(α, (u, i), p1, p2, r1, r2) u と i ∈ {1, 2} を選択して ri(u) deg(u) ≥ (p1, p2, r1, r2) = dcpush(α, (u, i), p1, p2, r1, r2) とする。 0.95
end while return p = [p1, p2] end while return p = [p1, p2] 1.00
As we have shown in Section 3.1, there is a direct correspondence between almost-bipartite sets in G, and low-conductance and simple sets in H. This means that the two facts above are exactly what we need to prove that Algorithm 1 can find densely connected sets in G. We will first show in Lemma 4 how the σ-operator affects some standard mixing properties of Pagerank vectors in order to establish the first fact promised above. 第3.1節で示したように、g のほぼ二成分集合と h の低コンダクタンスおよび単純集合の間には直接対応がある。これは、上記の2つの事実が、アルゴリズム 1 が g で密結合な集合を見つけることを証明するのにちょうど必要であることを意味する。
訳抜け防止モード: 第3.1節で示したように、g のほぼ二部集合の間には直接対応がある。 これは、上記の2つの事実が、アルゴリズム 1 が g で密に連結された集合を見つけることができることを証明するために、まさにそれであることを意味する。 lemma 4 において、σ - 作用素がページランクベクトルの標準的な混合特性にどのように影響するかを最初に示す。
0.71
This lemma relies on the fact that S ⊂ VG corresponds to a simple set in VH. この補題は、S > VG が VH の単純集合に対応するという事実に依存している。
訳抜け防止モード: この補題は事実に依存している S > VG は VH の単純集合に対応する。
0.83
This allows us to apply the σ-operator to the approximate Pagerank vector aprH (α, χu1, r) while preserving a large probability mass on the target set. これにより、σ-operator は、ターゲット集合上の大きな確率質量を保ちながら、近似した Pagerank ベクトル aprH (α, su1, r) に適用することができる。 0.73
Lemma 4. For any set S ⊂ VG with partitioning (L, R) and any constant α ∈ [0, 1], there is a subset Sα ⊆ S with vol(Sα) ≥ vol(S)/2 such that, for any vertex v ∈ Sα, the simplified approximate Pagerank on the double cover p = σ ◦ (aprH (α, χv1, r)) satisfies 第4回。 分割 (L, R) と任意の定数 α ∈ [0, 1] を持つ任意の集合 S と V(Sα) ≥ vol(S)/2 を持つ部分集合 Sα が存在して、任意の頂点 v ∈ Sα に対して、二重被覆 p = σ (aprH (α, sv1, r))) 上の単純化された近似ページランクが満足する。 0.69
p(L1 ∪ R2) ≥ 1 − 2β(L, R) p(L1 > R2) ≥ 1 − 2β(L, R) 0.97
α − 2vol(S) max u∈V α − 2vol(S) max u・V 0.80
r(u) deg(u) r(u) deg(u) 0.85
. To prove the second fact, we show as an intermediate lemma that the value of p(u1) can be bounded with . 2つ目の事実を証明するために、p(u1) の値が有界であることを中間補題として示す。 0.74
respect to its value after taking a step of the random walk: pW (u1). ランダムウォークのステップを踏んだ後の値について: pW (u1)。 0.70
Lemma 5. Let G be a graph with double cover H, and apr(α, s, r) be the approximate Pagerank vector defined with respect to H. Then, p = σ ◦ (apr(α, s, r)) satisfies that p(u1) ≤ α (s(u1) + r(u2)) + (1 − α)(pW )(u1), and p(u2) ≤ α (s(u2) + r(u1)) + (1 − α)(pW )(u2) for any u ∈ VG. 第5回。 G を二重被覆 H のグラフとし、apr(α, s, r) を H に関して定義される近似ページランクベクトルとすると、p = σ (apr(α, s, r)) は任意の u ∈ VG に対して p(u1) ≤ α (s(u1) + r(u2)) + (1 − α)(pW )(u1) かつ p(u2) ≤ α (s(u2) + r(u1)) + (1 − α)(pW )(u2) を満たす。 0.72
Notice that applying the σ-operator for any vertex u1 introduces a new dependency on the value of the residual vector r at u2. 任意の頂点 u1 に対して σ-operator を適用すると、u2 における残留ベクトル r の値に新しい依存が生じることに注意。 0.71
This subtle observation demonstrates the additional complexity introduced by the σ-operator when compared with previous analysis of Pagerank-based local algorithms [4]. この微妙な観察は、Pagerankベースの局所アルゴリズムの以前の分析と比較すると、σ-operatorによってもたらされた複雑さを示す[4]。 0.63
Taking account of the σ-operator, we further analyse the Lov´asz-Simonovits curve defined by p, which is a common technique in the analysis of random walks on graphs [17]: we show that if there is a set S with a large value of p(S), there must be a sweep set Sp これはグラフ上のランダムウォークの解析において一般的な手法である [17] により定義される Lov ́asz-Simonovits 曲線を更に解析する: p(S) の値が大きい集合 S が存在するなら、スイープ集合 Sp が存在しなければならないことを示す。 0.82
j with small conductance. コンダクタンスが小さいjです 0.53
6 6 0.85
英語(論文から抽出)日本語訳スコア
Algorithm 3: dcpush Input: α, (u, i), p1, p2, r1, r2 1, p(cid:48) Output: (p(cid:48) 1, r(cid:48) 2, r(cid:48) 2) 1, p(cid:48) Set (p(cid:48) 1, r(cid:48) 2, r(cid:48) 2) = (p1, p2, r1, r2) Set p(cid:48) i(u) = pi(u) + αri(u); r(cid:48) for v ∈ NG(u) do 3−i(v) = r3−i(v) + (1 − α) ri(u) 1, p(cid:48) アルゴリズム3: dcpush Input: α, (u, i), p1, p2, r1, r2 1, p(cid:48) Output: (p(cid:48) 1, r(cid:48) 2, r(cid:48) Set (p(cid:48) 1, r(cid:48) 2, r(cid:48) 2) = (p1, p2, r1, r2) Set p(cid:48) i(u) = pi(u) + αri(u); r(cid:48) for v ∈ NG(u) do 3−i(v) = r3−i(v) + (1 − α) ri(u) 1, p(cid:48) 1, p(cid:48) 0.95
Set r(cid:48) end for return (p(cid:48) set r(cid:48) end for return (p(cid:48) 0.90
1, r(cid:48) 2) 1, r(cid:48) 2) 0.96
2, r(cid:48) 2 r(cid:48) 0.91
2 deg(u) i(u) = (1 − α) ri(u) 2 deg(u) i(u) = (1 − α) ri(u) 0.85
2 Lemma 6. Let G be a graph with double cover H, and let p = σ◦(aprH (α, s, r)) such that maxu∈VH If there is a set of vertices S ⊂ VH and a constant δ such that p(S) − vol(S) j ∈ [1,|supp(p)|] such that ΦH (Sp 2 第6回。 G を二重被覆 H のグラフとし、p = σ (aprH (α, s, r)) を極大 VH とし、p(S) − vol(S) j ∈ [1,|supp(p)|] となるような頂点の集合 S(S) − vol(S) j ∈ [1,|supp(p)|) が存在するとする。 0.77
d(u) ≤ . d(u) ≤ である。 0.85
vol(VH ) ≥ δ, then there is some vol(vh ) ≥ δ ならば、いくつか存在する 0.82
(1 + vol(S))α ln( 4 (1 + )vol(s))α ln(4) 0.87
(cid:113) δ )(cid:14)δ. (cid:113) δ (cid:14)δ。 0.83
j ) < 6 r(u) j) < 6 r(u) 0.84
We have now shown the two facts promised at the beginning of this subsection. 現在、この節の冒頭で約束した2つの事実を示しています。 0.58
Putting these together, if there is a simple set S ⊂ VH with low conductance then we can find a sweep set of σ ◦ apr(α, s, r) with low conductance. これらを組み合わせると、低コンダクタンスを持つ単純な集合 s, vh が存在して、低コンダクタンスを持つ σ, apr(α, s, r) のスイープ集合を見つけることができる。 0.68
By the reduction from almost-bipartite sets in G to low-conductance simple sets in H our target set corresponds to a simple set S ⊂ VH which leads to Algorithm 1 for finding almost-bipartite sets. G の概二部集合から H の低導電性単純集合への還元により、対象集合は単純集合 S > VH に対応し、ほぼ二部集合を見つけるアルゴリズム 1 に繋がる。 0.77
Our result is summarised as follows. 我々の結果は以下の通り要約される。 0.67
Theorem 1. Let G be an n-vertex undirected graph, and L, R ⊂ VG be disjoint sets such that β(L, R) ≤ β and vol(L ∪ R) ≤ γ. 理論1。 G を n-頂点無向グラフとし、L, R , VG を β(L, R) ≤ β と vol(L, R) ≤ γ を満たすような非随伴集合とする。 0.75
Then, there is a set C ⊆ L ∪ R with vol(C) ≥ vol(L ∪ R)/2 such that, for any v ∈ C, すると、任意の v ∈ C に対して vol(C) ≥ vol(L ) R)/2 となるような集合 C は、Vol(C) ≥ vol(L ) R)/2 である。 0.72
LocBipartDC(cid:0)G, v, γ, Moreover, the algorithm has running time O(cid:0)β−1γ log n(cid:1). locbipartdc(cid:0)g, v, γ, さらにアルゴリズムは実行時間o(cid:0)β−1γ log n(cid:1)を持つ。 0.81
For any  ∈ [0, 1/2], their algorithm runs in time O(cid:0)2β−2γ1+ log3 γ(cid:1) and returns a set with volume O(cid:0)γ1+(cid:1) to guarantee the same bipartiteness ratio O(cid:0)√ 任意の | ∈ [0, 1/2] に対して、それらのアルゴリズムは o(cid:0)/2β−2γ1+> log3 γ(cid:1) で実行され、体積 o(cid:0)γ1+>(cid:1) を持つ集合を返して同じ二成分比 o(cid:0) を保証する。 0.64
The quadratic approximation guarantee in Theorem 1 matches the state-of-the-art local algorithm for finding a single set with low conductance [5]. Theorem 1の二次近似保証は、低コンダクタンス[5]の単一集合を見つけるための最先端の局所アルゴリズムと一致する。 0.78
Furthermore, our result presents a significant improvement over the previous state-of-the-art by Li and Peng [15], whose design is based on an entirely different technique than ours. さらに,Li と Peng [15] による従来の最先端技術よりも大幅に改善され,その設計は我々のものとは全く異なる技術に基づいている。 0.76
7560β(cid:1) returns (L(cid:48), R(cid:48)) with β(L(cid:48), R(cid:48)) = O(cid:0)√ 7560β(cid:48), R(cid:48)) を β(L(cid:48), R(cid:48)) = O(cid:0) で返す。 0.89
β(cid:1) and vol(L(cid:48) ∪ R(cid:48)) = O(cid:0)β−1γ(cid:1). β(cid:1) および vol(L(cid:48) ) R(cid:48)) = O(cid:0)β−1γ(cid:1)。 0.77
. In particular, their algorithm requires much higher time complexity in order . 特に、彼らのアルゴリズムは順番にはるかに高い時間を要する 0.77
(cid:16)(cid:112)β/ (cid:17) (cid:16)(cid:112)β/>(cid:17) 0.66
and bipartiteness ratio O and bipartiteness ratio O 0.85
β(cid:1). √ β (cid:1。 √ 0.86
4 The Algorithm for Digraphs 4 ダイアグラムのアルゴリズム 0.56
We now turn our attention to local algorithms for finding densely-connected clusters in digraphs. 現在では、ダイグラフ内の密結合クラスタを見つけるためのローカルアルゴリズムに注意を向けています。 0.57
In comparison with undirected graphs, we are interested in finding disjoint L, R ⊂ V of some digraph G = (V, E) such that most of the edges adjacent to L ∪ R are from L to R. To formalise this, we define the flow ratio from L to R as 直交しないグラフと比較して、あるグラフ G = (V, E) の解離 L, R, V を L から R へ直交する辺のほとんどを L から R へ向けることに興味がある。
訳抜け防止モード: 非直交グラフと比較して、不随伴 L, ある図形の G = ( V, E ) {\displaystyle G=(V,E)} の R > V である。 L > R に隣接する辺のほとんどは L から R へのものである。 L から R への流量比を
0.79
F (L, R) (cid:44) 1 − F (L, R) (cid:44) 1 − 0.99
2e(L, R) volout(L) + volin(R) 2e(L, R) volout (複数形 volouts) 0.67
, where e(L, R) is the number of directed edges from L to R. Notice that we take not only edge densities but also edge directions into account: a low F (L, R)-value tells us that almost all edges with their tail in L have their head in R, and conversely almost all edges with their head in R have their tail in L. One could also see F (L, R) as a generalisation of β(L, R). , ここで e(L, R) は L から R への有向エッジの数である: 辺密度だけでなく、辺方向も考慮する: 低い F (L, R)-値は、L の尾を持つほとんどすべての辺が R の頭を持ち、逆に R の頭のほとんどすべての辺は L の尾を持つ。
訳抜け防止モード: , ここで e(L, R) は L から R への有向エッジの数である。 エッジ密度だけでなく、エッジ方向も考慮しなければなりません。 F (L, R) 値の低い値がそれを教えてくれる。 L の尾を持つほぼすべての辺は、R の頭を持つ。 逆に、R の頭部のほとんどすべての辺は L の尾を持つ。また F ( L, R ) を β(L, R ) の一般化と見なすこともできる。
0.85
In particular, if we view an undirected graph as a digraph by replacing each edge with two directed edges, then β(L, R) = F (L, R). 特に、各辺を2つの有向辺に置き換えることで、無向グラフをグラフとして見るなら、β(L, R) = F(L, R) である。
訳抜け防止モード: 特に、各辺を2つの有向エッジに置き換えることで、無向グラフをグラフとして見る場合。 すると β(L, R ) = F ( L, R ) となる。
0.80
In this section, we will present a local algorithm for finding such vertex sets in a digraph, and analyse the algorithm’s performance. 本稿では,そのような頂点集合をダイアグラフで探索する局所アルゴリズムを示し,そのアルゴリズムの性能を分析する。 0.78
4.1 The Reduction by Semi-Double Cover Given a digraph G = (VG, EG), we construct its semi-double cover H = (VH , EH ) as follows: (1) every vertex v ∈ VG has two corresponding vertices v1, v2 ∈ VH; (2) for every edge (u, v) ∈ EG, we add the edge {u1, v2} 4.1 半二重被覆による削減 G = (VG, EG) が与えられたとき、その半二重被覆 H = (VH , EH ) を構成する: (1) すべての頂点 v ∈ VG は二つの対応する頂点 v1, v2 ∈ VH; (2) すべての辺 (u, v) ∈ EG に対して、エッジ {u1, v2} を加える。 0.83
7 7 0.85
英語(論文から抽出)日本語訳スコア
in EH, see Figure 4 for illustration. EH では図 4 を例示します。 0.75
1 It is worth comparing this reduction with the one for undirected graphs: 第一に、この削減を無向グラフと比較する価値がある。 0.74
• For undirected graphs, we apply the standard double cover and every undirected edge in G corresponds • 無向グラフの場合、標準二重被覆を適用すると、g のすべての無向辺は対応する。
訳抜け防止モード: •無向グラフの場合、標準二重被覆を適用する g の任意の無向辺は
0.81
to two edges in the double cover H; 二重被覆 h の2つの辺へ; 0.74
• For digraphs, every directed edge in G corresponds to one undirected edge in H. This asymmetry would • 図形の場合、G のすべての有向エッジは H の1つの無向エッジに対応する。 0.78
allow us to “recover” the direction of any edge in G. g の任意の辺の方向を “再被覆” できるようにします。 0.69
a c b d =⇒ あ c b d =⇒ 0.77
a1 a2 b1 b2 a1 a2 b1 b2 0.78
c1 c2 d1 d2 c1 c2 d1 d2 0.78
Figure 4: An example of a digraph and its semi-double cover. 図4: 図形とその半二重被覆の例。 0.67
We follow the use of S1, S2 from Section 3: for any S ⊂ VG, we define S1 ⊂ VH and S2 ⊂ VH by S1 (cid:44) {v1 | v ∈ S} and S2 (cid:44) {v2 | v ∈ S}. S1 (cid:44) {v1 | v ∈ S} と S2 (cid:44) {v2 | v ∈ S} によって S1 の VH と S2 の VH と S2 の VH を定義する。
訳抜け防止モード: 我々は、セクション3からのS1, S2の使用に従う。 S1 ( cid:44 ) { v1 | v ∈ S } で S1 > VH と S2 > VH を定義する。 そして S2 ( cid:44 ) { v2 | v ∈ S } である。
0.84
The lemma below shows the connection between the value of FG(L, R) for any L, R and ΦH (L1 ∪ R2). 下記の補題は、任意の L, R に対する FG(L, R) の値と sH(L1, R2) の間の接続を示している。 0.80
Lemma 7. Let G be a digraph with semi-double cover H. Then, it holds for any L, R ⊂ VG that FG(L, R) = ΦH (L1 ∪ R2). 第7回。 G {\displaystyle G} を半二重被覆 H {\displaystyle H} のダイグラフとすると、任意の L, R > VG に対して FG(L, R) = >H (L1 > R2) が成り立つ。 0.62
Similarly, for any simple set S ⊂ VH, let L = {u : u1 ∈ S} and R = {u : u2 ∈ S}. 同様に、任意の単純集合 S に対して、L = {u : u1 ∈ S} と R = {u : u2 ∈ S} とする。 0.91
Then, it holds that FG(L, R) = ΦH (S). すると、FG(L, R) = >H(S) となる。 0.71
4.2 Design and Analysis of the Algorithm Our presented algorithm is a modification of the algorithm by Andersen and Peres [2]. 4.2 アルゴリズムの設計と解析 提案アルゴリズムはAndersen と Peres [2] によるアルゴリズムの変更である。 0.77
Given a digraph G as input, our algorithm simulates the volume-biased ESP on G’s semi-double cover H. Notice that the graph H can be constructed locally in the same way as the local construction of the double cover. 入力としてダイアグラム g が与えられると、g の半二重被覆 h 上の体積バイアス esp をシミュレートする。
訳抜け防止モード: g を入力として与える 私たちのアルゴリズムは、gの半値に偏りのあるespのボリュームをシミュレートします。 グラフhは、二重被覆の局所構成と同様に局所的に構成することができる。
0.72
However, as the output set S of an ESP-based algorithm is not necessarily simple, our algorithm only returns vertices u ∈ VG in which exactly one of u1 and u2 are included in S. The key procedure for our algorithm is given in Algorithm 4, in which the GenerateSample procedure is the one described at the end of Section 2. しかし、ESPベースのアルゴリズムの出力セット S は必ずしも単純ではないため、我々のアルゴリズムは u1 と u2 の1つが S に含まれる頂点 u ∈ VG のみを返す。
訳抜け防止モード: しかし、ESPベースのアルゴリズムの出力セットSは必ずしも単純ではない。 我々のアルゴリズムは、 u1 と u2 の1つが S に含まれる頂点 u ∈ VG のみを返す。 GenerateSampleプロシージャが第2節の最後に記述されているプロシージャである場合
0.62
Algorithm 4: EvoCutDirected (ECD) アルゴリズム4: EvoCutDirected (ECD) 0.74
2 Input: Starting vertex u, i ∈ {1, 2}, target flow ratio φ Output: A pair of sets L, R ⊂ VG Set T = (cid:98)(100φ Compute S = GenerateSampleH (ui, T ) Let L = {u ∈ VG : u1 ∈ S and u2 (cid:54)∈ S} Let R = {u ∈ VG : u2 ∈ S and u1 (cid:54)∈ S} return L and R 2 入力: vertex u, i ∈ {1, 2}, target flow ratio φ output: A pair of set L, R > VG Set T = (cid:98)(100φ Compute S = GenerateSampleH (ui, T ) let L = {u ∈ VG : u1 ∈ S and u2 (cid:54)∂ S} let R = {u ∈ VG : u2 ∈ S and u1 (cid:54)∂ S} return L and R 0.88
3 )−1(cid:99). 3 )−1(cid:99。 0.84
Notice that in our constructed graph H, Φ(L1 ∪ R2) ≤ φ does not imply that Φ(L2 ∪ R1) ≤ φ. 構築したグラフ h において、 φ(l1 , r2) ≤ φ は φ(l2 , r1) ≤ φ を含まないことに注意する。 0.73
Due to this asymmetry, Algorithm 4 takes a parameter i ∈ {1, 2} to indicate whether the starting vertex is in L or R. If it is not known whether u is in L or R, two copies can be run in parallel, one with i = 1 and the other with i = 2. この非対称性のため、アルゴリズム4はパラメータ i ∈ {1, 2} を用いて開始頂点が L 内か R 内かを示す。 u が L 内か R 内か分からない場合、2 つのコピーを平行に実行でき、一方は i = 1 で、もう一方は i = 2 である。 0.83
Once one of them terminates with the performance guaranteed in Theorem 2, the other can be terminated. その一方がTheorem 2で保証されたパフォーマンスで終了すると、もう一方は終了できる。 0.76
Hence, we can always assume that it is known whether the starting vertex u is in L or R. したがって、始頂点 u が L 内か R 内であるかは、常に知られていると仮定できる。 0.71
Now we sketch the analysis of the algorithm. さて,アルゴリズムの解析をスケッチする。 0.67
Notice that, since the evolving set process gives us an arbitrary set on the semi-double cover, in Algorithm 4 we convert this into a simple set by removing any vertices u where u1 ∈ S and u2 ∈ S. The following definition allows us to discuss sets which are close to being simple. 進化する集合過程は半二重被覆上の任意の集合を与えるので、アルゴリズム4では、u1 ∈ S と u2 ∈ S の任意の頂点 u を取り除いてこれを単純集合に変換する。
訳抜け防止モード: 注意すべきは、進化する集合過程は半二重被覆上の任意の集合を与えるからである。 アルゴリズム4では、u1 ∈ S の任意の頂点 u を取り除き、これを単純な集合に変換する。 次の定義では 単純に近い集合について議論します
0.81
Definition 4 (-simple set). 定義 4(単純集合)。 0.69
For any set S ⊂ VH, let P = {u1, u2 : u ∈ VG, u1 ∈ S and u2 ∈ S}. 任意の集合 S に対して、P = {u1, u2 : u ∈ VG, u1 ∈ S, u2 ∈ S} とする。 0.88
We call set S -simple if it holds that vol(P ) もしそれが vol(P ) であるなら、集合 S を S-simple と呼ぶ。 0.62
vol(S) ≤ . vol(S) ≤ s である。 0.82
1We remark that this reduction was also used by Anderson [1] for finding dense components in a digraph. 1 この還元は、ダイグラフ中の高密度成分を見つけるためにアンダーソン[1]によっても用いられた。 0.66
8 8 0.85
英語(論文から抽出)日本語訳スコア
The notion of -simple sets measures the ratio of vertices in which both u1 and u2 are in S. In particular, any simple set defined in Definition 2 is 0-simple. 特に、定義 2 で定義される任意の単純集合は 0-単純である。
訳抜け防止モード: 単純集合の概念は、頂点の比を成す。 u1 と u2 は特に s にある。 定義 2 で定義される任意の単純集合は 0-単純 である。
0.74
We show that, for any -simple set S ⊂ VH, one can construct a simple set S(cid:48) such that Φ(S(cid:48)) ≤ 1 1− · (Φ(S) + ). 任意の単純集合 S と VH に対して、s(S(cid:48)) ≤ 1 1 − · (s(S) + s) となるような単純集合 S(cid:48) を構成することができる。 0.82
Therefore, in order to guarantee that Φ(S(cid:48)) is small, we need to construct S such that Φ(S) is small and S is -simple for small . したがって、 φ(s(cid:48)) が小さいことを保証するためには、 φ(s) が小さく、 s が小さい s に対して単純であるような s を構築する必要がある。
訳抜け防止モード: そのため、順に S(cid:48 ) ) が小さいことを保証する 私たちはそのようなSを構築する必要があります S は小さい。 そして、S は小数 は単純である。
0.82
Because of this, our presented algorithm uses a lower value of T than the algorithm in Andersen and Peres [2]; this allows us to better control vol(S) at the cost of a slightly worse approximation guarantee. このため,提案アルゴリズムはアンデルセンおよびペレス[2]のアルゴリズムよりもTの値が低いため,近似保証がわずかに悪くなるため,Vol(S)の制御性が向上する。 0.64
Our algorithm’s performance is summarised in Theorem 2. アルゴリズムの性能はTheorem 2にまとめられている。 0.79
Theorem 2. Let G be an n-vertex digraph, and L, R ⊂ VG be disjoint sets such that F (L, R) ≤ φ and vol(L ∪ R) ≤ γ. 定理2。 G を n-頂点ダイグラフとし、L, R , VG を F(L, R) ≤ φ と vol(L, R) ≤ γ を満たすような非随伴集合とする。 0.72
There is a set C ⊆ L ∪ R with vol(C) ≥ vol(L ∪ R)/2 such that, for any v ∈ C and some i ∈ {1, 2}, EvoCutDirected(G, v, i, φ) returns (L(cid:48), R(cid:48)) such that F (L(cid:48), R(cid:48)) = O and vol(L(cid:48) ∪ R(cid:48)) = O 任意の v ∈ c とある i ∈ {1, 2} に対して、evocutdirected(g, v, i, φ) が (l(cid:48), r(cid:48)) を返して f (l(cid:48), r(cid:48)) = o と vol(l(cid:48) と vol(l(cid:48)) と r(cid:48)) = o となるような集合 c (c) ≥ vol(l ) r)/2 が存在する。 0.84
. Moreover, the algorithm has running time O . さらにアルゴリズムには実行時間Oがある 0.86
(1 − φ 1 3 )−1γ (1 − φ 1 3 )−1γ 0.83
φ− 1 φ 1 3 log φ− 1 φ 1 3 ログ 0.83
1 2 n (cid:16) 1 2 n (cid:16) 0.82
(cid:17) (cid:16) (cid:17) (cid:16) 0.78
(cid:17) (cid:16) (cid:17) (cid:16) 0.78
(cid:17) 2 γ log (cid:17) 2 γログ 0.78
3 2 n . To the best of our knowledge, this is the first local algorithm for digraphs that approximates a pair of densely connected clusters, and demonstrates that finding such a pair appears to be much easier than finding a low-conductance set in a digraph; in particular, existing local algorithms for finding a low-conductance set require the stationary distribution of the random walk in the digraph [3], the sublinear-time computation of which is unknown [9]. 3 2 n . 私たちの知る限りでは、これは1対の密結合したクラスタに近似するダイアグラムに対する最初の局所的アルゴリズムであり、そのようなペアを見つけることは、ダイアグラム内の低伝導性集合を見つけるよりもずっと容易であることを示している;特に、既存の低伝導性集合を見つけるための局所アルゴリズムは、ダイアグラフ [3] におけるランダムウォークの定常分布を必要とする。 0.83
However, knowledge of the stationary distribution is not needed for our algorithm. しかし,本アルゴリズムでは定常分布の知識は不要である。 0.76
Further Discussion. It is important to note that the semi-double cover construction is able to handle directed graphs which contain edges between two vertices u and v in both directions. さらなる議論。 半二重被覆構成は、2つの頂点 u と v の間の両方向の辺を含む有向グラフを扱えることに注意する必要がある。 0.72
In other words, the adjacency matrix of the digraph need not be skew-symmetric. 言い換えれば、ダイグラフの隣接行列はスキュー対称である必要はない。 0.69
This is an advantage of our approach over previous methods (e g , [10]), and it would be a meaningful research direction to identify the benefit this gives our developed reduction. これは従来の手法(例: [10])に対する我々のアプローチの利点であり、この方法が先進的な削減をもたらすメリットを特定する上で意義ある研究の方向性となるだろう。 0.80
It is also insightful to discuss why Algorithm 1 cannot be applied for digraphs, although the input digraph is translated into an undirected graph by our reduction. ダイグラフにアルゴリズム1を適用できない理由についても議論するが、この削減により入力ダイグラフは無向グラフに変換される。 0.72
This is because, when translating a digraph into a bipartite undirected graph, the third property of the σ-operator in Lemma 3 no longer holds, since the existence of the edge {u1, v2} ∈ EH does not necessarily imply that {u2, v1} ∈ EH. これは、グラフを二部グラフに変換するとき、レンマ3のσ-operatorの3番目の性質はもはや成り立たないため、辺 {u1, v2} ∈ EH の存在は {u2, v1} ∈ EH を必ずしも意味しないからである。 0.81
Indeed, Figure 5 gives a counterexample in which (σ ◦ (pW )) (u) (cid:54)≤ ((σ ◦ p)W ) (u). 実際、図5は、(σ ) (pW )) (u) (cid:54)≤ ((σ ) p)W ) (u) となる反例を与える。 0.73
This means that the typical analysis of a Pagerank vector with the Lov´asz-Simonovitz curve cannot be applied anymore. これは、Lov ́asz-Simonovitz曲線を持つページランクベクトルの典型的な解析はもはや適用できないことを意味する。 0.63
In our point of view, constructing some operator similar to our σ-operator and designing a Pagerank-based local algorithm for digraphs based on such an operator is a very interesting open question, and may help to close the gap in the approximation guarantee between the undirected and directed cases. 我々の見解では、σ-演算子に類似した演算子を構築し、そのような演算子に基づくダイグラフのページランクに基づく局所アルゴリズムを設計することは非常に興味深い問題であり、無向ケースと有向ケースの間の近似保証のギャップを埋めるのに役立つ。
訳抜け防止モード: 我々の見解では、σに類似した演算子を構築する -オペレーターとページランクの設計 - そのような演算子に基づくグラフの局所アルゴリズムは非常に興味深い開問題である。 無指示ケースと指示ケースの 近似保証のギャップを埋めるのに役立ちます
0.74
a b =⇒ a1 a2 あ b =⇒ a1 a2 0.74
b1 b2 Figure 5: Consider the digraph and its semi-double cover above. b1 b2 図5: 上のグラフとその半二重被覆を考える。 0.76
Suppose p(a1) = p(a2) = 0.5 and p(b1) = p(b2) = 0. p(a1) = p(a2) = 0.5 かつ p(b1) = p(b2) = 0 とする。 0.90
It is straightforward to check that (σ ◦ (pW ))(b2) = 0.25 and ((σ ◦ p)W )(b2) = 0. pW ))(b2) = 0.25 かつ ((σ ) p)W )(b2) = 0 であることを確認するのは簡単である。 0.87
In addition, we underline that one cannot apply the tighter analysis of the ESP process given by Andersen et al. さらに、アンデルセンらによって与えられたespプロセスのより厳密な分析は適用できないと結論づけた。 0.64
[5] to our algorithm. アルゴリズムに[5] 0.51
The key to their analysis is an improved bound on the probability that a random walk escapes from the target cluster. 分析の鍵は、ランダムウォークがターゲットクラスタから脱出する確率に基づいて改善されたバウンダリである。 0.74
In order to take advantage of this, they use a larger value of T in the algorithm which relaxes the guarantee on the volume of the output set. これを利用するために、彼らは、出力セットの体積に対する保証を緩和するアルゴリズムにおいて、より大きなT値を使用する。 0.76
Since our analysis relies on a very tight guarantee on the overlap of the output set with the target set, we cannot use their improvement in our setting. 我々の分析は、ターゲットセットとの出力セットの重複を非常に厳格に保証しているので、我々の設定ではそれらの改善は利用できない。 0.71
5 Experiments In this section we evaluate the performance of our proposed algorithms on both synthetic and real-world data sets. 5 実験 本稿では,合成データと実世界データの両方における提案アルゴリズムの性能評価を行う。 0.83
For undirected graphs, we compare the performance of our algorithm against the previous state-of-the-art [15], through the synthetic dataset with various parameters and apply the real-world dataset to demonstrate the significance of our algorithm. 非有向グラフの場合、従来の[15]状態と比較し、様々なパラメータを用いた合成データセットを用いて実世界データセットを適用し、アルゴリズムの意義を実証する。
訳抜け防止モード: 非有向グラフの場合、アルゴリズムのパフォーマンスを以前の状態(-art [15])と比較します。 様々なパラメータを持つ合成データセットを通し、実世界データセットを適用する アルゴリズムの意義を示すためです
0.81
For directed graphs, we compare the performance of our algorithm with the 有向グラフの場合、アルゴリズムの性能と性能を比較する。 0.68
9 9 0.85
英語(論文から抽出)日本語訳スコア
state-of-the-art non-local algorithm since, to the best of our knowledge, our local algorithm for digraphs is the first such algorithm in the literature. 最先端の非局所アルゴリズム 最善の知識として、我々のダイアグラムの局所アルゴリズムは、文献における最初のそのようなアルゴリズムである。 0.76
All experiments were performed on a Lenovo Yoga 2 Pro with an Intel(R) Core(TM) i7-4510U CPU @ 2.00GHz processor and 8GB of RAM. 全ての実験はLenovo Yoga 2 ProでIntel(R) Core(TM) i7-4510U CPU @2.00GHzプロセッサと8GBのRAMで実施された。 0.82
Our code can be downloaded from https://github.com/p macg/local-densely-c onnected-clusters. 私たちのコードはhttps://github.com/p macg/local-densely-c onnected-clustersからダウンロードできる。 0.41
5.1 Results for Undirected Graphs 5.1.1 Experiments on Synthetic Data 5.1 無向グラフの成果 5.1.1 合成データに関する実験 0.63
We first compare the performance of our algorithm, LocBipartDC, with the previous state-of-the-art given by Li & Peng [15], which we refer to as LP, on synthetic graphs generated from the stochastic block model (SBM). 確率ブロックモデル(SBM)から生成した合成グラフ上で,まずアルゴリズムLocBipartDCと,Li & Peng [15]による先行技術との比較を行った。
訳抜け防止モード: まず,我々のアルゴリズムであるlocbipartdcの性能と,li & peng [15] が与えた以前の状態との比較を行った。 確率ブロックモデル(sbm)から生成された合成グラフについてlpと呼ぶ。
0.79
Specifically, we assume that the graph has k = 3 clusters {Cj}3 j=1, and the number of vertices in each cluster, denoted by n1, n2 and n3 respectively, satisfy n1 = n2 = 0.1n3. 具体的には、グラフは k = 3 個のクラスタ {Cj}3 j=1 を持ち、各クラスタ内の頂点の数は、それぞれ n1, n2, n3 で表され、n1 = n2 = 0.1n3 を満たすと仮定する。 0.72
Moreover, any pair of vertices u ∈ Ci and v ∈ Cj is connected with probability Pi,j. さらに、任意の頂点 u ∈ Ci と v ∈ Cj の対は確率 Pi,j と連結である。 0.81
We assume that P1,1 = P2,2 = p1, P3,3 = p2, P1,2 = q1, and P1,3 = P2,3 = q2. P1,1 = P2,2 = p1, P3,3 = p2, P1,2 = q1, P1,3 = P2,3 = q2 と仮定する。 0.61
Throughout our experiments, we maintain the ratios p2 = 2p1 and q2 = 0.1p1, leaving the parameters n1, p1 and q1 free. 実験を通して、p2 = 2p1 と q2 = 0.1p1 の比率を維持し、パラメータ n1, p1, q1 は自由である。 0.66
Notice that the different values of q1 and q2 guarantee that C1 and C2 are the ones optimising the β-value, which is why our proposed model is slightly more involved than the standard SBM. q1 と q2 の異なる値が c1 と c2 が β-値に最適化されていることを保証していることに注意してください。 0.64
We evaluate the quality of the output (L, R) returned by each algorithm with respect to its β-value, the Adjusted Rand Index (ARI) [12], as well as the ratio of the misclassified vertices defined by |L(cid:52)C1|+|R(cid:52)C2| |L∪C1|+|R∪C2| , where A(cid:52)B is the symmetric difference between A and B. a(cid:52)b が a と b の間の対称差分であるような |l(cid:52)c1|+|r(cid:52)c2|||l_c1|+|r_c2| で定義される誤分類された頂点の比率とともに、各アルゴリズムが返した出力 (l, r) のβ値、調整されたランド指数 (ari) [12] に関する品質を評価する。
訳抜け防止モード: 各アルゴリズムが返す出力(L, R)の質をβ値に対して評価する。 Adjusted Rand Index ( ARI ) [ 12 ] と |L(cid:52)C1|+|R(cid:52)C2| |L\C1|+|R\C2| で定義される誤分類された頂点の比率 ここで A(cid:52)B は A と B の対称差である。
0.77
All our reported results are the average performance of each algorithm over 10 runs, in which a random vertex from C1 ∪ C2 is chosen as the starting vertex of the algorithm. 報告された結果はすべて,アルゴリズムの開始頂点としてc1/c2からランダムな頂点が選択される,各アルゴリズムの平均性能である。 0.76
Setting the  parameter in the LP algorithm. LPアルゴリズムで s パラメータを設定する。 0.69
The LP algorithm has an additional parameter over ours, which we refer to as LP . lpアルゴリズムは、我々の上では追加のパラメータを持ち、これを slp と呼ぶ。 0.66
This parameter influences the runtime and performance of the algorithm and must be in the range [0, 1/2]. このパラメータはアルゴリズムの実行時間と性能に影響し、[0, 1/2]の範囲でなければならない。 0.78
In order to choose a fair value of LP for comparison with our algorithm, we consider several values on graphs with a range of target volumes. アルゴリズムとの比較において, slp の公平な値を選択するために, 対象体積の広いグラフ上の複数の値を考える。 0.74
We generate graphs from the SBM such that p1 = 1/n1 and q1 = 100p1 and vary the size of the target set by varying n1 between 100 and 10, 000. SBM から p1 = 1/n1 と q1 = 100p1 のグラフを生成し、ターゲットセットのサイズを 100 から 10 000 の間で変化させる。 0.79
For values of LP in {0.01, 0.02, 0.1, 0.5}, Figure 6(a) shows how the runtime of the LP algorithm compares to the LocBipartDC algorithm for a range of target volumes. {0.01, 0.02, 0.1, 0.5} の値に対して、図6(a) は、LPアルゴリズムのランタイムがターゲットボリュームの範囲で LocBipartDC アルゴリズムと比較する方法を示している。 0.79
In this experiment, the runtime of the LocBipartDC algorithm lies between the runtimes of the LP algorithm for LP = 0.01 and LP = 0.02. この実験では、locbipartdcアルゴリズムのランタイムは、lp = 0.01 の lp アルゴリズムのランタイムと slp = 0.02 のランタイムの間にある。 0.64
However, Figure 6(b) shows that the performance of the LP algorithm with LP = 0.01 is significantly worse than the performance of the LocBipartDC algorithm and so for a fair comparison, we set LP = 0.02 for the remainder of the experiments. しかし、図6(b)は、LPアルゴリズムの性能がLocBipartDCアルゴリズムの性能よりも著しく劣っていることを示しており、公平な比較のために、実験の残りの部分について、LP = 0.02を設定した。 0.79
Figure 6: (a) A comparison of the runtimes of the LocBipartDC algorithm and the LP algorithm with various values of LP . 図6: (a) LocBipartDC アルゴリズムと LP アルゴリズムの様々な値との比較。 0.56
(b) Setting LP = 0.01 results in significantly worse performance than the LocBipartDC algorithm. b) LocBipartDC アルゴリズムよりも,0.01 の値を設定すると性能が著しく低下する。 0.73
(a) (b) Comparison on the Synthetic Data. (a) (b) 合成データの比較 0.74
We now compare the LocBipartDC and LP algorithms’ performance on graphs generated from the SBM with different values of n1, p1 and q1. sbmから生成されたグラフに対するlocbipartdcとlpアルゴリズムのパフォーマンスを,n1,p1,q1の値で比較した。 0.67
As shown in Table 1, our algorithm not only runs faster, but also produces better clusters with respect to all three metrics. 表1に示すように、アルゴリズムは高速に走るだけでなく、3つのメトリクスすべてに対してより良いクラスタを生成する。 0.77
Secondly, since the clustering task becomes more challenging when the target clusters have higher β-value, we compare the algorithms’ performance on a sequence of instances with increasing value of β. 第二に、ターゲットクラスタがβ値が高い場合にはクラスタリングタスクがより困難になるため、一連のインスタンスにおけるアルゴリズムのパフォーマンスとβ値の増大を比較する。 0.82
Since q1/p1 = 2(1 − β)/β, we simply fix q1/p1 = 2(1 − β)/β なので、簡単に修正する。 0.64
10 50001×1045×1041×1055×105010203040506070Ta rgetSetVolumeTime(s) LocBipartDCLPϵ=0.01LPϵ=0.02LPϵ=0.1LPϵ=0.550001×1045×1041×1055×1050.00.20.40.60.81. 0TargetSetVolumeARIL ocBipartDCLPϵ=0.01 10 50001×1045×1041×1055×10501020406070Target SetVolumeTime(s)LocB ipartDCLPε=0.01LPε=0.02LPε=0.1LPε=0.550001×1045×1041×1055×1050.00.20.60.81.0Ta rgetSetVolumeARILocB ipartDCLPε=0.01 0.48
英語(論文から抽出)日本語訳スコア
Table 1: Full comparison between Algorithm 1 (LBDC) and the previous state-of-the-art [15] (LP). 表1:アルゴリズム1(LBDC)と以前の最先端[15](LP)の完全な比較。 0.71
For clarity we report the target bipartiteness β = β(C1, C2) and target volume γ = vol(C1 ∪ C2) along with the SBM parameters. 明確にするために、ターゲットの2成分性 β = β(c1, c2) とターゲットボリューム γ = vol(c1, c2) とsbmパラメータを報告する。 0.73
INPUT GRAPH PARAMETERS 入力グラフパラメータ 0.42
ALGO. RUNTIME ALGO ruNTIME 0.57
β-VALUE n1 = 1, 000, p1 = 0.001, q1 = 0.018 β値 n1 = 1, 000, p1 = 0.001, q1 = 0.018 0.71
β ≈ 0.1, γ ≈ 40, 000 β ≈ 0.1, γ ≈ 40, 000 0.98
n1 = 10, 000, p1 = 0.0001, q1 = 0.0018 n1 = 10, 000, p1 = 0.0001, q1 = 0.0018 0.78
β ≈ 0.1, γ ≈ 400, 000 β ≈ 0.1, γ ≈ 400, 000 0.98
n1 = 100, 000, p1 = 0.00001, q1 = 0.00018 n1 = 100, 000, p1 = 0.00001, q1 = 0.00018 0.78
β ≈ 0.1, γ ≈ 4, 000, 000 β ≈ 0.1, γ ≈ 4, 000, 000 0.99
n1 = 1, 000, p1 = 0.004, q1 = 0.012 n1 = 1, 000, p1 = 0.004, q1 = 0.012 0.78
β ≈ 0.4, γ ≈ 40, 000 β ≈ 0.4, γ ≈ 40, 000 0.98
LBDC LP LBDC LBDC LP LBDC 0.85
LP LBDC LP LP LBDC LP 0.85
LBDC LP 0.09 0.146 0.992 1.327 19.585 30.285 1.249 1.329 LBDC LP 0.09 0.146 0.992 1.327 19.585 30.285 1.249 1.329 0.71
0.154 0.202 0.215 0.297 0.250 0.300 0.506 0.597 0.154 0.202 0.215 0.297 0.250 0.300 0.506 0.597 0.42
ARI MISCLASSIFIED RATIO 0.968 0.909 0.940 0.857 0.950 0.865 0.503 0.445 比0.968 0.909 0.940 0.857 0.950 0.865 0.503 0.445 0.45
0.073 0.138 0.145 0.256 0.166 0.225 0.763 0.785 0.073 0.138 0.145 0.256 0.166 0.225 0.763 0.785 0.42
the values of n1, p1 as n1 = 1, 000, p1 = 0.001, and generate graphs with increasing value of q1/p1; this gives us graphs with monotone values of β. n1, p1 の値は n1 = 1, 000, p1 = 0.001 であり、q1/p1 の値が増加するグラフを生成する。 0.81
As shown in Figure 7(a), our algorithms performance is always better than the previous stat-of-the-art. 図7(a)に示すように、我々のアルゴリズムの性能は前回よりも常に優れている。 0.75
(a) (b) Figure 7: β-value. (a) (b) 図7: β値。 0.86
(b) The ARI of each algorithm when bounding the runtime of the algorithm. (b)アルゴリズムのランタイムをバウンディングする際の各アルゴリズムのARI。 0.78
(a) The ARI of each algorithm when varying the target β-value. (a)ターゲットβ値を変化させる際の各アルゴリズムのARI。 0.89
A larger q1/p1 ratio corresponds to a smaller より大きなq1/p1比は小さい値に対応する 0.62
Thirdly, notice that both algorithms use some parameters to control the algorithm’s runtime and the output’s approximation ratio, which are naturally influenced by each other. 第3に、両方のアルゴリズムがアルゴリズムのランタイムと出力の近似比を制御するためにいくつかのパラメータを使用していることに注意してください。 0.77
To study this dependency, we generate graphs according to n1 = 100, 000, p1 = 0.000015, and q1 = 0.00027 which results in target sets with β ≈ 0.1 and volume γ ≈ 6, 000, 000. この依存性を研究するために、n1 = 100, 000, p1 = 0.000015, q1 = 0.00027 に従ってグラフを生成する。
訳抜け防止モード: この依存関係を研究する。 n1 = 100, 000, p1 = 0.000015, そしてq1 = 0.00027 ターゲット集合は β = 0.1 で、体積 γ = 6, 000, 000 である。
0.75
Figure 7(b) shows that, in comparison with the previous state-of-the-art, our algorithm takes much less time to produce output with the same ARI value. 図7(b)は、従来の最先端技術と比較して、我々のアルゴリズムが同じARI値の出力を生成するのにはるかに時間を要することを示している。 0.67
5.1.2 Experiments on the Real-world Dataset 5.1.2 実世界のデータセットに関する実験 0.53
We demonstrate the significance of our algorithm on the Dyadic Militarised Interstate Disputes Dataset (v3.1) [19], which records every interstate dispute during 1816–2010, including the level of hostility resulting from the dispute and the number of casualties, and has been widely studied in the social and political sciences [18, 20] as well as the machine learning community [13, 21, 26]. このアルゴリズムは,1816~2010年におけるすべての州間紛争を記録したdyadic militarised interstate disputes dataset (v3.1) [19] において,紛争による敵意のレベルや死傷者数などの重要性を実証し,社会・政治科学 [18,20] や機械学習コミュニティ [13,21,26] において広く研究されている。 0.84
For a given time period, we construct a graph from the data by representing each country with a vertex and adding an edge between each pair of countries weighted according to the severity of any military disputes between those countries. 所定の期間、各国を頂点で表現し、両国間の軍事紛争の深刻度に応じて重み付けられた各国間の縁を追加することにより、データからグラフを構築する。 0.66
Specifically, if there’s a war2 between the two countries, the corresponding two vertices are connected by an edge with weight 30; for any other dispute that is not part of an interstate war, the two corresponding vertices are connected by an edge with weight 1. 具体的には、2つの国の間に戦争がある場合、対応する2つの頂点が重み30でエッジで接続され、州間戦争の一部ではない他の紛争に対して、対応する2つの頂点は重み1でエッジで接続される。 0.69
We always use the USA as the starting vertex of the algorithm, and our algorithm’s output, as visualised in Figure 1(a)-(d), can be well explained by geopolitics. 私たちは常に米国をアルゴリズムの出発頂点として使用しており、我々のアルゴリズムの出力は、図1(a)-(d)で視覚化されているように、ジオポリティクスによってよく説明できます。 0.76
The β-values of the pairs of clusters in Figures 1(a)-(d) are 0.361, 0.356, 0.170 and 0.191 respectively. 図1(a)-(d)のクラスター対のβ値はそれぞれ0.361、0.356、0.170、0.191である。 0.84
2A war is defined by the maintainers of the dataset as a series of battles resulting in at least 1,000 deaths. 2A戦争はデータセットのメンテナによって、少なくとも1,000人が死亡する一連の戦闘として定義されている。 0.61
11 2468100.00.20.40.60. 8Ratioq1/p1ARILocBip artDCLP510152025300. 50.60.70.80.91.0Time (s)ARILocBipartDCLP 11 2468100.00.40.60.8Ra tioq1/p1ARILocBipart DCLP5102025300.50.60 .70.80.91.0Time(s)AR ILocBipartDCLP 0.53
英語(論文から抽出)日本語訳スコア
5.2 Results for Digraphs Next we evaluate the performance of our algorithm for digraphs on synthetic and real-world datasets. 5.2 ダイグラフの結果 次に,合成および実世界のデータセット上でのダイグラフに対するアルゴリズムの性能を評価する。 0.67
Since there are no previous local digraph clustering algorithms that achieve similar objectives to ours, we compare the output of Algorithm 4 (ECD) with the state-of-the-art non-local algorithm proposed by Cucuringu et al [10], and we refer this to as CLSZ in the following. 従来の局所グラフクラスタリングアルゴリズムは我々のものと類似した目的を達成できなかったため、アルゴリズム4(ECD)の出力とCucuringu et al [10]による最先端の非局所アルゴリズムを比較し、以下に示すようにCLSZと呼ぶ。 0.82
Synthetic Dataset. We first look at the cyclic block model (CBM) described in Cucuringu et al [10] with parameters k, n, p, q, and η. 合成データセット。 まず,cucuringu et al [10] のパラメータ k, n, p, q, η について記述した cyclic block model (cbm) について考察する。 0.78
In this model, we generate a digraph with k clusters C1, . このモデルでは、k 個のクラスタ C1 のダイグラフを生成する。 0.75
. . , Ck of size n, and for u, v ∈ Ci, there is an edge between u and v with probability p and the edge direction is chosen uniformly at random. . . , Ck of size n, and for u, v ∈ Ci, have a edge between u and v with probability p and the edge direction is uniformly at random. 0.83
For u ∈ Ci and v ∈ Ci+1 mod k, there is an edge between u and v with probability q, and the edge is directed from u to v with probability η and from v to u with probability 1 − η. u ∈ Ci と v ∈ Ci+1 mod k に対して、確率 q の u と v の間の辺が存在し、その辺は確率 η の u から v へ、確率 1 − η の v から u へ向けられる。 0.78
Throughout our experiments, we fix p = 0.001, q = 0.01, and η = 0.9. 実験を通して、p = 0.001, q = 0.01, η = 0.9 を固定する。 0.80
Secondly, since the goal of our algorithm is to find local structure in a graph, we extend the cyclic block model with additional local clusters and refer to this model as CBM+. 第2に,アルゴリズムの目的はグラフ内の局所構造を見つけることであるので,局所クラスタを追加して巡回ブロックモデルを拡張し,このモデルを CBM+ と呼ぶ。 0.85
In addition to the parameters of the CBM, we introduce the parameters n(cid:48), q(cid:48) 2, and η(cid:48). CBMのパラメータに加えて,パラメータn(cid:48),q(cid:48)2 ,η(cid:48)を導入する。 0.72
In this model, the clusters C1 to Ck are generated as in the CBM, and there are two additional clusters Ck+1 and Ck+2 of size n(cid:48). このモデルでは、クラスタC1〜CkがCBMのように生成され、2つの追加クラスタCk+1とCk+2がサイズn(cid:48)である。 0.72
For u, v ∈ Ck+i for i ∈ {1, 2}, there is an edge between u and v with probability p and for u ∈ Ck+1 and v ∈ Ck+2, there is an edge with probability q(cid:48) 1; the edge directions are chosen uniformly at random. i ∈ {1, 2} の u, v ∈ Ck+i に対して、u と v の間に確率 p の辺が存在し、u ∈ Ck+1 と v ∈ Ck+2 に対して、確率 q(cid:48) 1 の辺が存在する。 0.76
For u ∈ Ck+1 ∪ Ck+2 and v ∈ C1, there is an edge with 2. u ∈ Ck+1 > Ck+2 および v ∈ C1 に対して、辺は 2 である。 0.83
If u ∈ Ck+1, the orientation is from v to u with probability η(cid:48) and from u to v with probability probability q(cid:48) 1− η(cid:48) and if u ∈ Ck+2, the orientation is from u to v with probability η(cid:48) and from v to u with probability 1− η(cid:48). u ∈ Ck+1 ならば、向きは確率 η(cid:48) の v から u へ、確率 q(cid:48) 1− η(cid:48) の u から v へ、そして u ∈ Ck+2 が確率 η(cid:48) の u から v へ、確率 1− η(cid:48) の v から u へ向けられる。 0.83
We always fix q(cid:48) 2 = 0.005, and η(cid:48) = 1. 常に q(cid:48) 2 = 0.005 と η(cid:48) = 1 を固定する。 0.75
Notice that the clusters Ck+1 and Ck+2 form a “local” cycle with the cluster C1. クラスタ Ck+1 と Ck+2 がクラスタ C1 で「局所」サイクルを形成することに注意。 0.75
1 = 0.5, q(cid:48) 1 = 0.5, q(cid:48) 0.81
1, q(cid:48) 1, q(cid:48) 0.92
In Table 2, we report the average performance over 10 runs with a variety of parameters. 表2では、さまざまなパラメータを備えた10実行当たりの平均パフォーマンスを報告します。 0.80
We find that CLSZ can uncover the global structure in the CBM more accurately than ECD. CLSZはECDよりも正確にCBMのグローバル構造を明らかにすることができる。 0.74
On the other hand, CLSZ fails to identify the local cycle in the CBM+ model, while ECD succeeds. 一方、LCSZはCBM+モデルの局所サイクルを識別できず、ECDは成功する。
訳抜け防止モード: 一方、CLSZは失敗します。 CBM+モデルの局所サイクルを識別し、ECDが成功する。
0.65
Table 2: Comparison of ECD with CLSZ on synthetic data. 表2:合成データにおけるCDとLCSZの比較 0.77
MODEL CBM CBM CBM+ CBM+ モデルCBM CBM+CBM+ 0.75
n(cid:48)102 102 n(cid:48)102 102 0.92
TIME ARI n k ECD 時間 アリ n k ECD 0.70
CLSZ ECD CLSZ CLSZ ECD CLSZ 0.85
103 103 103 104 103 103 103 104 0.85
3.99 1.59 5 50 3.81 156.24 3 3 3.99 1.59 5 50 3.81 156.24 3 3 0.64
6.12 45.17 6.12 45.17 0.50
0.24 0.32 0.92 0.99 0.98 0.99 0.24 0.32 0.92 0.99 0.98 0.99 0.48
1.00 0.99 0.35 0.01 1.00 0.99 0.35 0.01 0.45
Real-world Dataset. 実世界のデータセット。 0.51
Now we evaluate the algorithms’ performance on the US Migration Dataset [28]. 今回は,米国のマイグレーションデータセット[28]におけるアルゴリズムのパフォーマンスを評価する。 0.81
For fair comparison, we follow Cucuringu et al [10] and construct the digraph as follows: every county in the mainland USA is represented by a vertex; for any vertices j, (cid:96), the edge weight of (j, (cid:96)) is given by where Mj,(cid:96) is the number of people who migrated from county j to county (cid:96) between 1995 and 2000; in addition, the direction of (j, (cid:96)) is set to be from j to (cid:96) if Mj,(cid:96) > M(cid:96),j, otherwise the direction is set to be the opposite. アメリカ合衆国本土のすべての郡は頂点で表される; (cid:96) 任意の頂点 j に対して、 (j, (cid:96)) の端の重さは、mj, (cid:96) は、1995年から2000年の間に j 郡から郡 (cid:96) に移動した人々の数である; さらに (j, (cid:96) の方向が j から (cid:96) に設定される: mj, (cid:96) > m(cid:96)j ならば、その方向は逆になる。
訳抜け防止モード: 公正な比較のために、Cucuringu et al [10 ] に従う。 図を次のように作成します 米国本土のすべての郡は頂点で代表される ; 任意の頂点 j, (cid:96 ) に対して、(j, (cid:96 ) ) のエッジ重量は、Mj, (cid:96 ) が人の数である場所によって与えられる。 1995年から2000年の間にJ郡から (cid:96 ) ; さらに (j, ( cid:96 ) の方向を設定する to be j to ( cid:96 ) if Mj,(cid:96 ) > M(cid:96),j, さもないと方向が逆になる。
0.80
For CLSZ, we follow their suggestion on the same dataset and set k = 10. CLSZの場合、同じデータセット上で提案に従い、k = 10とする。 0.75
Both algorithms’ performance is evaluated with respect to the flow ratio, as well as the Cut Imbalance ratio used in their work. 両方のアルゴリズムのパフォーマンスは、フロー比、および彼らの作業で使用されるカット不均衡比について評価される。 0.74
For any vertex sets L and R, the cut imbalance ratio is defined by CI(L, R) = 1 indicates the connection between L and R is more significant. 任意の頂点集合 L と R に対して、カット不均衡比は CI(L, R) = 1 で定義される。
訳抜け防止モード: 任意の頂点集合 L と R に対して、カット不均衡比は CI(L,) で定義される。 R ) = 1 は L と R の間の接続がより大きいことを示す。
0.78
Using counties in Ohio, New York, California, and Florida as the starting vertices, our algorithm’s outputs are visualised in Figures 1(e)-(h), and in Table 3 we compare them to the top 4 pairs returned by CLSZ, which are shown in Figure 8. オハイオ、ニューヨーク、カリフォルニア、フロリダの各郡を出発点として、我々のアルゴリズムの出力は図1(e)-(h)で視覚化され、表3ではCLSZで返される上位4ペアと比較します。
訳抜け防止モード: オハイオ州、ニューヨーク州、カリフォルニア州、フロリダ州の各郡を出発点とする。 私たちのアルゴリズムの出力は図1(e)-(h )で視覚化されます。 表3では、CLSZで返される上位4ペアと比較します。 図8に示します。
0.69
Our algorithm produces better outputs with respect to both metrics. 我々のアルゴリズムは両方の指標に対してより良い出力を生成する。 0.66
(cid:12)(cid:12)(cid :12) Mj,(cid:96)−M(cid:96),j (cid:12)(cid:12)(cid :12), (cid:12)(cid:12)(cid :12), and a higher CI(L, R) value (cid:12)(cid:12)(cid :12)Mj,(cid:96)−M(cid:96)j(cid:12)(c id:12)(cid:12)、(cid:12)(cid:12)(cid :12)、CI(L, R)値が高い 0.81
2 ·(cid:12)(cid:12)(cid :12) e(L,R)−e(R,L) 2 ·(cid:12)(cid:12)(cid :12)e(L,R)−e(R,L) 0.90
e(L,R)+e(R,L) e(L,R)+e(R,L) 0.92
Mj,(cid:96)+M(cid:96),j Mj,(cid:96)+M(cid:96),j 0.94
These experiments suggest that local algorithms are not only more efficient, but can also be much more effective than global algorithms when learning certain structures in graphs. これらの実験は、局所アルゴリズムはより効率的であるだけでなく、グラフで特定の構造を学ぶ場合のグローバルアルゴリズムよりもはるかに効果的であることを示唆している。
訳抜け防止モード: これらの実験は、局所アルゴリズムがより効率的であるだけでなく しかし、グラフで特定の構造を学ぶ場合、グローバルアルゴリズムよりもずっと効果的です。
0.77
In particular, some localised structure might be hidden when applying the objective function over the entire graph. 特に、グラフ全体に目的関数を適用する際には、いくつかの局所構造が隠されることがある。 0.63
12 12 0.85
英語(論文から抽出)日本語訳スコア
Table 3: Comparison of EvoCutDirected with CLSZ on the US migration dataset. 表3: 米国移行データセット上のEvoCutDirectedとCLSZの比較。 0.76
FIGURE ALGORITHM CLSZ CLSZ CLSZ CLSZ 図 アルゴリズム CLSZ CLSZ CLSZ 0.58
8(A) 8(B) 8(C) 8(D) 1(E) 1(F) 1(G) 1(H) 8(A) 8(B) 8(C) 8(D) 1(E) 1(F) 1(G) 1(H) 0.85
CLUSTER PAIR 1 PAIR 2 PAIR 3 PAIR 4 クルスターペア1 ペア2 ペア3 ペア4 0.47
OHIO SEED CUT IMBALANCE オハイオ種 カット不均衡 0.35
FLOW RATIO 0.41 0.35 0.32 0.29 0.50 0.49 0.49 0.42 流量比 0.41 0.35 0.32 0.29 0.50 0.49 0.49 0.42 0.46
0.80 0.83 0.84 0.84 0.56 0.58 0.67 0.79 0.80 0.83 0.84 0.84 0.56 0.58 0.67 0.79 0.42
EVOCUTDIRECTED NEW YORK SEED EVOCUTDIRECTED EVOCUTDIRECTED CALIFORNIA SEED EVOCUTDIRECTED evocutdirected new york seed evocutdirected evocutdirected california seed evocutdirected 0.37
FLORIDA SEED (a) CLSZ, Pair 1 フロリダシード (a)CLSZ、Pair 1 0.64
(b) CLSZ, Pair 2 (b)CLSZ、Pair2 0.78
(c) CLSZ, Pair 3 (c)CLSZ、Pair 3 0.81
(d) CLSZ, Pair 4 (d)CLSZ、Pair 4 0.81
Figure 8: The top 4 pairs of clusters found by CLSZ on the US Migration dataset. 図8:米国のマイグレーションデータセットでclszによって発見されたクラスタの上位4つ。 0.78
Acknowledgements We thank Luca Zanetti for making insightful comments on an earlier version of this work. 覚書 Luca Zanetti氏は、この作品の初期バージョンについて洞察に富んだコメントをしてくれてありがとう。 0.52
Peter Macgregor is supported by the Langmuir PhD Scholarship, and He Sun is supported by an EPSRC Early Career Fellowship (EP/T00729X/1). Peter MacgregorはLangmuir PhD Scholarshipに、He SunはEP/T00729X/1に支援されている。 0.67
References [1] Reid Andersen. 参考文献 リード・アンデルセン(Reid Andersen)。 0.61
A local algorithm for finding dense subgraphs. 高密度部分グラフ探索のための局所アルゴリズム 0.71
ACM Transactions on Algorithms (TALG), ACM Transactions on Algorithms (TALG) 0.72
6(4):1–12, 2010. 6(4):1–12, 2010. 0.88
[2] Reid Andersen and Kumar Chellapilla. リード・アンデルセン(Reid Andersen)とクマール・チェラピラ(Kumar Chellapilla)。 0.43
Finding dense subgraphs with size bounds. サイズ境界を持つ密接な部分グラフを見つける。 0.50
In International Workshop on Algorithms and Models for the Web-Graph, pages 25–37, 2009. 海外では The Workshop on Algorithms and Models for the Web-Graph, page 25–37, 2009 0.76
[3] Reid Andersen and Fan Chung. [3]リード・アンデルセンとファン・チュン。 0.59
Detecting sharp drops in Pagerank and a simplified local partitioning algorithm. Pagerankにおけるシャープドロップの検出と簡易なローカルパーティショニングアルゴリズム。 0.76
In International Conference on Theory and Applications of Models of Computation (TAMC’07), pages 1–12, 2007. 計算モデルの理論と応用に関する国際会議(TAMC'07)において、2007年1-12ページ。 0.82
[4] Reid Andersen, Fan Chung, and Kevin Lang. Reid Andersen氏、Fan Chung氏、Kevin Lang氏。 0.59
Local graph partitioning using Pagerank vectors. Pagerankベクトルを用いた局所グラフ分割 0.82
In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 475–486, 2006. 47世紀 IEEE Symposium on Foundations of Computer Science (FOCS’06) 475-486, 2006年。 0.65
[5] Reid Andersen, Shayan Oveis Gharan, Yuval Peres, and Luca Trevisan. 5]Reid Andersen, Shayan Oveis Gharan, Yuval Peres, Luca Trevisan。 0.64
Almost optimal local graph clustering using evolving sets. ほぼ最適局所グラフ 進化する集合を使ったクラスタリング 0.70
Journal of the ACM (JACM), 63(2):1–31, 2016. The Journal of the ACM (JACM), 63(2):1-31, 2016 0.90
[6] Reid Andersen and Yuval Peres. 6] リード・アンデルセンと ユーヴァル・ペレス 0.53
Finding sparse cuts locally using evolving sets. 進化集合を用いて局所的にスパースカットを見つける。 0.47
In 41st Annual ACM 第41回年次大会報告 0.48
Symposium on Theory of Computing (STOC’09), pages 235–244, 2009. The Symposium on Theory of Computing (STOC’09) 235–244, 2009 0.78
[7] Austin R. Benson, David F. Gleich, and Jure Leskovec. 7]austin r. benson、david f. gleich、jure leskovec。 0.52
Tensor spectral clustering for partitioning higherorder network structures. 高次ネットワーク構造分割のためのテンソルスペクトルクラスタリング 0.79
In 15th International Conference on Data Mining (ICDM’15), pages 118–126, 2015. 第15回国際データマイニング会議(ICDM'15)において、2015年118-126頁。 0.75
[8] Austin R. Benson, David F. Gleich, and Jure Leskovec. 8]austin r. benson、david f. gleich、jure leskovec。 0.52
Higher-order organization of complex networks. 複雑なネットワークの高次構造。 0.75
Science, 353(6295):163–166, 2016. 科学、353(6295):163–166, 2016。 0.81
13 13 0.85
英語(論文から抽出)日本語訳スコア
[9] Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B Rao, Aaron Sidford, and Adrian Vladu. Michael B Cohen氏、Jonathan Kelner氏、John Peebles氏、Richard Peng氏、Anup B Rao氏、Aaron Sidford氏、Adrian Vladu氏。 0.74
Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs. マルコフ連鎖のほぼ線形時間アルゴリズムと有向グラフの新しいスペクトルプリミティブ 0.76
In 49th Annual ACM Symposium on Theory of Computing (STOC’17), pages 410–419, 2017. 第49回ACM Symposium on Theory of Computing (STOC’17) で、2017年410-419頁。 0.80
[10] Mihai Cucuringu, Huan Li, He Sun, and Luca Zanetti. [10]Mihai Cucuringu、Huan Li、He Sun、Luca Zanetti。 0.66
Hermitian matrices for clustering directed graphs: In 23rd International Conference on Artificial Intelligence and Statistics クラスタリング指向グラフのためのエルミート行列:第23回人工知能と統計に関する国際会議 0.73
Insights and applications. (AISTATS’20), pages 983–992, 2020. 洞察と応用。 (AISTATS’20) 983-992, 2020。 0.66
[11] Kimon Fountoulakis, Di Wang, and Shenghao Yang. 11]kimon fountoulakis、di wang、shenghao yang。 0.42
p-norm flow diffusion for local graph clustering. 局所グラフクラスタリングのためのpノルムフロー拡散 0.76
In 37th International Conference on Machine Learning (ICML’20), pages 3222–3232, 2020. 院 37th International Conference on Machine Learning (ICML’20), page 3222–3232, 2020 0.64
[12] Alexander J. Alexander J (複数形 Alexander Js) 0.59
Gates and Yong-Yeol Ahn. Gates and Yong-Yeol Ahn 0.89
The impact of random models on clustering similarity. ランダムモデルがクラスタリングの類似性に与える影響。 0.81
The Journal of Machine Learning Research, 18(1):3049–3076, 2017. Journal of Machine Learning Research, 18(1):3049–3076, 2017 0.60
[13] Changwei Hu, Piyush Rai, and Lawrence Carin. [13]Changwei Hu、Piyush Rai、Lawrence Carin。 0.64
Deep generative models for relational data with side information. サイド情報を含む関係データの深い生成モデル。 0.80
In 34th International Conference on Machine Learning (ICML’17), pages 1578–1586, 2017. 第34回機械学習国際会議(ICML'17)において、1578-1586頁。 0.74
[14] Steinar Laenen and He Sun. 14] シュタイナール・ラーネンと 彼は太陽を照らしました 0.64
Higher-order spectral clustering of directed graphs. 有向グラフの高次スペクトルクラスタリング 0.62
In 34th Advances in Neural Information Processing Systems (NeurIPS’20), 2020. 34世紀に入ると ニューラル情報処理システム(NeurIPS'20)、2020年。 0.72
[15] Angsheng Li and Pan Peng. [15]Angsheng LiとPan Peng。 0.73
Detecting and characterizing small dense bipartite-like subgraphs by the bipartiteness ratio measure. 2成分比測定による密度密度の小さい2成分状サブグラフの検出と特徴付け 0.52
In 24th International Symposium on Algorithms and Computation (ISAAC’13), pages 655–665, 2013. 第24回アルゴリズムと計算に関する国際シンポジウム (ISAAC'13) において、2013年655-665頁。 0.72
[16] Meng Liu and David F. Gleich. 16]Meng LiuとDavid F. Gleich。 0.75
Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering. 半教師付き学習と局所グラフクラスタリングのための強局所pノルムカットアルゴリズム 0.59
In 34th Advances in Neural Information Processing Systems (NeurIPS’20), 2020. The 34th Advances in Neural Information Processing Systems (NeurIPS’20, 2020)。 0.82
[17] L´aszl´o Lov´asz and Mikl´os Simonovits. [17] L ́aszl ́o Lov ́asz and Mikl ́os Simonovits 0.64
The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume. マルコフ連鎖の混合速度、等尺不等式、体積の計算。 0.46
In 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS’90), pages 346–354, 1990. 第31回IEEE Symposium on Foundations of Computer Science (FOCS’90)において、346–354, 1990。 0.83
[18] Edward D. Mansfield, Helen V. Milner, and B. Peter Rosendorff. 18] エドワード・d・マンスフィールド、ヘレン・v・ミルナー、b・ピーター・ローゼンドルフ 0.66
Why democracies cooperate more: Electoral control and international trade agreements. 民主主義がより協力する理由: 選挙管理と国際貿易協定。 0.74
International Organization, 56(3):477–513, 2002. 国際機関, 56(3):477-513, 2002 0.88
[19] Zeev Maoz, Paul L. Johnson, Jasper Kaplan, Fiona Ogunkoya, and Aaron P. Shreve. [19]Zeev Maoz、Paul L. Johnson、Jasper Kaplan、Fiona Ogunkoya、Aaron P. Shreve。 0.74
The dyadic militarized interstate disputes (MIDs) dataset version 3.0: Logic, characteristics, and comparisons to alternative datasets. dyadic militarized interstate disputes (mids) dataset version 3.0: logic, characteristics, and comparisons to alternative datasets。 0.76
Journal of Conflict Resolution, 63(3):811–835, 2019. Journal of Conflict Resolution, 63(3):811–835, 2019 0.93
Accessed: January 2021. 2021年1月 - 開局。 0.52
[20] Philippe Martin, Thierry Mayer, and Mathias Thoenig. Philippe Martin氏、Thierry Mayer氏、Mathias Thoenig氏。 0.57
Make trade not war? 貿易は戦争ではない。 0.69
The Review of Economic Studies, 75(3):865–900, 2008. 経済の見返り 研究, 75(3):865-900, 2008。 0.70
[21] Aditya Krishna Menon and Charles Elkan. アディティア・クリシュナ・メノンとチャールズ・エルカン。 0.56
Link prediction via matrix factorization. 行列分解によるリンク予測。 0.61
In Machine Learning and Knowledge Discovery in Databases, pages 437–452, 2011. 機械学習では and Knowledge Discovery in Databases, page 437–452, 2011 0.83
[22] Cristopher Moore, Xiaoran Yan, Yaojia Zhu, Jean-Baptiste Rouquier, and Terran Lane. [22]Cristopher Moore、Xiaoran Yan、Yaojia Zhu、Jean-Baptiste Rouquier、Terran Lane。 0.74
Active learning for node classification in assortative and disassortative networks. assortative and disassortative networkにおけるノード分類のためのアクティブラーニング 0.82
In 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’11), pages 841–849, 2011. 第17回ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’11, 841–849, 2011)。 0.79
[23] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. [23]Hongbin Pei、Bingzhe Wei、Kevin Chen-Chuan Chang、Yu Lei、Bo Yang。 0.73
Geom-GCN: Geometric Graph Convolutional Networks. Geom-GCN:Geometric Graph Convolutional Networks 0.87
In 7th International Conference on Learning Representations (ICLR’19), 2019. 第7回国際学習表現会議(ICLR’19)に参加。 0.66
[24] Daniel A Spielman and Shang-Hua Teng. [24]Daniel A SpielmanとShang-Hua Teng。 0.89
A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. 大規模グラフの局所クラスタリングアルゴリズムとほぼ線形時間グラフ分割への応用 0.67
SIAM Journal on Computing (SICOMP), 42(1):1–26, 2013. siam journal on computing (sicomp), 42(1):1–26, 2013年。 0.84
[25] Yuuki Takai, Atsushi Miyauchi, Masahiro Ikeda, and Yuichi Yoshida. [25]高井裕、宮内篤、池田正弘、吉田雄一 0.45
Hypergraph clustering based on pagerank. pagerankに基づくハイパーグラフクラスタリング。 0.77
In 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’20), pages 1970–1978, 2020. 第26回ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’20)において、1970-1978, 2020。 0.83
14 14 0.85
英語(論文から抽出)日本語訳スコア
[26] V. A. Traag and Jeroen Bruggeman. 26] v. a. traag and jeroen bruggeman. 0.76
Community detection in networks with positive and negative links. 正および負のリンクを持つネットワークにおけるコミュニティ検出 0.82
Physical Review E, 80(3):036115, 2009. フィジカル・レビュー E, 80(3):036115, 2009 0.75
[27] Luca Trevisan. 27] ルカ・トレビサン 0.53
Max cut and the smallest eigenvalue. 最大カットと最小の固有値。 0.74
SIAM Journal on Computing (SICOMP), 41(6):1769– SIAM Journal on Computing (SICOMP), 41(6):1769– 0.91
1786, 2012. 1786, 2012. 0.85
[28] U.S. Census Bureau. [28]米国国勢調査局 0.65
United states 2000 census. 2000年アメリカ合衆国国勢調査。 0.60
https://web.archive. org/ https://web.archive. org/ 0.43
web/20150905081016/h ttps://www.census.go v/population/www/cen 2000/ commuting/, 2000. web/20150905081016/h ttps://www.census.go v/population/www/cen 2000/ commuting/, 2000 0.37
Accessed: January 2021. 2021年1月 - 開局。 0.52
[29] Di Wang, Kimon Fountoulakis, Monika Henzinger, Michael W. Mahoney, and Satish Rao. [29]Di Wang, Kimon Fountoulakis, Monika Henzinger, Michael W. Mahoney, Satish Rao。 0.80
Capacity In 34th International Conference on Machine Learning 第34回機械学習国際会議参加報告 0.70
releasing diffusion for speed and locality. 速度と局所性のために拡散を放出します 0.63
(ICML’17), pages 3598–3607, 2017. (ICML'17), page 3598–3607, 2017。 0.83
[30] Hao Yin, Austin R Benson, Jure Leskovec, and David F Gleich. Hao Yin氏、Austin R Benson氏、Jure Leskovec氏、David F Gleich氏。 0.64
Local higher-order graph clustering. 局所的な高階グラフクラスタリング。 0.66
In 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’17), pages 555–564, 2017. 第23回ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’17), page 555–564, 2017 0.81
[31] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. [31]Jong Zhu、Yujun Yan、Lingxiao Zhao、Mark Heimann、Leman Akoglu、Danai Koutra。 0.65
Beyond homophily in graph neural networks: Current limitations and effective designs. グラフニューラルネットワークにおけるホモフィリーを超えて:現在の制限と効果的な設計。 0.61
In 34th Advances in Neural Information Processing Systems (NeurIPS’20), 2020. The 34th Advances in Neural Information Processing Systems (NeurIPS’20, 2020)。 0.82
[32] Zeyuan Allen Zhu, Silvio Lattanzi, and Vahab Mirrokni. [32]Zeyuan Allen Zhu, Silvio Lattanzi, Vahab Mirrokni。 0.71
A local algorithm for finding well-connected ウェルコネクテッド探索のための局所アルゴリズム 0.71
clusters. In 30th International Conference on Machine Learning (ICML’13), pages 396–404, 2013. クラスタ。 第30回機械学習国際会議(ICML'13)にて、396-404頁。 0.65
A Omitted detail from Section 3 第3節の省略された詳細 0.66
In this section, we present all the omitted details from Section 3 of our paper. 本項では, 本論文第3節の省略された詳細について述べる。 0.72
We formally introduce the Lov´asz-Simonovits curve and use it to analyse the performance of the LocBipartDC algorithm for undirected graphs. 公式な Lov ́asz-Simonovits 曲線を導入し,無向グラフに対する LocBipartDC アルゴリズムの性能解析に利用する。 0.79
The Lov´asz-Simonovits Curve. Lov ́asz-Simonovits Curve 0.72
Our analysis of the LocBipartDC algorithm is based on the Lov´aszSimonovits curve, which has been used extensively in the analysis of local clustering algorithms [4, 32]. LocBipartDCアルゴリズムの解析はLov ́aszSimonovits曲線に基づいており、局所クラスタリングアルゴリズム [4, 32] の解析に広く用いられている。 0.75
Lov´asz and Simonovits [17] originally defined the following function to reason about the mixing rate of Markov chains. Lov ́asz と Simonovits [17] は当初、マルコフ連鎖の混合速度を推論するために以下の関数を定義した。 0.67
For any vector p ∈ Rn≥0, we order the vertices such that ≥ p(v2) deg(v2) 任意のベクトル p ∈ Rn≥0 に対して、 ≥ p(v2) deg(v2) となるような頂点を順序付ける。 0.74
p(v1) deg(v1) j = {v1, . p(v1) deg(v1) j = {v1, 。 0.85
. . , vj} for 1 ≤ j ≤ n. The Lov´asz-Simonovits curve, denoted by j ), and is linear between those points for . . , vj} for 1 ≤ j ≤ n. The Lov ́asz-Simonovits curve,marked by j ) and is linear between these points for these point. 0.86
and define the sweep sets of p as Sp p[x] for x ∈ [0, vol(V )], is defined by the points p[vol(Sp consecutive j. Lov´asz and Simonovits also show that そして、p のスイープ集合を x ∈ [0, vol(V )] に対して Sp p[x] として定義し、点 p[vol(Sp continuous j. Lov ́asz と Simonovits によって定義される。 0.85
≥ . . . ≥ p(vn) deg(vn) ≥ . . . ≥ p(vn) deg(vn) 0.85
, j )] (cid:44) p(Sp (cid:88) , j )] (cid:44) p(Sp (cid:88) 0.90
u∈V uhtmlv です。 0.22
w(u)p(u). w(u)p(u) である。 0.86
(2) (cid:80) Proof. (2) (cid:80) 証明。 0.81
By definition, we have that p(S) =(cid:80) 定義により、p(s) =(cid:80) となる。 0.79
p[x] = max w∈[0,1]n p[x] = 最大値 w ∈[0,1]n 0.81
u∈V w(u) deg(u)=x u・V w(u) deg(u)=x 0.81
Proposition 1. For any p ∈ Rn≥0 and any S ⊆ V , it holds that p(S) ≤ p[vol(S)] . 命題1。 任意の p ∈ Rn≥0 および任意の S ≤ V に対して、p(S) ≤ p[vol(S)] が成り立つ。 0.66
u∈V χS(u)p(u). p(u)p(u)p(u)。 0.52
Hence, by (2) we have that p(S) ≤ p[vol(S)]. したがって、(2) によって p(S) ≤ p[vol(S)] が成立する。 0.77
Double Cover Reduction. ダブルカバー・リダクション。 0.74
The following two proofs establish the reduction from almost-bipartite sets to sets with low conductance in the double cover and follow almost directly from the definition of the bipartiteness ratio and conductance. 以下の2つの証明は、二重被覆の低コンダクタンス集合に対するほぼ二分集合からの還元を確立し、二分比とコンダクタンスの定義からほぼ直接従うものである。 0.71
15 15 0.85
英語(論文から抽出)日本語訳スコア
Proof of Lemma 1. Lemma 1の証明。 0.65
Let S(cid:48) = L1 ∪ R2, and by definition we have that volG(S) = volH (S(cid:48)). S(cid:48) = L1 > R2 とし、定義により volG(S) = volH (cid:48) とする。 0.85
On the other hand, it holds that 一方、それはそうである。 0.47
volH (S(cid:48)) = eH (S(cid:48), V \ S(cid:48)) + 2eH (S(cid:48), S(cid:48)) = eH (S(cid:48), V \ S(cid:48)) + 2eH (L1, R2), volH (S(cid:48)) = eH (S(cid:48), V \ S(cid:48)) + 2eH (S(cid:48), S(cid:48)) = eH (S(cid:48), V \ S(cid:48)) + 2eH (L1, R2), 0.95
which implies that ΦH (S(cid:48)) = つまり シュH(S(cid:48)) = 0.50
eH (S(cid:48), V \ S(cid:48)) eH(S(cid:48),V \ S(cid:48) 0.95
volH (S(cid:48)) volH (S(cid:48)) 0.94
= volG(S) − 2eH (L1, R2) = volG(S) − 2eH (L1, R2) 0.90
volG(S) volG (複数形 volGs) 0.71
= 1 − 2eG(L, R) volG(S) = 1 − 2eG(L, R) volG(S) 0.91
= βG(L, R), = βG(L, R) 0.81
which proves the statement. Proof of Lemma 2. 声明を証明します Lemma 2の証明。 0.62
The statement follows by Lemma 1. この文はLemma 1によって従う。 0.49
The simplify operator. We now study the σ-operator to establish the properties given in Lemma 3. 簡単なオペレータ。 本稿では、 σ-作用素を lemma 3 で与えられる性質を確立するために研究する。 0.55
Recall that the lazy random walk matrix for a graph is defined to be W = 1 Proof of Lemma 3. グラフの遅延ランダムウォーク行列が W = 1 のLemma 3 の証明であると定義されていることを思い出してください。 0.62
For any u1 ∈ VH, we have by definition that 任意の u1 ∈ vh に対して、定義により 0.80
2 (I + D−1A). 2 (i + d−1a) である。 0.64
σ ◦ (c · p)(u1) = max(0, c · p(u1) − c · p(u2)) σ (c · p)(u1) = max(0, c · p(u1) − c · p(u2)) である。 0.95
= c · max(0, p(u1) − p(u2)) = c · σ ◦ p(u1), = c · max(0, p(u1) − p(u2)) = c · σ かつ p(u1) である。 0.96
and similarly we have σ ◦ (c · p)(u2) = c · σ ◦ p(u2). 同様に、 σ (c · p)(u2) = c · σ , p(u2) が存在する。 0.81
Therefore, the first property holds. したがって、最初の財産は保持される。 0.55
Now we prove the second statement. さて 2つ目の声明を証明します 0.59
Let u1, u2 ∈ VH be the vertices that correspond to u ∈ VG. u1, u2 ∈ VH を u ∈ VG に対応する頂点とする。 0.84
We have by definition that 我々は 定義によって 0.80
σ ◦ (a + b)(u1) = max(0, a(u1) + b(u1) − a(u2) − b(u2)) = max(0, a(u1) − a(u2) + b(u1) − b(u2)) ≤ max(0, a(u1) − a(u2)) + max(0, b(u1) − b(u2)) = σ ◦ a(u1) + σ ◦ b(u1), a + b)(u1) = max(0, a(u1) + b(u1) − b(u2)) = max(0, a(u1) − a(u2) + b(u2) − b(u2)) ≤ max(0, a(u1) − a(u2)) + max(0, b(u1) − b(u2)) = σ s a(u1) + σ s b(u1) 0.88
where the last inequality holds by the fact that max(0, x + y) ≤ max(0, x) + max(0, y) for any x, y ∈ R. For the same reason, we have that ここで、最後の不等式は、任意の x, y ∈ R に対して max(0, x + y) ≤ max(0, x) + max(0, y) であるという事実によって成り立つ。 0.86
σ ◦ (a + b)(u2) ≤ σ ◦ a(u2) + σ ◦ b(u2). σ(a + b)(u2) ≤ σ(u2) + σ(u2) + σ(u2) である。 0.85
Combining these proves the second property of σ. これらを組み合わせることで、σ の第二の性質が証明される。 0.48
Finally, we will prove the third property. 最後に、第3のプロパティを証明します。 0.66
By the definition of matrix W , we have that 行列 W の定義により、我々はそれを持つ。 0.69
and (pW )(u1) = そして (pW)(u1) = 0.83
(pW )(u2) = (pW)(u2) = 0.94
1 2 1 2 p(u1) + 1 2 1 2 p(u1) + 0.90
p(u2) + 1 2 p(u2) + 1 2 0.92
1 2 (cid:88) (cid:88) 1 2 (cid:88)(cid:88) 0.80
v∈NG(u) vvng (複数形 vvngs) 0.41
v∈NG(u) vvng (複数形 vvngs) 0.41
p(v2) degH (v2) p(v2) degH (v2) 0.98
p(v1) degH (v1) p(v1) degH (v1) 0.98
, . Without loss of generality, we assume that (pW )(u1) ≥ (pW )(u2). , . 一般性を失うことなく、 (pW )(u1) ≥ (pW )(u2) と仮定する。 0.84
This implies that (σ ◦ (pW ))(u2) = 0 ≤ ((σ ◦ p)W )(u2), hence it suffices to prove that (σ ◦ (pW ))(u1) ≤ ((σ ◦ p)W )(u1). したがって、 (σ ) (pW ))(u2) = 0 ≤ ((σ ) p)W )(u2) となるので、 (σ ) (pW ))(u1) ≤ ((σ ) p)W )(u1) であることを示すのに十分である。 0.90
By definition, we have that 定義上、我々はそれを持っている。 0.59
(σ ◦ (pW ))(u1) = max(0, pW (u1) − pW (u2)) (σ(pW))(u1) = max(0, pW(u1) − pW(u2)) 0.89
= pW (u1) − pW (u2) (p(u1) − p(u2)) + = pW (u1) − pW (u2) (p(u1) − p(u2)) + 1.00
= 1 2 = 1 2 = 1 2 = 1 2 0.85
(p(u1) − p(u2)) + (p(u1) − p(u2)) + 0.98
1 2 1 2 (cid:88) (cid:88) 1 2 1 2 (cid:88)(cid:88) 0.81
v∈NG(u) vvng (複数形 vvngs) 0.41
v∈NG(u) vvng (複数形 vvngs) 0.41
(cid:18) p(v2) (cid:18)p(v2) 0.84
degH (v2) p(v2) − p(v1) degH (v2) p(v2) − p(v1) 0.97
degG(v) (cid:19) degG(v) (cid:19) 0.82
− p(v1) degH (v1) -p(v1) degH (v1) 0.94
, (3) where the last line follows by the fact that degH (v1) = degH (v2) = degG(v) for any v ∈ VG. , (3) 最後の直線は、任意の v ∈ VG に対して degH (v1) = degH (v2) = degG(v) であるという事実に従う。 0.85
To analyse (3), notice that p(v1) − p(v2) = (σ ◦ p)(v1) − (σ ◦ p)(v2) for any v ∈ VG for the following reasons: (3) を解析するには、以下の理由から、任意の v ∈ vg に対して p(v1) − p(v2) = (σ ) p(v1) − (σ ) p)(v2) に注意する。 0.85
16 16 0.85
英語(論文から抽出)日本語訳スコア
• When p(v1) ≥ p(v2), we have that (σ ◦ p)(v1) − (σ ◦ p)(v2) = (p(v1) − p(v2)) − 0 = p(v1) − p(v2); • Otherwise, we have p(v1) < p(v2) and (σ ◦ p)(v1)− (σ ◦ p)(v2) = 0− (p(v2)− p(v1)) = p(v1)− p(v2). • p(v1) ≥ p(v2) のとき、(σ ) p)(v1) − (σ ) p)(v2) = (p(v1) − p(v2)) − 0 = p(v1) − p(v2); • でなければ、p(v1) < p(v2) と (σ ) p)(v1)− (σ ) p)(v2) = 0− (p(v2)− p(v1)) = p(v1)− p(v2) となる。 0.94
Therefore, we can rewrite (3) as (σ ◦ (pW ))(u1) = したがって、(3) を (σ ) (pW ))(u1) = と書き直すことができる。 0.81
1 2 ((σ ◦ p)(u1) − (σ ◦ p)(u2)) + 1 2 ((σ , p)(u1) − (σ , p)(u2)) + 0.88
(σ ◦ p)(v2) − (σ ◦ p)(v1) (σ ) p)(v2) − (σ ) p)(v1) 0.91
degG(v) (cid:88) degG(v) (cid:88) 0.82
1 2 v∈N (u) 1 2 vvn (複数形 vvns) 0.66
(cid:88) v∈N (u) (cid:88) vvn (複数形 vvns) 0.62
(σ ◦ p)(v2) degG(v) (σ ) p)(v2) degG(v) 0.89
≤ 1 2 · (σ ◦ p)(u1) + ≤ 1 2 ·(σ ) p)(u1) + 0.88
1 2 = ((σ ◦ p)W )(u1), 1 2 = ((σ ) p)W )(u1) 0.83
where the inequality holds by the fact that (σ ◦ p)(u1) ≥ 0 and (σ ◦ p)(u2) ≥ 0 for any u ∈ VG. ここでの不等式は、任意の u ∈ VG に対して (σ ) p)(u1) ≥ 0 かつ (σ ) p)(u2) ≥ 0 であるという事実によって成り立つ。 0.76
Since the analysis above holds for any v ∈ VG, we have that σ ◦ (pW ) (cid:22) (σ ◦ p)W , which finishes the proof of the statement. 上記の解析は任意の v ∈ VG に対して成り立つので、 σ > (pW ) (cid:22) (σ > p)W が成り立つ。
訳抜け防止モード: 上記の解析は任意の v ∈ VG に対して成り立つからである。 σ > ( pW ) ( cid:22 ) ( σ > p)W, これはステートメントの証明を完了します。
0.80
Analysis of ApproximatePagerankD C. ApproximatePagerankD Cの解析 0.58
The following lemma shows that dcpush maintains that throughout the algorithm, [p1, p2] is an approximate Pagerank vector on the double cover with residual [r1, r2]. 以下の補題は dcpush がアルゴリズム全体を通して [p1, p2] が[r1, r2] の残差を持つ二重被覆上の近似ページランクベクトルであることを示している。 0.68
Lemma 8. Let p(cid:48) p(cid:48) = [p(cid:48) 第8回。 p(cid:48) p(cid:48) = [p(cid:48) 0.72
2 be the result of dcpush((u, i), p1, p2, r1, r2). 2 は dcpush((u, i), p1, p2, r1, r2) の結果である。 0.92
Let p = [p1, p2], r = [r1, r2], p = [p1, p2], r = [r1, r2] とする。 0.85
2, r(cid:48) 2] and r(cid:48) = [r(cid:48) 2, r(cid:48) 2] および r(cid:48) = [r(cid:48) 0.90
2]. Then, we have that 2]. そして、それです。 0.58
1 and r(cid:48) 1, r(cid:48) 1, r(cid:48) 1, r(cid:48) 0.86
1, p(cid:48) 1, p(cid:48) 0.92
1, p(cid:48) 1, p(cid:48) 0.92
Proof. After the push operation, we have 証明。 プッシュ操作の後、私たちは 0.69
p(cid:48) + prH (α, r(cid:48)) = p + prH (α, r). p(cid:48) + prH (α, r(cid:48)) = p + prH (α, r)。 0.95
p(cid:48) = p + αr(ui)χui r(cid:48) = r − r(ui)χui + (1 − α)r(ui)χuiW p(cid:48) = p + αr(ui)-ui r(cid:48) = r − r(ui)-ui + (1 − α)-r(ui)-uiW 0.92
where W is the lazy random walk matrix on the double cover of the input graph. ここで W は入力グラフの二重被覆上の遅延ランダムウォーク行列である。 0.68
Then we have p + prH (α, r) = p + prH (α, r − r(ui)χui) + prH (α, r(ui)χui) そして私たちは p + prH (α, r) = p + prH (α, r − r(ui)-ui) + prH (α, r(ui)-ui) 0.78
= p + prH (α, r − r(ui)χui) + [αr(u)χui + (1 − α)prH (α, r(u)χuiW )] = [p + αr(ui)χui] + prH (α, [r − r(ui)χui + (1 − α)r(ui)χuiW ]) = p(cid:48) + prH (α, r(cid:48)), p = p + prH (α, r − r(ui)) + [αr(ui)-ui + (1 − α)prH (α, r(u)-uiW )] = [p + αr(ui)-ui] + prH (α, [r − r(ui)-ui + (1 − α)-r(ui)-uiW ]) = p(cid:48) + prH (α, r(cid:48))) 0.84
where we use the fact that pr(α,·) is linear and that pr(α,·) が線型であることと 0.40
which follows from the fact that pr(α, s) = α(cid:80)∞ これは pr(α, s) = α(cid:80)∞ であるという事実に従う。 0.77
pr(α, s) = αs + (1 − α)pr(α, sW ), pr(α, s) = αs + (1 − α)pr(α, sW ) 0.83
t=0(1 − α)tsW t. t=0(1 − α)tsW t。 0.92
The following lemma shows the correctness and performance guarantee of the ApproximatePagerankD C 以下の補題は ApproximatePagerankD C の正確性と性能保証を示している。 0.71
algorithm. Lemma 9. アルゴリズム。 第9回。 0.64
For a graph G with double cover H and any v ∈ VG, ApproximatePagerankD C(v, α, ) runs in time O( 1 二重被覆 H と任意の v ∈ VG を持つグラフ G に対して、 ApproximatePagerankD C(v, α, s) は時間 O( 1) で走る。 0.79
α ) and computes p = aprH (α, χv1, r) such that maxu∈VH p = aprH (α, sv1, r) を最大 VH で計算する。 0.64
deg(u) <  and vol(supp(p))) ≤ 1 α. deg(u) < s と vol(supp(p)) ≤ 1 sα である。 0.85
r(u) Proof. By Lemma 8, we have that p = aprH (α, χv1, r) throughout the algorithm and so this clearly holds for the output vector. r(u) 証明。 Lemma 8 により、アルゴリズム全体で p = aprH (α, sv1, r) を持つので、これは出力ベクトルに対して明らかに成り立つ。 0.76
By the stopping condition of the algorithm, it is clear that maxu∈VH アルゴリズムの停止条件により、maxu・VHは明らかである。 0.69
Let T be the total number of push operations performed by ApproximatePagerankD C, and let dj be the degree of the vertex ui used in the jth push. T を ApproximatePagerankD C によって実行されるプッシュ操作の総数とし、dj を jth プッシュで使用される頂点 ui の次数とする。 0.72
The amount of probability mass on ui at time j is at least dj and so the amount of probability mass that moves from ri to pi at step j is at least αdi. 時間 j における ui 上の確率質量の量は少なくとも dj であり、したがってステップ j において ri から pi に移動する確率質量の量は少なくとも α/di である。 0.74
Since (cid:107)r1(cid:107) 1 +(cid:107)r2(cid:107) 1 = 1 (cid:107)r1(cid:107) 1 +(cid:107)r2(cid:107) 1 = 1 なので 0.71
deg(u) < . deg(u) < s である。 0.85
r(u) at the beginning of the algorithm, we have that α(cid:80)T T(cid:88) r(u) アルゴリズムの開始時点では、 α\(cid:80)t t(cid:88) が成立する。 0.82
j=1 dj ≤ 1, which implies that j=1 dj ≤ 1 ということは 0.92
. (4) dj ≤ 1 α . (4) dj ≤ 1 α 0.84
j=1 17 j=1 17 0.72
英語(論文から抽出)日本語訳スコア
err 翻訳エラー 0.00
英語(論文から抽出)日本語訳スコア
where the first line follows by the definition of the approximate Pagerank, the second line follows by the definition of the Pagerank, and the last two inequalities follow by Lemma 3. 1行目が近似ページランクの定義に従えば、2行目はページランクの定義に従い、最後の2つの不等式は補題3に従う。
訳抜け防止モード: 最初の行が近似ページランクの定義に従う場合 2行目はページランクの定義に従っている。 そして、最後の2つの不等式は lemma 3 によって従う。
0.70
This proves the first inequality, and the second inequality follows by symmetry. これは第一の不等式を証明し、第二の不等式は対称性によって従う。 0.49
We now turn our attention to the Lov´asz-Simonovits curve defined by the simplified approximate Pagerank vector p = σ ◦ apr(α, s, r). 我々は、単純化された近似ページランクベクトル p = σ × apr(α, s, r) によって定義される lov ́asz-simonovits curve に注意を向ける。 0.65
We will bound the curve at some point by the conductance of the corresponding sweep set with the following lemma. 曲線は、次の補題で対応するスイープ集合のコンダクタンスによって、ある点で束縛される。 0.60
Lemma 10. Let p = σ ◦ (apr(α, s, r)). 背番号10。 p = σ > (apr(α, s, r)) とする。 0.60
It holds for any j ∈ [1, n − 1] that これは任意の j ∈ [1, n − 1] に対して成り立つ。 0.79
+ (1 − α) vol(Sp + (1 − α) vol(Sp) 0.88
(cid:104) (cid:16) (cid:104) (cid:16) 0.78
p 1 2 j ) −(cid:12)(cid:12)(cid :12)∂(Sp p 1 2 j ) −(cid:12)(cid:12)(cid :12)∂(Sp) 0.84
j ) (cid:12)(cid:12)(cid :12)(cid:105)(cid:17 ) j)。 (cid:12)(cid:12)(cid :12)(cid:105)(cid:17 ) 0.77
+ (1 − α) (cid:16) + (1 − α) (cid:16) 0.82
p 1 2 (cid:104) p 1 2 (cid:104) 0.83
vol(Sp j ) + vol(Sp) j ) + 0.88
(cid:12)(cid:12)(cid :12)∂(Sp (cid:12)(cid:12)(cid :12)∂(Sp) 0.75
j ) (cid:12)(cid:12)(cid :12)(cid:105)(cid:17 ) j)。 (cid:12)(cid:12)(cid :12)(cid:105)(cid:17 ) 0.77
. (cid:105) . (cid:105) 0.82
(cid:104) (cid:16) (cid:104)(cid:16) 0.73
(cid:104) p ≤α (cid:104) p ≤α 0.83
vol(Sp j ) vol(Sp j ) 0.85
s vol(Sp j ) s vol(Sp j ) 0.85
(cid:105) (cid:104) j ) ±(cid:12)(cid:12)(cid :12)∂(Sp (cid:105) (cid:104) j ) ±(cid:12)(cid:12)(cid :12)∂(Sp) 0.78
+ r (cid:105)(cid:17) (cid:12)(cid:12)(cid :12) = vol(Sp +r (cid:105)(cid:17) (cid:12)(cid:12)(cid :12) = vol(Sp) 0.74
vol(Sp j ) vol(Sp j ) 0.85
Since vol(Sp vol (複数形 vols) 0.55
j )), this tells us that when the conductance of the sweep set Sp j is large, the Lov´asz-Simonovits curve around the point vol(Sp j ) is close to a straight line. これは、スイープ集合 Sp j のコンダクタンスが大きいとき、点 vol(Sp j ) の周りの Lov ́asz-Simonovits 曲線が直線に近いことを示している。 0.69
For the proof of Lemma 10, we will view the undirected graph H instead as a digraph, and each edge {u, v} ∈ EH as a pair of directed edges (u, v) and (v, u). Lemma 10 の証明については、グラフの代わりに無向グラフ H をダイグラフとして、各辺 {u, v} ∈ EH を (u, v) と (v, u) の対として見る。 0.71
For any edge (u, v) and vector p ∈ R2n≥0, let 任意の辺 (u, v) とベクトル p ∈ R2n≥0 に対して、 0.74
j ) j )(1 ± Φ(Sp j)。 j)(1 ± )(Sp) 0.85
and for a set of directed edges A, let そして、一組の有向エッジ A に対して、 0.71
p(A) = p(u, v). p(A) = p(u, v) である。 0.83
p(u, v) = p(u) d(u) p(u, v) = p(u) d(u) 0.85
(cid:88) (u,v)∈A (cid:88) (u,v)大A 0.72
Now for any set of vertices S ⊂ VH, let in(S) = {(u, v) ∈ EH : v ∈ S} and out(S) = {(u, v) ∈ EH : u ∈ S}. 任意の頂点 S に対して、in(S) = {(u, v) ∈ EH : v ∈ S} とout(S) = {(u, v) ∈ EH : u ∈ S} とする。 0.77
Additionally, for any simple set S ⊂ VH, we define the “simple complement” of the set S by さらに、任意の単純集合 S > VH に対して、集合 S の「単純補集合」を S によって定義する。 0.71
(cid:98)S = {u2 : u1 ∈ S} ∪ {u1 : u2 ∈ S}. (cid:98)S = {u2 : u1 ∈ S} > {u1 : u2 ∈ S} である。 0.83
We will need the following property of the Lov´asz-Simonovitz curve with regard to sets of edges. エッジの集合に関して、Lov ́asz-Simonovitz曲線の以下の性質が必要である。 0.71
Lemma 11. For any set of edges A, it holds that 背番号11。 任意の辺 a に対して、それを保持する 0.56
p(A) ≤ p[|A|] . p(A) ≤ p[|A|] である。 0.91
Proof. For each u ∈ V , let xu = |{(u, v) ∈ A}| be the number of edges in A with the tail at u. 証明。 各 u ∈ V に対して、xu = |{(u, v) ∈ A}| を a の尾を持つ A の辺の数とする。 0.70
Then, we have by definition that そして、その定義により、 0.68
Since xu d(u) ∈ [0, 1] and xu 以降 d(u) ∈ [0, 1] と 0.76
p(A) = (cid:88) p(A) = (cid:88) 0.82
u∈V uhtmlv です。 0.22
(cid:88) p(u) d(u) (cid:88) p(u) d(u) 0.82
(u,v)∈A = (cid:88) (cid:88) (u,v)大A = (cid:88)(cid:88) 0.75
u∈V uhtmlv です。 0.22
u∈V uhtmlv です。 0.22
xu d(u) d(u) = xu d(u) d(u) = 0.85
xu = |A| , xu = |A| , 0.84
xu d(u) p(u) xu d(u) p(u) 0.85
the statement follows from equation (2). この記述は等式(2)から従う。 0.67
We will also make use of the following lemma from [4]. また、[4]から次の補題も利用します。 0.58
Lemma 12 ([4], Lemma 4). Lemma 12 ([4], Lemma 4)。 0.66
For any distribution p, and any set of vertices A, 任意の分布 p, および任意の頂点 A, に対して 0.88
pW (A) ≤ 1 2 pW (A) ≤ 1 2 0.85
· (p(in(A) ∪ out(A)) + p(in(A) ∩ out(A))) ·(p(in(A) ) out(A)) + p(in(A) ) out(A)) 0.77
We now have all the pieces we need to prove the behaviour of the Lov´asz-Simonovits curve described in Lov ́asz-Simonovits曲線の振舞いを証明するために必要な全てのピースがある。 0.71
Lemma 10. 19 背番号10。 19 0.67
英語(論文から抽出)日本語訳スコア
α (s(u1) + r(u2)) + (1 − α)(pW )(u1) α(s(u1) + r(u2)) + (1 − α)(pW )(u1) 0.95
α (s(u2) + r(u1)) + (1 − α)(pW )(u2) α(s(u2) + r(u1)) + (1 − α)(pW )(u2) 0.95
(cid:16) (cid:17) (cid:88) (cid:88) (cid:16) (cid:17) (cid:88) (cid:88) 0.76
u2∈S + (cid:33) u2htmls + (cid:33) 0.65
u2∈S (cid:32) (cid:88) u2htmls (cid:32)(cid:88) 0.52
u1∈S (cid:17) (cid:88) u1図 (cid:17)(cid:88) 0.55
u2∈S (cid:33) u2htmls (cid:33) 0.55
Proof of Lemma 10. By definition, we have that レンマ10の証明。 定義上、我々はそれを持っている。 0.55
p(u1) + p(u2) p(u1) + p(u2) 0.99
p(S) = u1∈S p(S) = u1図 0.69
(cid:88) (cid:16) ≤ (cid:88) (cid:32) (cid:88) = α ·(cid:16) ≤ α ·(cid:16) (cid:88) (cid:16) ≤ (cid:88) (cid:32) (cid:88) = α ·(cid:16) ≤ α ·(cid:16) 0.79
u1∈S = α · u1htmls = α · 0.56
u1∈S s(S) + r u1図 s(S) + r 0.61
s(S) + r (cid:88) s(S) + r (cid:88) 0.82
u2∈S (cid:88) (cid:16)(cid:98)S (cid:17)(cid:17) (cid:17)(cid:17) (cid:16)(cid:98)S (cid:104) u2htmls (cid:88) (cid:16)(cid:98)S (cid:17)(cid:17) (cid:17)(cid:17) (cid:16)(cid:98)S (cid:104) 0.52
(cid:88) ·(cid:16) (cid:88)·(cid:16) 0.76
u1∈S u2∈S + (1 − α) · pW (S) + (1 − α) · 1 2 u1図 u2∂S + (1 − α) · pW (S) + (1 − α) · 1 2 0.63
(cid:105) s(u1) + (cid:105) s(u1) + 0.89
s(u2) + r(u2) + s(u2) + r(u2) + 0.99
r(u1) (pW )(u1) + r(u1) (pW)(u1)+ 0.95
(pW )(u2) + (1 − α) · (pW)(u2) + (1 − α) · 0.90
where the first inequality follows by Lemma 5 and the last inequality follows by Lemma 12. 最初の不等式はLemma 5で、最後の不等式はLemma 12で従う。 0.57
Now, recall that p さて、それを思い出してください。 0.32
vol(Sp j ) vol(Sp j ) 0.85
= p(Sp j ) and notice that vol = p(Sp) j) その点に気付きます 0.81
= vol Sp j = vol Sp j 0.85
Hence, using Lemma 11, we have that したがって、Lemma 11 を使っています。 0.71
p(in(S) ∪ out(S)) + p(in(S) ∩ out(S)) p(in(S) > out(S)) + p(in(S) > out(S)) 0.77
, (cid:17) holds by the definition of (cid:98)S. , (cid:17)は (cid:98)S の定義によって保持される。 0.76
(cid:16) (cid:17) (cid:16) (cid:17) 0.78
(cid:17) (cid:16)(cid:99)Sp (cid:17) (cid:16)(cid:99)Sp 0.78
j (cid:104) j (cid:104) 0.82
(cid:105) vol(Sp j ) p = p(Sp j ) ≤ α s(Sp ≤ α (cid:105) vol(Sp j ) p = p(Sp j ) ≤ α s(Sp ≤ α) 0.84
(cid:16) (cid:16) (cid:16)(cid:16) 0.73
(cid:104) s (cid:104) s 0.82
j ) + r vol(Sp j ) j ) + r vol(Sp j ) 0.85
(cid:16)(cid:99)Sp (cid:105) (cid:16)(cid:99)Sp(c id:105) 0.76
j (cid:17)(cid:17) (cid:104) j (cid:17)(cid:17)(cid :104) 0.79
+ r It remains to show that +r 証拠は残っていますが 0.56
and (cid:16) そして (cid:16) 0.75
(cid:16) p (cid:16) p 0.82
in(Sp + (1 − α) · 1 2 in(Sp + (1 − α) · 1 2 0.85
j ) ∩ out(Sp j ) j ) は out(Sp j ) 0.76
j ) ∪ out(Sp j ) j ) ∩ out(Sp j ) j ) は out(Sp j ) j ) は out(Sp j ) 0.78
vol(Sp j ) vol(Sp j ) 0.85
+ (1 − α) · 1 2 + (1 − α) · 1 2 0.85
(cid:105)(cid:17) (cid:12)(cid:12)(cid :12)in(Sp (cid:12)(cid:12)(cid :12)in(Sp (cid:12)(cid:12)(cid :12)in(Sp (cid:12)(cid:12)(cid :12)in(Sp (cid:12)(cid:12)(cid :12) = (cid:105)(cid:17) (cid:12)(cid:12)(cid :12)in(sp(cid:12)(ci d:12)(cid:12)in(sp(c id:12)(cid:12)(cid:1 2)in(sp(cid:12)(cid: 12)(cid:12)in(sp(cid :12)(cid:12)(cid:12) = 0.75
p + p + p(in(Sp p +p + p(in(Sp) 0.86
(cid:12)(cid:12)(cid :12)(cid:105)(cid:17 ) (cid:12)(cid:12)(cid :12)(cid:105)(cid:17 ) 0.72
(cid:104)(cid:12)(ci d:12)(cid:12)in(Sp (cid:104)(cid:12)(ci d:12)(cid:12)in(Sp) 0.74
(cid:17) j ) ∩ out(Sp j )) j ) ∩ out(Sp j ) (cid:17) j ) > out(Sp j )) j ) > out(Sp j ) 0.75
(cid:17) (cid:104)(cid:12)(ci d:12)(cid:12)in(Sp (cid:16) j ) ∪ out(Sp j ) j ) ∪ out(Sp j ) (cid:12)(cid:12)(cid :12) = vol(Sp j ) −(cid:12)(cid:12)(cid :12)∂(Sp (cid:12)(cid:12)(cid :12)∂(Sp (cid:12)(cid:12)(cid :12) = vol(Sp (cid:12)(cid:12)(cid :12) counts precisely twice the number of edges with both (cid:12)(cid:12)(cid :12)in(Sp (cid:12)(cid:12)(cid :12) + (cid:17) (cid:104)(cid:12)(ci d:12)(cid:12)(cid:12 )(cid:12)(cid:12))in (Sp (cid:16) j ) s out(Sp j ) (cid:12)(cid:12) = vol(Sp j ) −(cid:12)(cid:12)(cid :12)(cid:12)(cid:12) (cid:12)(cid:12)(cid :12) = vol(Sp(cid:12)(cid:1 2)(cid:12)(cid:12)(c id:12) 両辺の倍の数をカウントする。 0.96
(cid:12)(cid:12)(cid :12)(cid:105) (cid:12)(cid:12)(cid :12) , (cid:12)(cid:12)(cid :12) . (cid:12)(cid:12)(cid :105) (cid:12)(cid:12)(cid :12) , (cid:12)(cid:12)(cid :12) 。 0.78
(cid:12)(cid:12)(cid :12) + (cid:12)(cid:12)(cid :12)out(Sp (cid:12)(cid:12)(cid :12). (cid:12)(cid:12)(cid :12) + (cid:12)(cid:12)(cid :12)out(Sp(cid:12)(c id:12)(cid:12)) 0.75
(cid:12)(cid:12)(cid :12)∂(Sp (cid:12)(cid:12)(cid :12)∂(Sp) 0.75
j ) \ out(Sp j ) j ) \out(Sp j ) 0.82
j ) \ in(Sp j ) j ) \ in(Sp j ) 0.85
j ) + (cid:12)(cid:12)(cid :12) j ) + (cid:12)(cid:12)(cid :12) 0.79
j ) j ) j ) j)。 j)。 j)。 0.81
. The first follows by noticing that endpoints inside Sp . 最初はsp内のエンドポイントに気付くことで続きます。 0.69
(cid:12)(cid:12)(cid :12)in(Sp (cid:12)(cid:12)(cid :12)in(Sp) 0.75
j . The second follows since j ) ∪ out(Sp j ) j.j. 第二は j ) が out(sp j ) であることから従う。 0.63
j ) ∩ out(Sp j ) j ) は out(Sp j ) 0.76
and both the second and third terms on the right hand side are equal to 右辺の第2項と第3項は 0.43
To understand the following lemma, notice that since p[0] = 0 and p[vol(H)] = 1, if the curve were simply linear then it would be the case that p[k] = k vol(H) and so the following lemma bounds how far the Lov´asz-Simonovits curve deviates from this line. 以下の補題を理解するためには、p[0] = 0 と p[vol(H)] = 1 が単に線型であるなら、p[k] = k vol(H) が成り立つので、次の補題は Lov ́asz-Simonovits 曲線がこの直線からどれだけ離れているかに注意する。 0.76
In particular, if there is no sweep set with small conductance, then the deviation must be small. 特に、小さなコンダクタンスを持つスイープ集合が存在しない場合、偏差は小さくなければならない。
訳抜け防止モード: 特に、小さなコンダクタンスを持つスイープセットがない場合は、 そして、その偏差は小さくなければならない。
0.67
Lemma 13. Let p = σ ◦ (aprH (α, s, r)) such that maxu∈VH Φ(Sp 背番号13。 p = σ (aprH (α, s, r)) {\displaystyle p=σ (prH (α, s, r)) 0.60
d(u) ≤ , and φ be any constant in [0, 1]. d(u) ≤ s であり、 φ は [0, 1] 内の任意の定数である。 0.79
If j ) ≥ φ for all j ∈ [1,|supp(p)|], then もしも j ) ≥ φ for all j ∈ [1,|supp(p)|], then 0.64
r(u) p[k] − k r(u) p[k] − k 0.85
vol(H) vol (複数形 vols) 0.55
≤ αt + αkt +(cid:112)min(k, vol(H) − k) ≤ αt + α\kt +(cid:112)min(k, vol(H) − k) 0.94
(cid:18) 1 − φ2 8 (cid:18) 1 − φ2 8 0.88
(cid:19)t for all k ∈ [0, vol(H)] and integer t ≥ 0. (cid:19)t すべての k ∈ [0, vol(H)] および整数 t ≥ 0 に対して。 0.86
20 20 0.85
英語(論文から抽出)日本語訳スコア
Proof. For ease of discussion we write kj = vol(Sp will write 証明。 議論の容易さのために、我々はkj = vol(sp が書く)を書く。 0.61
ft(k) = αt + αkt +(cid:112)min(k, vol(H) − k) ft(k) = αt + α\kt +(cid:112)min(k, vol(H) − k) 0.97
We will prove by induction that for all t ≥ 0, 帰納法によってすべての t ≥ 0 に対して証明する。 0.61
p[k] − k vol(H) p[k] − k vol (複数形 vols) 0.70
≤ ft(k). (cid:18) ≤ ft(k)。 (cid:18) 0.78
1 − φ2 8 (cid:19)t 1 − φ2 8 (cid:19)t 0.91
. j ) and let kj = min(kj, vol(H) − kj). . j ) とし、kj = min(kj, vol(h) − kj) とする。 0.88
For convenience we For the base case, this equation holds for t = 0 for any φ. 便宜のために 基底の場合、この方程式は任意の φ に対して t = 0 に対して成り立つ。 0.62
Our proof is based on a case distinction: (1) For any integer k ∈ [1, vol(H) − 1], この証明はケースの区別に基づいている: (1) 任意の整数 k ∈ [1, vol(h) − 1] に対して。 0.84
p[k] − k ≤ 1 ≤(cid:112)min(k, vol(H) − k) ≤ f0(k); p[k] − k ≤ 1 ≤(cid:112)min(k, vol(h) − k) ≤ f0(k); 0.86
vol(H) = 0 ≤ f0(k). vol(H) = 0 ≤ f0(k)。 0.88
The base case follows since f0 is concave, and p[k] Now for the inductive case, we assume that the claim holds for t and will show that it holds for t + 1. f0 が凹凸であり、p[k] が帰納的の場合、この主張は t に対して成り立つと仮定し、それが t + 1 に対して成り立つことを示す。 0.60
It vol(H) (2) For k = 0 or k = vol(H), p[k] − k is linear between integer values. それ vol(H) (2) k = 0 または k = vol(H) の場合、p[k] − k は整数値間の線型である。 0.81
suffices to show that the following holds for every j ∈ [1,|supp(p)|]: ≤ ft+1(kj). 以下がすべての j ∈ [1,|supp(p)|]: ≤ ft+1(kj) に対して成り立つことを示すのに十分である。 0.87
p[kj] − kj p[kj] − kj 0.85
vol(H) vol (複数形 vols) 0.55
The theorem will follow because this equation holds trivially for j = 0 and j = n and p[k] is linear between kj for j ∈ {0, n} ∪ [1,|supp(p)|]. この定理は、この方程式が j = 0 に対して自明に成り立つことと、j = n に対して p[k] が j ∈ {0, n} に対して kj の間の線型であることから従う。 0.85
For any j ∈ [1,|supp(p)|], it holds by Lemma 10 that 任意の j ∈ [1,|supp(p)|] に対して、それは Lemma 10 によって成り立つ。 0.87
kj −(cid:12)(cid:12)(cid :12)∂(Sp (cid:12)(cid:12)(cid :12)(cid:105) (cid:104) (cid:16) (cid:105) (cid:104) p[kj] ≤ α (s[kj] + r[kj]) + (1 − α) 1 p 2 (cid:3)(cid:1) , (cid:3) + p(cid:2)kj + φkj j ) · kj kj − Φ(Sp kj − (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) (cid:105) (cid:104) (cid:16) (cid:105) (cid:104) p[kj] ≤ α (s[kj] + r[kj]) + (1 − α) 1 p 2 (cid:3) (cid:1) , (cid:3) + p(cid:2) kj + φkj j ) · kj kj − φ(sp) 0.93
(cid:16) (cid:104) (cid:0)p(cid:2)kj − φkj (cid:16) (cid:104) (cid:0)p(cid:2)kj − φkj 0.77
≤ α + αkj + ≤ α + αkj + ≤ α + α\kj + ≤ α + α\kj + 0.84
+ p j ) p kj + Φ(Sp +p j)。 p kj + s(Sp) 0.85
(cid:104) kj + j ) · kj (cid:104)kj+j)·kj 0.93
(cid:12)(cid:12)(cid :12)∂(Sp (cid:105)(cid:17) (cid:12)(cid:12)(cid :12)∂(sp(cid:105)(cid:17) 0.77
j ) (cid:12)(cid:12)(cid :12)(cid:105)(cid:17 ) j)。 (cid:12)(cid:12)(cid :12)(cid:105)(cid:17 ) 0.77
+ p 1 2 1 2 +p 1 2 1 2 0.81
where the second line uses the fact that r[kj] ≤ kj and the last line uses the concavity of p[k] and the fact that Φ(Sp 2行目は r[kj] ≤ shkj と最後の行が p[k] の凹凸と sh(Sp) が使われるという事実を用いる。 0.71
j ) ≥ φ. j ) ≥ φ である。 0.81
By the induction hypothesis, we have that 帰納仮説により、我々はそれを持っている。 0.45
(cid:18) p[kj] ≤ α + αkj + (cid:18) p[kj] ≤ α + α\kj + 0.88
1 2 = α + αkj + 1 2 = α + α\kj + 0.85
(cid:18)(cid:113) (cid:18)(cid:113) 0.75
+ 1 2 = α + αkj + αt + αkjt + + 1 2 = α + α-kj + αt + α-kjt + 0.82
ft(kj − φkj) + kj ft(kj − φkj) + kj 0.94
+ 1 2 vol(H) + 1 2 vol (複数形 vols) 0.75
+ ft(kj + φkj) + + ft(kj + φkj) + 0.94
kj − φkj vol(H) kj − φkj vol(H) 0.96
(cid:0)ft(kj + φkj) + ft(kj − φkj)(cid:1) (cid:113) (cid:0)ft(kj + φkj) + ft(kj − φkj)(cid:1) (cid:113) 0.87
vol(H) vol (複数形 vols) 0.55
kj (cid:19) kj (cid:19) 0.82
kj + φkj vol(H) kj + φkj vol(H) 0.96
(cid:19)(cid:18) (cid:19)(cid:18) 0.75
1 − φ2 8 (cid:19)t 1 − φ2 8 (cid:19)t 0.91
min(kj − φkj, vol(H) − kj + φkj) + min(kj − φkj, vol(H) − kj + φkj) + 0.95
min(kj + φkj, vol(H) − kj − φkj) min(kj + φkj, vol(H) − kj − φkj) 0.96
(cid:113) (cid:19)(cid:18) (cid:113) (cid:19)(cid:18) 0.77
(cid:19)t 1 − φ2 8 (cid:19)t 1 − φ2 8 0.91
≤ α(t + 1) + αkj(t + 1) + ≤ α(t + 1) + α\kj(t + 1) + 0.94
kj kj − φkj + kj kj − φkj + 0.92
kj + φkj Now, using the Taylor series of kj + φkj さて、Taylorシリーズを使って 0.82
(cid:16)(cid:112)x − φx +(cid:112)x + φx (cid:16)(cid:112)x − φx +(cid:112)x + φx) 0.76
1 2 vol(H) √ 1 + φ at φ = 0, we see the following for any x ≥ 0 and φ ∈ [0, 1]. 1 2 φ = 0 における vol(H) = 1 + φ は、任意の x ≥ 0 および φ ∈ [0, 1] に対して以下のようになる。 0.87
(cid:19) (cid:18) (cid:19) (cid:18) 0.78
+ 1 + φ 2 − φ2 8 + 1 + φ 2 − φ2 8 0.87
+ φ3 16 (cid:19)(cid:19) + φ3 16 (cid:19)(cid:19) 0.83
(cid:18)(cid:113) (cid:18)(cid:18) (cid:18) (cid:18)(cid:113) (cid:18)(cid:18) (cid:18) 0.72
+ 1 2 (cid:17) ≤ ≤ √ + 1 2 (cid:17) ≤ ≤ ) 0.84
√ x 2 x x 2 である。 x 0.71
1 − φ 2 (cid:19) 1 − φ 2 (cid:19) 0.82
− φ2 8 − φ3 16 − φ2 8 − φ3 16 0.94
. 1 − φ2 8 . 1 − φ2 8 0.92
21 21 0.85
英語(論文から抽出)日本語訳スコア
Letting v = vol(Hc) we set t = v = vol(Hc) とすると t = となる。 0.74
8 φ2 ln 2 v/2 δ 8 φ2 ln 2 v/2 δ 0.83
. Now, assuming that . さて、そう仮定して 0.70
δ < p[k] − δ < p[k] − 0.85
(cid:24) k (cid:24) k 0.82
vol(Hc) √ vol (複数形 vols) 0.58
(cid:25) < αt(1 + k) + (cid:25) < αt(1 + ]k) + 0.87
k we have δ < (1 + k)α k 我々は δ < (1 + sk)α 0.79
We set c such that (cid:38) 私たちはcを (cid:38) 0.66
2(cid:112)v/2 2(cid:112)v/2 0.71
δ 8 φ2 ln δ ≥ 2(cid:112)v/2 (cid:39) 2(cid:112)v/2 δ 8 φ2 ln δ ≥ 2(cid:112)v/2(cid:39 ) 2(cid:112)v/2 0.84
+ δ (cid:112) + δ (cid:112) 0.83
(5) + δ 2 9(1 + k)α ln(v/2) (5) + δ 2 9(1 + sk)α ln(v/2) 0.87
k < (cid:18) 4 k<i> (cid:18)4 0.67
δ φ2 (cid:19)2 δ φ2 (cid:19)2 0.82
Applying this with x = kj, we have これを x = kj で適用すれば、 0.78
p[kj] − kj p[kj] − kj 0.85
vol(H) vol (複数形 vols) 0.55
≤ α(t + 1) + αkj(t + 1) + ≤ α(t + 1) + α\kj(t + 1) + 0.94
= ft+1(kj), = ft+1(kj) 0.92
which completes the proof. (cid:113) 証明を完了させます (cid:113) 0.72
kj (cid:18) kj (cid:18) 0.82
1 − φ2 8 (cid:19)(cid:18) 1 − φ2 8 (cid:19)(cid:18) 0.86
1 − φ2 8 (cid:19)t 1 − φ2 8 (cid:19)t 0.91
The next lemma follows almost directly from Lemma 13 by carefully choosing the value of t. 次の補題は、t の値を慎重に選択することによって、ほとんど lemma 13 から直接従う。
訳抜け防止モード: 次の補題は、ほぼ直接的に補題13から続く t の値を慎重に選択する。
0.66
Proof of Lemma 6. Lemma 6の証明。 0.68
Let Hc be a weighted version of the double cover with the weight of every edge equal to some constant c. Let k = volHc(S) and k = min(k, vol(Hc) − k). Hc をすべての辺の重みが定数 c に等しい重み付きバージョンとし、k = volHc(S) と k = min(k, vol(Hc) − k とする。
訳抜け防止モード: hc を任意の辺の重さが定数 c に等しい二重被覆の重み付きバージョンとすると、k = volhc(s) とする。 そして k = min(k , vol(hc ) − k ) である。
0.76
Notice that the behaviour of random walks and the conductance of vertex sets are unchanged by re-weighting the graph by a constant factor. ランダムウォークの挙動と頂点集合の伝導性は、定数因子でグラフを再重み付けすることによって変化しないことに注意。 0.78
As such, p = σ ◦ aprHc(α, s, r) and we let φ = minj ΦHc(Sp したがって、p = σ > aprHc(α, s, r) であり、φ = minj >Hc(Sp) とする。 0.80
j ). Hence, by Lemma 13 it holds for any t > 0 that J)。 したがって、Lemma 13 では任意の t > 0 に対して成り立つ。 0.68
(cid:112) (cid:18) (cid:112) (cid:18) 0.78
(cid:19)t . (cid:19)t . 0.85
1 − φ2 8 which satisfies (5) and implies that 1 − φ2 8 (5)を満足させ 0.76
φ < 18(1 + k)α ln(4/δ) φ < 18(1 + sk)α ln(4/δ) 0.90
δ . v = c vol(H) = vol(Hc) = δ . v = c vol(H) = vol(Hc) = 0.85
(cid:114) By the definition of φ, there must be some Sp (cid:114) φ の定義により、ある sp が存在しなければならない 0.77
j with the desired property. j は所望のプロパティを持つ。 0.68
Finally, we prove the performance guarantees of Algorithm 1 in the following theorem. 最後に,アルゴリズム1の性能保証を次の定理で証明する。 0.70
Proof of Theorem 1. We set the parameters of the main algorithm to be 定理 1 の証明。 主アルゴリズムのパラメータを設定する。 0.58
• α = (cid:98)β2/378 = 20β • α = (cid:98)β2/378 = 20β 0.74
•  = 1/(20γ). •  = 1/(20γ). 0.96
Let p = σ ◦ (aprH (α, χv, r)) be the simplified approximate Pagerank vector computed in the algorithm, which d(v) ≤ , and let C(cid:48) = L1 ∪ R2 be the target set in the double cover. p = σ ′ (aprH (α, sv, r)) をアルゴリズムで計算された単純化された近似ページランクベクトルとし、d(v) ≤ ′ とし、C(cid:48) = L1 > R2 を二重被覆のターゲット集合とする。 0.83
Hence, by Lemma 4 satisfies that maxv∈VH we have that したがって、lemma 4 は maxv ajaxvh を満たす。 0.56
r(v) Notice that, since C(cid:48) is simple, we have that vol(C(cid:48)) r(v) c(cid:48) は単純であるため、vol(c(cid:48)) である。 0.79
p(C(cid:48)) ≥ 1 − 2β α p(C(cid:48)) ≥ 1 − 2β α 0.96
− 2 · vol(C) ≥ 1 − 1 10 vol(VH ) ≤ 1 p(C(cid:48)) − vol(C(cid:48)) 1 ≥ 1 − 1 10 vol(VH ) ≤ 1 p(C(cid:48)) − vol(C(cid:48)) 0.73
2 and ≥ 4 5 2 と ≥ 4 5 である。 0.73
− 1 2 vol(VH ) − 1 2 vol(VH) 0.84
= 3 10 . − 1 10 = 3 10 . − 1 10 0.85
= 4 5 . Therefore, by Lemma 6 and choosing δ = 3/10, there is some j ∈ [1,|supp(p)|] such that = 4 5 . したがって、Lemma 6 と δ = 3/10 を選択することにより、いくつかの j ∈ [1,|supp(p)|] が存在する。 0.83
(cid:114) 360 (cid:114)360 0.79
3 Φ(Sp j ) < 3 シュ(スプ) j) < 0.72
(1 + vol(C))α ln( (1 + svol(C))α ln( 0.83
) ≤ 40 3 22 ) ≤ 40 3 22 0.85
(cid:115)(cid:18) (cid:115)(cid:18) 0.75
(cid:19) 7200β = (cid:98)β. (cid:19) 7200β = (cid:98)β。 0.81
1 + 1 20 1 + 1 20 0.85
英語(論文から抽出)日本語訳スコア
Since such a Sp R(cid:48) = {u ∈ VG : u2 ∈ Sp そのようなSp R(cid:48) = {u ∈ VG : u2 ∈ Sp 0.95
j } satisfy β((, L)(cid:48), R(cid:48)) ≤ (cid:98)β. j は β((, l)(cid:48), r(cid:48)) ≤ (cid:98)β を満たす。 0.92
For the volume guarantee, Lemma 9 gives that j is a simple set, by Lemma 1, we know that the sets L(cid:48) = {u ∈ VG : u1 ∈ Sp 体積保証のために、Lemma 9 は j を単純集合とし、Lemma 1 により集合 L(cid:48) = {u ∈ VG : u1 ∈ Sp が成立する。 0.76
j } and Since the sweep set procedure in the algorithm is over the support of p, we have that j } と アルゴリズムのスイープセットプロシージャは p のサポートを超越しているので、我々はそれを持っている。
訳抜け防止モード: j } と アルゴリズムのスイープ集合の手続きは p のサポートを超越しているからである。 我々には
0.76
vol(L(cid:48) ∪ R(cid:48)) ≤ vol(supp(p)) ≤ β−1γ. vol(L(cid:48) > R(cid:48)) ≤ vol(supp(p)) ≤ β−1γ。 0.90
vol(supp(p)) ≤ 1 α vol(supp(p)) ≤ 1 である。 0.89
= γ β . Now, we will analyse the running time of the algorithm. = γ β . では、アルゴリズムの実行時間を分析します。 0.80
By Lemma 9, computing the approximate Pagerank vector p(cid:48) takes time lemma 9 による近似ページランクベクトル p(cid:48) の計算には時間がかかる 0.70
Since vol(supp(p(cid:48))) = O(cid:0) 1 (cid:1), computing σ ◦ (p(cid:48)) can also be done in time O(cid:0)β−1γ(cid:1). vol(supp(p(cid:48)) = O(cid:0) 1 (cid:1) であるため、時間 O(cid:0)β−1γ(cid:1) で計算することもできる。 0.85
The cost of checking each conductance in the sweep set loop is O(vol(supp(p)) ln(n)) = O(cid:0)β−1γ ln(n)(cid:1). スイープ集合ループの各コンダクタンスをチェックするコストは o(vol(supp(p)) ln(n)) = o(cid:0)β−1γ ln(n)(cid:1) である。 0.80
This dominates the = O(cid:0)β−1γ(cid:1) . これが支配する = O(cid:0)β−1γ(cid:1)。 0.71
α O α (cid:18) 1 α お α (cid:18)1 0.75
(cid:19) running time of the algorithm, which completes the proof of the theorem. (cid:19) アルゴリズムの実行時間です 定理の証明を完了します 0.68
B Omitted detail from Section 4 b 第4節による詳細 0.81
In this section, we present all the omitted details from Section 4 of our paper. 本項では, 本論文第4節の省略された詳細について述べる。 0.72
We will use the evolving set process to analyse the correctness and performance of the EvoCutDirected algorithm. 我々はevocutdirectedアルゴリズムの正確性と性能を分析するために進化するsetプロセスを利用する。 0.80
(cid:124) The evolving set process. (cid:124) 進化するセットプロセス。 0.81
To understand the ESP update process, notice that χvW χ is the probability that Si a one-step random walk starting at v ends inside Si. ESPの更新プロセスを理解するために、v から始まる一段階のランダムウォークが Si の内部で終わる確率は svW > であることに気付く。 0.71
Given that the transition kernel of the evolving set process is given by K(S, S(cid:48)) = P[Si+1 = S(cid:48)|Si = S], the volume-biased ESP is defined by the transition kernel K(S, S(cid:48)) = P[Si+1 = S(cid:48)|Si = S] により進化した集合過程の遷移核が与えられると、体積バイアス ESP は遷移核によって定義される。 0.74
(cid:98)K(S, S(cid:48)) = (cid:98)K(S, S(cid:48)) = 0.92
vol(S(cid:48)) vol(S) vol(S(cid:48)) vol(S) 0.99
K(S, S(cid:48)) K(S, S(cid:48)) 0.98
We now give some useful facts about the evolving set process which we will use in our analysis of Algorithm 4. 現在、アルゴリズム4の分析に使用する、進化するセットプロセスに関する有用な事実をいくつか紹介しています。 0.70
The first proposition tells us that an evolving set process running for sufficiently many steps is very likely to have at least one state with low conductance. 最初の提案は、十分に多くのステップで実行される進化するセットプロセスは、コンダクタンスが低い少なくとも1つの状態を持つ可能性が高いことを示している。 0.66
Proposition 3 ([6], Corollary 1). 命題3([6], Corollary 1)。 0.50
Let S0, S1, . S0, S1, とする。 0.69
. . , ST be sets drawn from the volume-biased evolving set process beginning at S0. . . , ST は S0 から始まる体積バイアス発展集合から引き出される集合である。 0.80
Then, it holds for any constant c ≥ 0 that そして、任意の定数 c ≥ 0 に対して成り立つ。 0.83
(cid:20) (cid:112) (cid:20) (cid:112) 0.78
P min j≤T Φ(Sj) ≤ √ P min j≤T ~(Sj) ≤ ~ 0.73
c 4T −1 ln(vol(V )) c 4T −1 ln(vol(V)) 0.90
≥ 1 − 1 c . ≥ 1 − 1 c . 0.85
If (X0, X1, . X0, X1, である。 0.69
. . , XT ) is a lazy random walk Markov chain with X0 = x then for any set A ⊆ VH and . . , XT ) は X0 = x の遅延ランダムウォークマルコフ連鎖であり、任意の集合 A > VH に対して成り立つ。 0.81
integer T , let integer T , let 0.85
esc(x, T, A) (cid:44) P esc(x, T, A) (cid:44) P 0.98
Xj (cid:54)∈ A xj (cid:54)servlet a 0.67
 T(cid:91) (cid:21)  T(第91回) (cid:21)- 0.84
(cid:21) be the probability that the random walk leaves the set A in the first T steps. (cid:21) ランダムウォークが集合 A を最初の T ステップに残す確率とする。
訳抜け防止モード: (cid:21) be the probability―be the probability ランダムウォークは、集合 A を最初の T ステップに残す。
0.79
We will use the following results connecting the escape probability to the conductance of the set A and the volume of the sets in the evolving set process. エスケープ確率と集合 A のコンダクタンスと、進化する集合過程における集合の体積とを結合する以下の結果を用いる。 0.58
Proposition 4 ([24], Proposition 2.5). 命題4([24],命題2.5)。 0.46
There is a set AT ⊆ A with vol(AT ) ≥ 1 any x ∈ AT that 任意の x ∈ AT に対して vol(AT ) ≥ 1 の集合 AT > A が存在する。 0.88
2 vol(A), such that it holds for 2 vol(A) である。 0.50
esc(x, T, A) ≤ T Φ(A). esc(x, T, A) ≤ T (A) である。 0.80
j=0 Proposition 5 ([6], Lemma 2). j=0 命題5([6], Lemma 2)。 0.56
For any vertex x, let S0, S1, . 任意の頂点 x に対して、S0, S1, とする。 0.63
. . , ST be sampled from a volume-biased ESP starting from S0 = {x}. . . , ST は S0 = {x} から始まる体積バイアス ESP からサンプリングされる。 0.86
Then, it holds for any set A ⊆ VH and λ > 0 that すると、任意の集合 A > VH と λ > 0 に対して成り立つ。 0.79
(cid:20) P (cid:20) P 0.82
vol(St \ A) vol(St) vol(St \ A) vol(St) 0.85
max t≤T > λesc(x, T, A) Max t≤T >λesc(x, T, A) 0.80
< 23 1 λ . < 23 1 λ . 0.85
英語(論文から抽出)日本語訳スコア
Analysis of EvoCutDirected. EvoCutDirectedの解析 0.57
We now come to the formal analysis of our algorithm for finding almostbipartite sets in digraphs. 現在では、ダイアグラム中のほぼ二部集合を見つけるためのアルゴリズムの形式的解析にたどり着く。 0.64
We start by proving the connection between F (L, R) in a digraph with the conductance of the set L1 ∪ R2 in the semi-double cover. まず、F(L, R) 間のダイグラフ上の接続と、半二重被覆における集合 L1, R2 のコンダクタンスを証明することから始める。 0.68
Proof of Lemma 7. Lemma 7の証明。 0.69
We define SH = L1 ∪ R2, and have that SH = L1 > R2 と定義し、それを持つ。 0.78
ΦH (SH ) = シュッハ(SH) = 0.77
e(SH , VH \ SH ) volH (SH ) − 2eH (SH , SH ) e(SH , VH \ SH ) volH (SH ) − 2eH (SH , SH ) 0.89
volH (SH ) volH (SH ) 0.85
= volH (SH ) = 1 − 2eH (SH , SH ) volH (SH ) = volH (SH ) = 1 − 2eH (SH , SH ) volH (SH ) 0.87
This proves the first statement of the lemma. これは補題の最初の文である。 0.62
The second statement of the lemma follows by the same argument. 補題の第二のステートメントは、同じ議論によって従う。 0.74
= 1 − 2eG(L, R) = 1 − 2eG(L, R) 0.91
volout(L) + volin(R) volout (複数形 volouts) 0.37
= FG(L, R). fg(l, r) である。 0.60
We now show how removing all vertices u where u1 ∈ S and u2 ∈ S affects the conductance of S on the u1 ∈ s と u2 ∈ s が s のコンダクタンスに影響するようなすべての頂点 u の除去方法を示す。 0.70
semi-double cover. Lemma 14. 半二重カバー。 背番号14。 0.58
For any -simple set S ⊂ VH, let P = {u1, u2 : u ∈ VG, u1 ∈ S and u2 ∈ S} and set S(cid:48) = S \ P . P = {u1, u2 : u ∈ VG, u1 ∈ S and u2 ∈ S} とし、集合 S(cid:48) = S \ P とする。
訳抜け防止モード: 任意の単純集合 S に対して、P = { u1, u2 : u ∈ VG, u1 ∈ S, u2 ∈ S } S(cid:48 ) = S \ P とする。
0.88
Then, Φ(S(cid:48)) ≤ 1 Proof. すると、s(S(cid:48)) ≤ 1 Proof となる。 0.67
By the definition of conductance, we have 伝導の定義により、私たちは 0.79
1− (Φ(S) + ). 1 − ( φ(s) + ) である。 0.65
Φ(S(cid:48)) = シュ(S(cid:48)) = 0.68
vol(S(cid:48)) vol(S(cid:48)) 0.94
e(S(cid:48), V \ S(cid:48)) ≤ e(S, V \ S) + vol(P ) vol(S) − vol(P ) (cid:18) e(S, V \ S) ≤ 1 1 −  ≤ 1 1 −  1 1 −  e(S(cid:48), V \ S(cid:48)) ≤ e(S, V \ S) + vol(P ) vol(S) − vol(P ) (cid:18) e(S, V \ S) ≤ 1 1 − シュ ≤ 1 1 − シュ 1 1 − シュ 0.89
(Φ(S) + ) , (S)+(S)→(S) 0.60
vol(S) vol(S) vol(S) vol(S) 0.85
= (cid:19) = (cid:19) 0.82
+  e(S, V \ S) + vol(P ) +  e(S, V \ S) + vol(P ) 0.85
which proves the lemma. As such, we would like to show that the output of the evolving set process is very close to being a simple set. 補題を証明します したがって、進化する集合プロセスのアウトプットは単純な集合に非常に近いことを示したいと思います。 0.55
The following lemma shows that, by choosing the number of steps of the evolving set process carefully, we can very tightly control the overlap of the output of the evolving set process with the target set S, which we know to be simple. 以下の補題は、進化的集合過程のステップ数を慎重に選択することにより、進化的集合過程の出力とターゲット集合 S との重なりの重なりを極めて厳密に制御できることを示している。 0.66
Lemma 15. Let C ⊂ VH be a set with conductance Φ(C) = φ, and let T = (100φ 3 )−1. 背番号15。 C をコンダクタンス φ(C) = φ の集合とし、T = (100φ 3 )−1 とする。 0.59
There exists a set Cg ⊆ C with volume at least vol(C)/2 such that for any x ∈ Cg, with probability at least 7/9, a sample path (S0, S1, . 任意の x ∈ Cg に対して、少なくとも 7/9 の確率でサンプルパス (S0, S1, ) が成り立つような体積が少なくとも vol(C)/2 の集合 Cg > C が存在する。 0.79
. . , ST ) from the volume-biased ESP started from S0 = {x} will satisfy the following: . . S0 = {x} から始まる体積バイアス ESP から得られる , ST ) は以下の式を満たす。 0.84
2 • Φ(St) < 60φ 2 •(St) < 60φ 0.84
• vol(St ∩ C) ≥(cid:16) • vol(St s C) ≥(cid:16) 0.83
1 3 ln 1 2 vol(V ) for some t ∈ [0, T ]; 1 − 1 1 3 ln 1 2 vol(V ) for some t ∈ [0, T ]; 1 − 1 0.84
vol(St) for all t ∈ [0, T ]. すべての t ∈ [0, T ] に対して vol(St) である。 0.78
1 3 10 φ (cid:17) 1 3 10 φ (cid:17) 0.83
Proof. By Proposition 3, with probability at least (1 − 1/9) there is some t < T such that 証明。 命題3により、少なくとも (1 − 1/9) の確率で、ある t < t が存在する。 0.70
Φ(St) ≤ 3 4T −1 ln vol(VH ) = 3 シュ(St)≤ 3 4T −1 ln vol(VH ) = 3 0.82
400φ 2 3 ln vol(VH ) = 60φ 400φ 2 3 ln vol(VH ) = 60φ 0.86
1 3 ln 1 2 (vol(VH )). 1 3 ln 1 2(vol(VH))。 0.82
(cid:112) (cid:113) (cid:112) (cid:113) 0.78
24 24 0.85
英語(論文から抽出)日本語訳スコア
(cid:17) (cid:16) (cid:17) (cid:16) 0.78
vol(S(cid:48)) ≤ vol(S) ≤ vol(S ∩ C) 10 φ vol(s(cid:48)) ≤ vol(s) ≤ vol(s \ c) 10 φ である。 0.91
1 − 1 1 3 ≤ vol(C) 1 − φ 1 − 1 1 3 ≤ vol(C) 1 − φ 0.85
1 3 . Finally, the running time of the algorithm is dominated by the GenerateSample method, which was shown in [6] to have running time O 1 3 . 最後に、アルゴリズムの実行時間は、[6]に示すように実行時間oを示すgenesampleメソッドによって支配される。 0.83
vol(C)φ− 1 vol(C)φ− 1 0.97
3 2 (n) 2 ln 3 2 (n) 2ln 0.72
. Then, by Proposition 4 we have that esc(x, T, C) ≤ T φ = 1 at least 9/10, . そして、命題 4 により、esc(x, T, C) ≤ T φ = 1 を少なくとも 9/10 とする。 0.85
100 φ1/3. Hence, by Proposition 5, with probability 100 φ1/3. したがって、確率を伴う命題5により 0.73
vol(St \ C) vol(St) vol(St \ C) vol(St) 0.85
max t≤T ≤ 10 · esc(x, T, C) ≤ 1 10 Max t≤T ≤ 10 · esc(x, T, C) ≤ 1 10 0.76
· φ1/3 Applying the union bound on these two events proves the statement of the lemma. · φ1/3 これら2つの事象に結合を適用することは、補題のステートメントを証明している。 0.57
Now we combine everything together to prove Theorem 2. 定理 2 を証明するために、すべてを組み合わせる。 0.72
Proof of Theorem 2. By Lemma 15, we know that, with probability at least 7/9, the set S computed by the algorithm will satisfy 定理2の証明。 Lemma 15により、少なくとも7/9の確率で、アルゴリズムによって計算された集合 S が満たされることが分かる。 0.71
Let P = {u1, u2 : u1 ∈ S and u2 ∈ S}. P = {u1, u2 : u1 ∈ S and u2 ∈ S} とする。 0.88
Then, since C is simple, we have that そして、C は単純であるから、私たちはそれを持っている。 0.53
vol(S ∩ C) ≥ vol(s , c) ≥ 0.80
1 − 1 10 1 3 1 − 1 10 1 3 0.85
φ vol(S). (cid:19) φ vol(S)。 (cid:19) 0.80
(cid:18) (cid:19)(cid:19) (cid:18) (cid:19)(cid:19) 0.77
vol(P ) ≤ 2 · (vol(S) − vol(S ∩ C)) ≤ 2 · vol(p ) ≤ 2 · (vol(s) − vol(s \ c)) ≤ 2 · 0.81
1 − 1 − 1 10 1 − 1 − 1 10 0.85
1 3 φ · vol(S) = 1 3 φ ·vol(S) = 0.79
1 5 · φ 1 3 vol(S), 1 5 · φ 1 3 vol(s) である。 0.83
which implies that S is (1/5) · φ つまり、S は (1/5) · φ である。 0.75
1 3 -simple. Therefore, by letting S(cid:48) = S \ P , we have by Lemma 14 that 1 3 - 単純。 したがって、S(cid:48) = S \ P とすることで、Lemma 14 が持つ。 0.78
(cid:16) 1 Since Φ(S) = O 2 (n) direct calculation shows that (cid:16) 1 φ(s) = o 2 (n) の直接計算が示すからである。 0.76
1 3 ln φ Φ(S(cid:48)) ≤ 1 1 −  1 3 ln φ Φ(S(cid:48)) ≤ 1 1 −  0.89
· (Φ(S) + ) ≤ 1 1 − 1 · (Φ(S) + ) ≤ 1 1 − 1 0.85
5 Φ(S) + 1 3 5 シュ(S)+ 1 3 0.79
φ 1 5 ≤ 5 4 φ 1 5 ≤ 5 4 0.85
· Φ(S) + · φ · φ(s) + · φ 0.78
1 3 . 1 4 by Lemma 15, we have that Φ(S(cid:48)) = O 1 3 . 1 4 Lemma 15 により、s(S(cid:48)) = O となる。 0.83
φ 1 3 ln 1 2 (n) φ 1 3 ln 1 2 (n) 0.85
. For the volume guarantee, . ボリューム保証のために 0.74
(cid:19) (cid:16) (cid:19)(cid:16) 0.73
(cid:17) (cid:18) (cid:18) (cid:17) (cid:18)(cid:18) 0.75
(cid:18) (cid:17) (cid:18) (cid:17) 0.78
25 25 0.85
                                                   ページの最初に戻る

翻訳にはFugu-Machine Translatorを利用しています。