高速な最大k-Plex探索アルゴリズムの提案

[1]

[2]

H. Shiokawa, T. Amagasa and H. Kitagawa,

"Scaling Finegrained Modularity Clustering

for Massive Graphs," in IJCAI'19 , 2019.

X. Huang and L. V. S. Lakshamanan,

"Attribute-Driven Community Search," vol.

10, no. 9, pp. 949-960, 2017.

[3]

[4]

M. Onizuka, T. Fujimori and H. Shiokawa,

"Graph Partitioning for Distributed Graph

Processing," vol. 2, pp. 94-105, 2017.

C. Godsil , G. Royle, Algebraic Graph Theory,

Springer, 1949.

[5]

I. Bomze, M. Budinich, P. Pardalos and M.

Pelillo, "The Maximum Clique Problem,"

Handbook of Combinatorial Optimization, vol.

4, 5 1999.

[6]

J. Abello, M. Resende and S. Sudarsky,

"Massive

Quasi-Clique

Detection,"

in

LATIN'02 , 2002.

[7]

B. Balasundaram, S. Butenko and I. Hicks,

"Clique Relaxations in Social Network

Analysis: The Maximum k-Plex Problem,"

Operations Research, vol. 29, no. 1, pp. 133142, 2011.

[8]

J. Gao, J. Chen, M. Yin, R. Chen and Y. Wang,

"An Exact Algorithm for Maximum k-Plexes in

Massive Graphs," in IJCAI'18 , 2018.

S. B. Seidman, "Network Structure and

Minimum Degree," Social Networks, vol. 5, no.

3, pp. 269-287, 1983.

[9]

[10] R. Rossi and N. Ahmed, "The Network Data

Repository with Interactive Graph Analytics

and Visualization," in AAAI'15 , 2015.

[11] H. Moser, R. Niedermeier and M. Sorge, "Exact

Combinatorial Algorithms and Experiments

for Finding Maximum k-Plexes," Journal of

Combinatorial Optimization, vol. 24, no. 3, pp.

1-27, 2012.

[12] M. Xiao, W. Lin, Y. Dai and Y. Zeng, "A Fast

Algorithm to Compute Maximum k-Plexes in

Social Network Analysis," in AAAI'17 , 2017.

[13] B. X. Wu, "A Parallel Algorithm for

Enumerating All the Maximal k -Plexes," in

PAKDD Workshops'07 , 2007.

[14] Z. Wang, Q. Chen, B. Hou, B. Sho, Z. Li, W. Pan

and Z. Ives, "Parallelizing Maximal Clique and

k-Plex Enumeration over Graph Data,"

Journal

of

Parallel

and

Distributed

Computing, vol. 106, pp. 79-91, 8 2017.

[15] J. M. Robson, “ Finding a maximum

independent set in time O(2n/4),” Technical

Report, 2001.

付録 A(subgraph-reduction) 本節では，既存手法に用いられる subgraph-reduction，

およびそれを用いた remove-reduction (Algorithm 4)につい

て述べる．まず subgraph-reduction の元となる定理を示

し，アルゴリズムについて解説する．

定義 2 を用いて，次の定理が成り立つ．

定理 11

グラフ𝐺(𝑉, 𝐸)，整数𝑘, k-plex 𝑆 ⊆ 𝑉，およびノード𝑣 ∈

𝑉 ∖ 𝑆が与えられたとき，𝑆 ∪ {𝑣}について以下が成り立つ．

定理 2 により除去可能なノードを除去した残りのグラフ𝑉 ∗

が|𝑆| + |𝑉 ∗ | + 𝑟9,; (𝑣) ≤ 𝐿𝐵を満たすとき，𝑆 ∪ {𝑣}は𝐿𝐵より

大きな k-plex に含まれない．

証明

本稿では省略する( [8]を参照されたい．)

定理 11 は，あるノード𝑣を k-plex 𝑆に追加したと仮定し

て，それにより除去されたグラフから𝑣を評価する．定理

11 を用いて設計されるアルゴリズムを， Algorithm 8 に示

す．Algorithm 8 は，候補集合𝐶の各要素について(1 行

目)，一時的に𝑆に追加したとき，v-reduction によって除去

された結果が定理 11 を満たすか否かを判定する(4-15 行

目)．

付録 B(remove-reduction) Algorithm 8: subgraph-reduction(𝐺, 𝑆, 𝐿𝐵, 𝑘, 𝐶)

Input: 𝐺 = (𝑉, 𝐸), 整 数 𝑘, 𝐿𝐵, k-plex 𝑆 ⊆ 𝑉,

ノ ー ド 集 合 𝐶(た だ し 𝐶 ∩ 𝑆 = ∅)

Output: 削 減 さ れ た グ ラ フ 𝐺’

1. foreach 𝑣 ∈ 𝐶 do

2.

𝑟9,; (𝑢)を ∀𝑢 ∈ (𝑁9 (𝑣) ∖ 𝑆) ∪ 𝑈に つ い て 求 め る ;

3.

𝐺 SS (𝑉 SS , 𝐸SS ) ← 𝐺, 𝑄 ← ∅;

4.

foreach 𝑢 ∈ 𝑁9 RR (𝑣) ∖ 𝑆 do

5.

𝑐9SS,; (𝑢, 𝑣)を 求 め る ;

6.

if 𝑐9SS,; (𝑢, 𝑣) ≤ 𝐿𝐵 − |𝑆| then 𝑄.push(𝑢);

7.

while 𝑄 ≠ ∅ do

8.

𝑢 ← 𝑄. 𝑝𝑜𝑝(𝑣);

9.

𝐻 ← c𝑁9SS (𝑢) ∩ 𝑁9SS (𝑣)e ∖ 𝑆;

10.

if 𝑢 ∈ 𝑉′′ then 𝐺′′.remove(𝑢);

11.

foreach w∈ 𝐻 do

12.

𝑐9SS,; (𝑤, 𝑣)を 求 め る ;

13.

if 𝑐9SS,; (𝑤, 𝑣) ≤ 𝐿𝐵 − |𝑆| then 𝑄.push(𝑤);

14.

if|𝑁9 RR (𝑣) ∪ {𝑣}) ∖ 𝑆| + 𝑟9,; (𝑣) ≤ 𝐿𝐵 − |𝑆| then

15.

𝐺.remove(𝑣);

16.

break;

17. return 𝐺;

本節では，既存手法に用いられる remove-reduction につ

いて説明する．remove-reduction はあるノード𝑣を𝑆に追加

しないことを決定した際に実行される．例えば，𝑣が含ま

れる k-plex を全て探索し終えた際には，v そのものを除去

してしまって構わない．このような場面で呼ばれる除去ア

ルゴリズムが remove-reduction である．remove-reduction を

Algorithm 9 に示す．remove-reduction は，vertex-reduction

と subgraph-reduction を実行した後，親となる再帰関数を

実行する．

Algorithm 9: remove-reduction(𝐺, 𝑆, 𝐿𝐵, 𝑘, 𝑣)

Input: 𝐺 = (𝑉, 𝐸), 整 数 𝑘, 𝐿𝐵, k-plex 𝑆 ⊆ 𝑉,ノ ー ド 𝑣 ∈ 𝑉

Output: 𝐺 ∖ {𝑣}に 対 す る 最 大 k-plex の 大 き さ 𝐿𝐵

1. 𝑆 ← 𝑆 ∖ {𝑣}, 𝐺. 𝑟𝑒𝑚𝑜𝑣𝑒(𝑣);

2. 𝐺 ← vertex-reduction(𝐺, 𝐿𝐵, 𝑘);

3. 𝐺 ← subgraph-reduction(𝐺, 𝑆, 𝐿𝐵, 𝑘, 𝑉 ∖ 𝑆);

4. if |{𝑢|𝑢 ∈ 𝑉 ∖ 𝑆 ∧ 𝑑9 (𝑢) + 𝑘 > 𝐿𝐵}| + |𝑆| > 𝐿𝐵 then

5.

𝐿𝐵 ← max (𝐿𝐵, 𝐵𝐵(𝐺, 𝑆, 𝑘, 𝐿𝐵));

6. return 𝐿𝐵;

付録 C(前処理) Algorithm 10: preprocessing(𝐺, 𝑘)

Input: 𝐺 = (𝑉, 𝐸), 整 数 𝑘,

Output:下 限 値 𝐿𝐵と ， 削 減 さ れ た グ ラ フ 𝐺′

1. 𝑚 ← |𝑉| + 1, 𝐿𝐵 ← 0;

2. while |𝑉| < 𝑚 do

3.

𝑚 ← |𝑉|;

4.

𝐿𝐵 ← max (𝐿𝐵, 𝐿𝐵-Heuristic(𝐺, 𝑘));

5.

𝐺 ←vertex-reduction(𝐺, 𝐿𝐵, 𝑘);

6.

𝐺 ←subgraph-reduction(𝐺, ∅, 𝐿𝐵, 𝑘, 𝑉);

7. return (𝐿𝐵, 𝐺);

8.

9. function 𝐿𝐵-Heuristic(𝐺, 𝑘)

10. for 𝑖 ← 1 𝑡𝑜 |𝑉| do

11.

𝑣 ← argminy∈l 𝑑9 (𝑢);

12.

if 𝑑9 (𝑣) + 𝑘 ≥ |𝑉| then break;

13.

𝐺.remove(𝑣);

14. return |𝑽|;

本節では，既存手法に用いられる preprocessing につい

て説明する．preprocessing の目的は次の二つである．

1. 𝐿𝐵の初期値を与える

2. 探索を始める前に静的にグラフサイズを小さくする

1 について，既存手法は𝐿𝐵が大きいとき程多くの枝刈り

を実行可能である．そのため，前処理として素朴なアルゴ

リズムにより最低限の𝐿𝐵，つまり小さな k-plex を見つけ

ることが重要である．

2 について，既存手法にて提案された除去アルゴリズム

のうち，vertex-reduction と subgraph-reduction は起点ノー

ドを指定せずとも実行可能である．そのため，まずこれら

を実行することにより，探索を行う前にグラフサイズの削

減を図る．Algorithm 10 に preprocessing を示す．Algorithm

10 では，𝑉中の次数が最も少ないノードを除去し，𝑉が kplex となるまでこれを繰り返す(16-19 行目)．これにより

下限値𝐿𝐵を導出し，それに基づいてグラフサイズを削減

する．これらを相互に繰り返し，前述した二つの目的を達

成する．

既存手法では，前処理によってグラフサイズが極限まで

小さくなり，最大の k-plex を検出できるケースが存在す

ることが示されていた．本稿では提案手法との比較のた

め，そのようなデータセットは実験対象から除外してお

り，全てのデータセットに対して動的な探索を行う．

...