DEIM Forum 2023 2b-6-2

グラフ集約に基づく高速な最大 k-plex 探索
真次 彰平†

藤原 靖宏††

塩川浩昭†††† 筑波大学大学院理工情報生命学術院 〒 305-8571 茨城県つくば市天王台 1-1-1†† 日本電信電話株式会社 〒 243-0198 神奈川県厚木市森の里若宮 3-1††† 筑波大学計算科学研究センター 〒 305-8571 茨城県つくば市天王台 1-1-1
E-mail: †matsugu@kde.cs.tsukuba.ac.jp, ††yasuhiro.fujiwara.kh@hco.ntt.co.jp, †††shiokawa@cs.tsukuba.ac.jp
あらましk-plex はクリークを一般化した密部分グラフのモデルであり，グラフ中の最大の k-plex を求める MPS(Maximum k-Plex Search) 問題は実世界の幅広いソーシャルネットワーク分析に応用される．しかしながら，既存のMPS 問題の解法は探索候補を枝刈りする過程で全てのノードを繰り返し走査する必要るため低速である．そこで本稿では隣接するノードをマージすることで探索空間を大幅に削減する高速な解法を提案する．実データを用いた実験により提案手法におけるマージ戦略が効率的な探索を実現し，最先端の既存手法に対して最大約 10 倍高速であることを確認した．
キーワード k-plex，グラフ
パーソナライズドソーシャルサーチ パーソナライズドソー

1 はじめにシャルサーチはソーシャルネットワーク上の友人関係によるコソーシャルネットワークにおけるユーザの行動分析に用いられる技術の一つに最大密部分グラフ抽出がある．最大密部分グ
ラフ抽出はグラフ中の密度の高い部分グラフのうち最も多くのノードからなる部分グラフを発見する技術である．最大密部
分グラフ抽出における最も代表的なアプローチである最大クリーク探索は幅広い分野で応用されているが，次に示す二つの問題点がある．一つ目は実世界のソーシャルネットワークには
スケールフリー性があるため，コミュニティが多様な密度を持つ点である．二つ目は最大クリーク探索の既存手法は実際のコミュニティに対して非常に密で小さい部分グラフを同定してしまう点である．以上のことから，既存の最大クリーク探索手法
は実世界のコミュニティを正確に発見することが困難である．
この問題を解決するため近年最大 k-plex 探索 [1] が注目を集めている [2, 3]．k-plex はクリークを一般化した密部分グラフのモデルであり，n 個のノードからなる部分グラフの各ノードがその部分グラフ中の n − k 個以上のノードと隣接するような部
分グラフのことである [4]．k-plex は密度と大きさのバランスに優れており，最大 k-plex 探索は実世界の大きな密部分グラフをミュニティを用いて Web 検索結果をランキングする手法であり [7, 8]，最大 k-plex 探索が用いられている．例えば Danezis らは友人による最大のコミュニティで共有される検索嗜好の事前計算に最大 k-plex 探索を用いた [9]．具体的にはまずソーシャ
ルネットワークから最大 k-plex を抽出し，その k-plex における嗜好をベイズモデルにより推論する．k-plex が多様な密度のコ
ミュニティを扱うことができるため，最大 k-plex 探索を用いたパーソナライズドソーシャルサーチは他の密部分グラフのモデルと比較して有効であることが報告されている．
グラフニューラルネットワーク (GNN) 最大 k-plex 探索は近年
ソーシャルネットワーク解析の主要なアプローチの一つとなっている GNN の性能向上にも寄与している．GNN ではノードのコンテキストを把握するためにグラフのプーリングが重要であり，古典的にはクリークを用いたグラフプーリング手法が用いられてきた [10]．Bianchi らは最大 k-plex 探索を基にしたグラ
フプーリング手法を提案し，クリークによる手法と比較して畳み込み層の数を削減した．その結果として提案手法は GNN 上の課題である過平滑化問題を緩和することに成功し，高精度な抽出できるため，次のようなアプリケーションに応用される．

GNN を実現した [11]．

犯罪ネットワーク分析

最大 k-plex 探索は他にも口コミによる広告戦略の策定 [12, 13]

最大 k-plex 探索はソーシャルネット

ワークにおけるテロ組織，犯罪組織，カルト宗教のような警戒すべきコミュニティの発見に有効である．Menon らはパブリッ
クデータセットから 9.11 アメリカ同時多発テロに関与したテ
ロリストを検出するために複数のモデルを比較し，k-plex がクリークを含むいくつかのモデルと比較して最も多くのテロリス
トを検出できることを明らかにした [5]．また Balasundaram は
犯罪ネットワークにおける麻薬取引やマネーロンダリングの検出において最大 k-plex 探索が最大クリーク探索より優れている
ことを報告している [6]．

や感染症の拡大分析 [14, 15] などにも応用されている．紙面の都合上，詳細は省略する．
最大 k-plex 探索は多くのアプリケーションに有効であるが，グラフ中の最大 k-plex を見つける問題は NP-Hard であることが知られている [1]．具体的にはグラフ G 中のノード集合を VGとすると，素朴な最大 k-plex 探索アルゴリズムは O(2|VG | |VG |)の時間計算量を要する．しかしながら，近年のソーシャルネッ
トワークは巨大であるため [16]，最大 k-plex の探索は数日程度の計算時間を要する．

1. 1 既存研究と本研究の位置付け

BnM 法は我々の知る限り大規模なソーシャルネットワークに最大 k-plex 探索の高速化にはいくつかのアプローチがある．

対して効率的に最大 k-plex を出力できる唯一の手法であり，最古典的なアプローチとしては greedy branching 法 [17]，branch-

先端の既存手法と比較して高速に最大 k-plex を探索できる．例

and-cut 法 [1]，および branch-and-search 法 [18] が挙げられる．

えば 110 万ノードからなるソーシャルネットワークに対して，

これらの手法な素朴な最大 k-plex 探索と比較して高速だが，枝最先端の既存手法である KpLeX 法 [16] が最大 k-plex の出力に刈りに用いる上限値の計算が緩いため探索する必要のあるノー

1 分以上掛かる一方で，BnM 法は同じ解を 16 秒以内に求めるド数が依然として多い．そのためこれらのアプローチでは実用ことが可能であり，BnM 法は実世界の多様なアプリケーション

的な計算時間で最大 k-plex を出力できない．

の品質を向上させることができる．

Gao らは近年 branch-and-bound (BnB) 法を提案した．その2 事前準備基本となるアイデアはグラフ削減アルゴリズムを用いて最大まずはじめに本稿で用いる記号を定義する．本稿では重みのk-plex になり得ないノードの無駄な探索を避けることにある．

ない連結な無向グラフ G = (VG , EG ) を考える．ここで VG ，このグラフ削減アルゴリズムに基づき，BnB 法は冗長な探索をEG はそれぞれ G のノード集合およびエッジ集合である．ノー

省略しつつ最大 k-plex を見つけられることが保証される．BnB

ド u の G における次数を dG (u)，部分ノード集合 VS ⊆ VG に法は古典的なアプローチと比較して高速だが，その速度は未だよる G の誘導部分グラフを G[VS ] と書く．またグラフ G から十分でないため BnB 法を高速化した手法がこれまでに提案さノード v および v に接続するエッジを除いたグラフを G−v とれている [16, 19, 20]．しかしながら，既存の最先端の手法であ書く．すなわち，G−v = G[VG \{v}] である．

る KpLeX 法 [16] はグラフを削減するためにすべてのノードを最大 k-plex 探索はグラフ G 中の最大の k-plex を見つける問

繰り返し探索する必要があり，O(|VG | ) の時間計算量を要する題である．ここで k-plex はクリークを一般化した密部分グラフ2ため，巨大なソーシャルネットワークに対して高速に応答できのモデルであり，次のように定義される [21]．

ない．そのため，大規模なソーシャルネットワークに対する最定義 1 (k-plex) グラフ G，および正の整数 k が与えられた

大 k-plex 探索の更なる高速化は重要な研究課題である．

とき，G[VS ] ⊆ G が VS 中の全てのノード v ∈ VS に対して

1. 2 本研究の貢献
本稿ではソーシャルネットワークに対する高速な最大 k-plex 探索手法である，Brunch-and-Merge (BnM) 法を提案する．1. 1 節
で述べた近年の既存手法はグラフ削減アルゴリズムを実行するために O(|VG |2 ) の時間計算量を要する．それに対して BnM 法はソーシャルネットワークが持つスケールフリー性に着目することで，最大 k-plex に含まれないノードを O(|VG |) 時間で列挙することができる．これにより BnM 法は効率的にグラフサイズを削減し，高速な計算を実現する．
上述したアイデアに基づき，BnM 法を次の 3 つのステップで設計する．
（1）最大 k-plex に同時に含まることのないノード集合を safe-to-merge ノードとして定義する（3. 2 節）．
（2）

dG[VS ] (v) >= |VS | − k を満たすとき，G[VS ] は k-plex である．
G[VS ] が k-plex であれば, 各ノード v ∈ VS は少なくとも |VS |−k個のノードと隣接する．定義 1 を用いて，最大 k-plex 探索は以下のように定義される。
問題定義 1 (最大 k-plex 探索)

グラフ G，および正の整数 k が与えられたとき，最大 k-plex 探索は G 中の最大の k-plex，すな
わち |VS | が最大となる G[VS ] ⊆ G を見つける問題である．

k = 1 のとき，問題定義 1 は明らかに最大クリーク探索と等価である [22]．最大 k-plex 探索は NP 困難 [21, 23, 24] であるため大規模ソーシャルネットワークに対する効率的な探索手法の開発は重要である．

3 Branch-and-Mergeh (BnM) 法

safe-to-merge ノードを効率よく探索してグラフサイズを削減

本節では提案手法 BnM 法について説明する．最初に 3. 1 節

する node-merging 法を提案する（3. 3 節）. （3）node-mergingに BnM 法を構成する基本的なアイデアを示し，その詳細を以法を用いて最大 k-plex を高速に探索する BnM 法を設計する

降の節にて説明する．紙面の都合上，補題の証明は省略する．

（3. 4 節）. さらには，BnM 法が実世界のグラフが持つスケール

3. 1 基本アイデア

フリー性を利用することで，node-merging 法によるグラフサイズの削減が効果的に機能することを理論的に示す．
本研究の貢献は以下の通りである．

1. 1 節で示した既存手法は最大 k-plex に含まれないノードを削除するグラフ削減アルゴリズムを繰り返し適用することで探索空間を小さくする．しかしながら，それらのグラフ削減アル

効率性: BnM 法はここ数年で提案された最大 k-plex 探索

ゴリズムは全てのノードを繰り返し参照する必要があるため計手法より高速である（4. 1 節）．また BnM 法は最先端の既存手算コストが高い．それに対し BnM 法は最大 k-plex に含まれな法と比較して時間計算量が小さいことを示す（定理 1）.

いノードを効率的に探索し，グラフサイズを小さくする．その••正確性: BnM 法は探索の効率化のためにグラフサイズ

ために，本稿ではまず共に最大 k-plex に含まれることのないを非常に小さくするが，必ず正確な最大 k-plex を見つけること

ノード集合に着目し，それらを safe-to-merge ノードとして定ができる（定理 2）.

義する（3. 2 節）．次に safe-to-merge ノードをグラフから効率

スケーラビリティ: BnM 法は既存手法と比較して優れた的に計算および削除する node-merging 法を説明する（3. 3 節）．

スケーラビリティを持つ（4. 3 節）．我々の実験において，BnM

最後に探索空間を大幅に削減することで最大 k-plex を高速に発法はノード数に対しておよそ線形なスケーラビリティを示した．

見する BnM 法を提案する（3. 4 節）．

•

(6, 3)-plexes

Fragile nodes

Unfruitful nodes

Edges between safe-to-merge nodes

𝑠$%&
𝑣$

𝑣"

𝑣%

𝑣&

𝑣'

𝑣!

𝑣#

𝑣$*

𝑣)

𝑣$

𝑣(

𝑣%

𝑣$$

𝑣&

𝑣"

𝑣'

𝑣!

𝑣#

(a)

𝑣)

𝑣$

𝑣(

𝑣%

𝑣$*

𝑣&

𝑠!"

𝑣"

𝑣'

𝑣!

𝑣)

𝑣(

𝑣!

𝑠!"#

𝑣#

(b)

𝑠
𝑠') !"#

𝑣"

𝑣(

𝑣"

𝑣#

(c)

𝑣!

𝑠!"#

𝑠$%&

𝑣#

(d)

(e)

図 1: node-merging 法の動作例 （α = 6，k = 3．
） s123 , s78 ，および s789 はスーパーノードを示す．
上記のアイデアを基に提案するアルゴリズムは既存手法に対して二つの優位性を持つ．
（１）BnM 法は最大 k-plex を短時間で出力可能である．全ノードを繰り返し参照する既存のグラフ
削減アルゴリズムとは異なり，BnM 法は最大 k-plex に含まれないノードに隣接するノードのみを走査することでグラフサイズを縮小する．ここでソーシャルネットワークはスケールフリー性を持つため [25]，次数の小さな最大 k-plex に含まれないノードが多く存在する．この特性を活用し，BnM 法は実世界のグラフにおいて効果的にグラフサイズを削減可能である．
（２）BnM

定義 4 (収束グラフ) α，および k に対して，G(i) を i 回目の削除後に残ったグラフとする．すなわちG[VG \UG ]
(i)
G =
G[V
G(i−1) \UG(i−1) ](i = 1)(i > 1).

と す る と ，収 束 グ ラ フ Ĝ を UG(i) = ∅ を 満 た す Ĝ =G[VG(i) \UG(i) ] である．
定義 4 に示した通り収束グラフ Ĝ には unfruitful ノードが存在しない. 例えば図 1 (a) において (6, 3)-plex に対する収束グラフ法は常に正確な最大 k-plex を出力する．これは BnM 法がノーを作ることを考える．unfruitful ノード UG は UG = {v11 } であドをマージする際に最大 k-plex に含まれないノードのみを削除るため，UG を削除した後には図 1 (b) のような G(1) を得る．

するためである．そのため BnM 法は探索の品質を落とすこと

定義 3 より G(1) はさらに unfruitful ノード UG(1) = {v10 } を持なく最大 k-plex を発見する．その結果として，BnM 法は効率つ．そのため G(2) は図 1 (c) のようになる．G(2) は全てのノー的に正確な最大 k-plex を探索できる．

ドが次数 α − k = 3 以下であるため unfruitful ノードが存在しな
い．したがって，G(2) は G の収束グラフ，すなわち Ĝ = G(2)3. 2 Safe-to-merge ノード
BnM 法は共に最大 k-plex に含まれることの無いようなノーである．
次に定義 2，定義 3，および定義 4 を用いて safe-to-merge ノードを削除する．このようなノードの集合を safe-to-merge ノードを定義する．

ドと呼ぶ．safe-to-merge ノードを定義するために，先に定義 2，

定義 5 (Safe-to-Merge Nodes) 隣接する二つのノード u, v ∈ Ĝ

定義 3，および定義 4 を導入する．

が与えられたとき，u ∈ UĜ−v かつ v ∈ UĜ−u であり，かつそ

定義 2 ((α, k)-plex) 部分グラフ G[VS ] ⊆ G の大きさ |VS | が αのときに限り，u と v は safe-to-merge ノードである．また u とであるとき，G[VS ] は G の (α, k)-plex である．

v が safe-to-merge ノードであるとき，u ↔Ĝ v と表す．

(α, k)-plex は大きさ α の k-plex である．ここで (α, k)-plex は α

定義 5 は収束グラフ Ĝ からノード v を削除した後にノード u が毎に複数存在し得ることに注意したい．例えば図 1 (a) は二つのunfruitful ノードになることと，u ↔hatG v が成り立つことが(6, 3)-plex をもつ．具体的には G[{v1 , v2 , v3 , v4 , v5 , v6 }] および同値であることを示す（逆も同様である）．図 1 (c) において太G[{v4 , v5 , v6 , v7 , v8 , v9 }] が定義 2 を満たす (6, 3)-plex である．

線は両ノードが safe-to-merge ノードであることを示す．例えば

定義 2 に基づき unfruitful ノードを定義する．これは以下の(6, 3)-plex において隣り合う二ノード v7 と v8 は safe-to-merge

ように任意の (α, k)-plex に含まれないノード集合である．

ノードである．これは G−v8 においてノード v7 の次数が 2 と定義 3 (Unfruitful ノード) α と k に対して, unfruitful ノードなるため α − k = 3 より小さくなり，ノード v8 も G−v7 におUG は UG = {v ∈ VG | dG (v) < α − k}. である．

いて次数が 3 より小さくなるためである．定義 5 について次の定義 3 の通り unfruitful ノード UG は次数が α − k より小さな補題が成り立つ．

u ↔Ĝ v であるノード u, v について，v がある (α,ノードの集合である．定義 2 および定義 3 より，UG は任意の補題 1(α, k)-plex に含まれない．例えば図 1 (a) において，unfruitfulk)-plex に含まれないならば，u もその (α, k)-plex に含まれない．

ノードは dG (v11 ) = 2 < α − k = 3 より UG = {v11 } である．

補題 1 は safe-to-merge ノードである二つのノードのうち，一方unfruitful ノードは任意の (α, k)-plex に含まれないため，グラのノードがある (α, k)-plex に含まれない場合，もう一方のノー

フ G から削除できる．しかし，ノードの削除によって隣接する

ドもその (α, k)-plex に含まれないことを示している．逆に，一ノードの次数が下がるため，新しく unfruitful ノードが発生す方のノードがある (α, k)-plex に属する場合，もう一方のノードる．そこで以下のように G 中の全ての unfruitful ノードを削除も必ずその (α, k)-plex に属している．よって，(α, k)-plex に含したグラフを収束グラフとして定義する．

まれないノードがあれば，それらの safe-to-merge ノードを削除

することで効率的にグラフサイズを削減できる．しかしながら，

Algorithm 1 Node-merging 法

定義 5 に基づき safe-to-merge ノードを特定するためには全てのInput: 収束グラフ Ĝ;Output: safe-to-merge ノードをマージしたグラフ G∗ ;ノード対について計算する必要がある．これは O(|VĜ |2 ) 時間の計算を要するため効率的でない．

1: procedure M ERGE (Ĝ, α, k):

3. 3 Node-merging 法

2:
3:

本節では収束グラフから効率的に safe-to-merge ノードを見つ
ける node-merging 法を説明する．まず背景となる性質について述べた後（3.3.1 節），その詳細について示す（3.3.2 節）．

4:
5:
6:
7:
8:

3. 3. 1 Fragile ノード

9:

まず safe-to-merge ノードを効率的に探索するために重要とな

10:
11:

る fragile ノードについて説明する．
定義 6 (Fragile ノード)

収束グラフ Ĝ が与えられたとき，frag-ile ノード FĜ を以下のように定義する．
FĜ = {v ∈ VĜ | dĜ (v) = α − k}.
例えば図 1 (c) において，fragile ノードは次数が α − k = 3 であるノードの集合であるため，FĜ = {v1 , v2 , v3 , v7 , v8 } とな
る．ノードが削除されるとその隣接ノードの次数が小さくなる
ため，fragile ノードは自身に隣接するノードが削除されたとき

unfruitful ノードに変わる．例えば図 1 (c) 中の v7 は v8 を Ĝ から削除した後 unfruitful ノードになる．この逆もまた成り立つ
ため，定義 5 より v7 と v8 は safe-to-merge ノードであることがわかる．一般的にこのような性質は次の補題として示すこと
ができる．
補題 2

12:
13:
14:
15:
16:
17:
18:

G∗ ← Ĝ;FG∗ ← {v ∈ VG∗ | dG∗ (v) = α − k};M ← G[FG∗ ] 中の連結成分;
while M =| ∅ doスーパーノード s を VG∗ に追加;
for each v ∈ M dofor each u ∈ N (v)\M do
エッジ (u, s) を EG∗ に追加;
VG∗ から v を削除する;FG∗ ← FG∗ ∪ {s}\M ;M ← ∅;
for each v ∈ NG∗ (s) do
if v ↔G∗s thenM ← M ∪ {v};if M = ∅ thenM ← G[FG∗ ] 中の連結成分;
return G∗ ;スーパーノードは safe-to-merge ノードの集合を単一のノードとして表現する特別なノードである．またマージされる前のノードは全て fragile ノードであるため，スーパーノードの次数は常に α − k とする．さらには M に接続する各エッジを s と接続しなおすため，同一のエッジが複数本作られることがある．例えば図 1 (d) において {v1 , v2 , v3 } を s123 にマージするとき，エッジ (v1 , v4 ) および (v2 , v4 ) はどちらも (s123 , v4 ) に変換される．

Algorithm 1 に node-merging 法のアルゴリズムを示す．補題 2

G[FĜ ] を fragile ノードから構成される誘導部分グラフ

よりノード u, v ∈ FĜ が G[FĜ ] で連結であるとき，u, v はとする．G[FĜ ] にパス v1 → v2 → ... → vN が存在するならば，

safe-to-merge ノードであり，Algorithm 1 はこの性質を利用す

vi ↔Ĝ vi+1 が i ∈ {1, 2, ..., N − 1} について成り立つ．

る．Algorithm 1 はまず fragile ノード FG∗ を計算する（3 行目）．

補題 2 は fragile ノードから構成される誘導部分グラフ中の連

次に補題 2 に基づき G[FG∗ ] の中から連結なノード集合 M を深結なノード集合は safe-to-merge ノードであることを示していさ優先探索により探索する（4 行目）．その後，各連結成分 M にる．例えば図 1 (c) においてノード v1 ，v2 ，および v3 は FĜ について定義 7 に従い M を対応するスーパーノード s に置き換え属している．またパス v1 → v2 → v3 が G[FĜ ] に存在するた（6–10 行目），s は常に fragile ノードであるため s を FG∗ に追加

め，v1 ↔Ĝ v2 かつ v2 ↔Ĝ v3 が成り立つ．fragile ノードを用する（11 行目）. ここで，NG∗ (u) = {v ∈ VG∗ | (u, v) ∈ EG∗ }いるとこのようなパスは O(|VĜ |) 時間で自明に探索できる．しを u の G∗ における隣接ノードの集合とし，Algorithm 1 はたがって補題 2 に基づき効率的に safe-to-merge ノードを見つけNG∗ (s) を探索することで連結成分 M を更新する．NG∗ がることができる．

スーパーノード s と隣接する safe-to-merge ノードを持つなら

3. 3. 2 Node-merging 法のアルゴリズム

ば，それらのノードを M に追加する（13–15 行目）．またそう

safe-to-merge ノードを効率的に探索する手法である node-でないならば，次の連結成分の探索へ移行する（16–17 行目）．

merging 法のアルゴリズムを説明する．node-merging 法はまず

safe-to-merge ノードが無くなったとき，Algorithm 1 は終了する

補題 2 に基づき safe-to-merge ノードを列挙する．次に補題 1 を（5–17 行目）．

用いてそれらのノードを単一のスーパーノードとしてマージす

図 1 (c)， (d)，および (e) は Algorithm 1 の実行例である．

ることでグラフサイズを削減する．node-merging 法のアルゴリ

図 1 (c) に示す収束グラフ Ĝ は，FĜ = {v1 , v2 , v3 , v7 , v8 } を持

ズムを説明するために，先にスーパーノードを定義する．

つ．このとき {v7 , v8 } をマージすることにより，Algorithm 1

定義 7 (スーパーノード) グ ラ フ Ĝ，お よ び 連 結 な safe-to-はスーパーノード s78 を図 1 (d) のように追加する．定義 7 に

merge ノード M ∈ G[FĜ ] の集合が与えられたとき，スーパーノード s を M をマージした後のノードとする．ここで，s は{v ∈ VĜ | ∀u ∈ M, (u, v) ∈ EĜ } に属するノードと隣接する．
また s の次数は dĜ (s) = α − k とし，スーパーノードの大きさ|s| を |s| = |M | と定義する．M をマージすることにより，Mのノードおよびそれらに接続するエッジは Ĝ から削除される．

基づき, エッジ (v7 , v4 )，(v7 , v9 )，(v8 , v6 )，および (v8 , v9 ) はそれぞれ (s78 , v4 )，(s78 , v9 )，(s78 , v6 )，および (s78 , v9 ) に置
き換えられる．同様に {v1 , v2 , v3 } は s123 へとマージされる．
ここで図 1 (d) において互いに隣接する s78 と v9 はどちらも

safe-to-merge ノードであるため，これらのノードを図 1 (e) のように s789 としてマージする．

Algorithm 2 提案手法: Branch-and-Merge (BnM) 法
Input: グラフ G, 正の整数 k;
Output: 最大の k-plex Gmax ;1: Ĝ ← G, Gmax ← ∅, α ← k + 1;
2: while true do
3:
4:
5:
6:
7:
8:
9:
10:

Ĝ ← Ĝ の α および k における収束グラフ;
Gcurr ← B RANCH (Ĝ, |VĜ |, α, k)if Gcurr = ∅ thenreturn Gmax ;Ĝ ← G[VĜ \FĜ ];Gmax ← Gcurr ;α←α+1

11: procedure B RANCH (Ĝ, n, α, k)12:
if n = α then
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:

return Ĝ;if n < α thenreturn ∅;G∗ ←M ERGE (Ĝ, α, k);Gcurr ← ∅;for each v ∈ VG∗ do
if v is a supernode thenn ← n − |v|;elsen ← n − 1;
Gcurr ← B RANCH (G∗−v , n, α, k);
if Gcurr =| ∅ thenreturn Gcurr ;return ∅;最後に Algorithm 1 を用いて Ĝ 中の全ての safe-to-merge ノードをマージする時間計算量を示す．
補題 3

Algorithm 1 の時間計算量は O(|FĜ | · (α − k)) である．

再帰計算の後に Ĝ のノード数が α であるならば，B RANCH 関
数は Ĝ を (α, k)-plex として返す．そうでないならば，B RANCH
関数は何も返さない（12–15 行目）．最後に B RANCH 関数が何も返さなければ，BnM 法は (α − 1, k)-plex を最大 k-plex として出力する (5–6 行目)．
理論解析：BnM 法の効率性と正確性について理論的に解析する．本節では τ を Algorithm 2 において B RANCH 関数を呼び出した回数とする．
定理 1

BnM 法の時間計算量は O(τ (|VĜ | + |FĜ |(α − k))) である．
証明

Algorithm 2 の 16 行目に示した通り，B RANCH 関数は

M ERGE 関数を呼び出しており，補題 3 よりその時間計算量
は O(|FĜ |(α − k)) である．さらに Algorithm 2 の 18–25 行目に示した通り，BnM 法 (α, k)-plex を求めるために |VĜ | 回のイテレーションを実行する．よって BnM 法の時間計算量はO(τ (|VĜ | + |FĜ |(α − k))) となる．

2

最 先 端 の 既 存 手 法 は グ ラ フ 削 減 に O(|VG | ) 時 間 を 要 す る
2

ため，最大 k-plex の探索には O(τ |VG |2 ) 時間を要する．その一方で定理 1 に示した通り BnM 法は時間計算量を大幅に 削 減 す る ．3. 3 節 で 述 べ た 通 り，ス ケ ー ル フ リ ー 性 に よって O(|FĜ |) ≈ O(|VG |/(α − k)(γ−1) ) が成り立つため，定理 1 で 導 い た 時 間 計 算 量 は O(τ (|VG | + |FĜ |(α − k))) ≈O(τ |VG |(1 + 1/(α − k)(γ−2) ))) と近似できる．このとき実用

3. 1 節で述べた通り，実世界のソーシャルネットワークはス

的には O(1 + 1/(α − k)(γ−2) ) ≈ O(1) と見なせるため，BnM

ケールフリー性により次数の小さなノードを多く持つ．スケー

法は O(τ |VG |) 時間で実行可能である．ここで理論的には τ はルフリー性とは γ をデータの次数分布の偏りを表す正の定数|VG∗ | に依存する．|VG∗ | の値は探索の過程で動的に減少するたとしたとき，次数が d であるノードの数がおおよそ |VG |d−γ

め，τ の実際の値は |VG∗ | より遥かに小さい．これにより BnMに比例するという性質である [26, 27]．fragile ノードはちょう

法はノード数に対しておおよそ線形のスケーラビリティを持つ．

ど d = α − k 個のノードと隣接するため，実用上は O(|FĜ |)4 節にて実世界のソーシャルネットワークに対する BnM 法のは O(|FĜ |) ≈ O(|VĜ |(α − k)−γ ) と近似できる．したがって効率性とスケーラビリティを検証する．

Algorithm 1 は O(|FĜ | · (α − k)) ≈ O(|VĜ |/(α − k)(γ−1) ) 時間定理 2でグラフサイズを削減できる．つまり Algorithm 1 は実世界のBnM 法は正確な最大 k-plex を出力する．

ソーシャルネットワークにおいてノード数に対して劣線形時間

証明で応答する．それに対して，1. 1 節で述べた通り最先端の既存関数の呼び出し（4 行目，11–26 行目）の二つのステップからBnM 法は（１）Ĝ の構築（3 行目），および（２）B RANCH

手法は O(|VG |2 ) 時間でグラフ削減を行う．そのため補題 3 はなる．
（１）について Algorithm 2 の 3 行目に示した通り，定義 4

Algorithm 1 は既存の最大 k-plex 探索アルゴリズムと比較してに基づき Ĝ の構築には unfruitful ノードの削除のみしか行わな

効率的にグラフを小さくできることを示している．

い．unfruitful ノードは定義 3 により (α, k)-plex に含まれない

3. 4 BnM 法

ことが明らかである．
（２）について Algorithm 2 の 18–25 行目に示した通り，BnM 法はノード v ∈ Ĝ を逐次選択し，Ĝ−v かBnM 法のアルゴリズムを Algorithm 2 に示す．BnM 法は繰りら (α, k)-plex を探索する．補題 1 で示した通り，もし v がスー

返し α を増加させながら最大 k-plex を見つけるまで (α, k)-plex

パーノード s に属するならば，s 中の全てのノードは Ĝ−v 中のを探索し続ける（2–9 行目）．まず任意の k 個のノードは自明に任意の (α, k)-plex に含まれない．そのため Algorithm 2 が直接(k, k)-plex であるため，α = k + 1 から探索を始める（1 行目）．

分枝探索しないノード（18 行目）が存在しても，BnM 法は全各イテレーションについて BnM 法は Ĝ から (α, k)-plex を見つての (α, k)-plex を各イテレーションで計算できる．したがってけるために B RANCH 関数を呼び出す（4 行目）．B RANCH 関数

BnM 法は正確な最大 k-plex を出力する．

は削減（16 行目）と分枝（18–25 行目）の 2 つのステップからなる．削減のステップでは Algorithm 1 に示した M ERGE 関数を用いてグラフサイズを削減する．分枝のステップでは再帰的に

B RANCH 関数を呼び出し，VG∗ 中のノードを一つずつ削除する．

2

定理 2 は BnM 法が効率的な最大 k-plex の探索を実現するためにノードの集約および削除を行うが，それらが最大 k-plex の品質に影響を与えないことを示している．

表 1: 実データセットに対する実行時間
Graphs
4*soc-LiveMocha

4*soc-douban

4*soc-gowalla

4*soc-twitter-follows

4*soc-youtube

4*soc-delicious

4*soc-FourSquare

4*soc-youtube-snap

4*soc-lastfm

4*soc-pokec

4*soc-ﬂixster

4*soc-livejournal|VG |4*104,103

4*154,908

4*196,591

4*404,719

4*495,957

4*536,108

4*639,014

4*1,134,890

4*1,191,805

|EG |

γ

αmax

k

BnM

BnB

Maplex

KpLeX

4*2,193,083 4*1.75

19

2

16.23 (± 0.31) sec.

467.19 (± 4.42) sec.

48.96 (± 0.91) sec.

12.01 (± 0.32) sec.

22340.80 (± 0.55) sec.

DNF

329.74 (± 1.37) sec.

42.77 (± 0.81) sec.

25

4

529.31 (± 2.76) sec.

DNF

5,122.63 (± 7.72) sec.

631.10 (± 4.28) sec.

28

58,899.67 (± 8.42) sec.

DNF

DNF

DNF

12

2

0.16 (± 0.01) sec.

0.81 (± 0.06) sec.

0.21 (± 0.03) sec.

0.28 (± 0.02) sec.

14

30.16 (± 0.01) sec.

0.71 (± 0.05) sec.

0.26 (± 0.03) sec.

0.31 (± 0.03) sec.

16

40.14 (± 0.01) sec.

0.59 (± 0.07) sec.

0.16 (± 0.02) sec.

0.21 (± 0.02) sec.

17

50.10 (± 0.01) sec.

0.20 (± 0.03) sec.

0.09 (± 0.01) sec.

0.16 (± 0.02) sec.

30

2

1.02 (± 0.09) sec.

42.10 (± 1.30) sec.

1.09 (± 0.09) sec.

1.60 (± 0.09) sec.

31

3

1.12 (± 0.10) sec.

43.45 (± 1.46) sec.

1.17 (± 0.08) sec.

1.94 (± 0.13) sec.

32

4

3.49 (± 0.21) sec.

90.91 (± 3.08) sec.

3.27 (± 0.21) sec.

9.20 (± 0.82) sec.

32

528.00 (± 0.87) sec.

280.44 (± 6.45) sec.

58.54 (± 1.10) sec.

64.14 (± 3.71) sec.

8

2

1.53 (± 0.07) sec.

11.42 (± 0.23) sec.

0.81 (± 0.09) sec.

0.98 (± 0.05) sec.

93

1.28 (± 0.05) sec.

23.56 (± 0.36) sec.

0.75 (± 0.08) sec.

0.72 (± 0.04) sec.

11

40.61 (± 0.02) sec.

24.44 (± 0.32) sec.

0.52 (± 0.08) sec.

0.68 (± 0.07) sec.

13

50.29 (± 0.02) sec.

28.71 (± 0.47) sec.

0.32 (± 0.03) sec.

0.44 (± 0.06) sec.

20

22.49 (± 0.18) sec.

17.23 (± 1.72) sec.

3.26 (± 0.21) sec.

4.52 (± 0.31) sec.

21

3

19.31 (± 0.89) sec.

30.06 (± 1.96) sec.

16.25 (± 0.56) sec.

5.81 (± 0.39) sec.

24

4

21.31 (± 0.85) sec.

20.12 (± 2.01) sec.

50.46 (± 0.91) sec.

23.22 (± 0.80) sec.

26

5

11.90 (± 0.52) sec.

25.00 (± 1.75) sec. 3,701.25 (± 20.31) sec.

63.00 (± 2.13) sec.

23

20.20 (± 0.01) sec.

1.51 (± 0.15) sec.

0.19 (± 0.05) sec.

0.89 (± 0.04) sec.

27

3

0.21 (± 0.02) sec.

1.79 (± 0.17) sec.

0.21 (± 0.04) sec.

0.82 (± 0.04) sec.

29

40.14 (± 0.01) sec.

1.11 (± 0.14) sec.

0.16 (± 0.02) sec.

0.77 (± 0.04) sec.

30

50.08 (± 0.01) sec.

0.79 (± 0.11) sec.

0.16 (± 0.03) sec.

0.63 (± 0.02) sec.

352

621.23 (± 2.31) sec. 5,291.21 (± 24.33) sec.

798.20 (± 8.21) sec.

680.21 (± 4.12) sec.

393

886.14 (± 2.91) sec.

DNF 1,302.39 (± 10.04) sec.

430.99 (± 3.10) sec.

424910.26 (± 3.09) sec.

DNF 5,788.21 (± 25.42) sec.

604.49 (± 4.47) sec.

44

53,490.63 (± 6.89) sec.

DNF

20

2

1.87 (± 0.19) sec.

32.80 (± 0.90) sec.

3.92 (± 0.42) sec.

21

3

9.89 (± 0.79) sec.

79.56 (± 1.16) sec.

49.95 (± 1.89) sec.

4.99 (± 0.41) sec.

24

4

10.02 (± 0.90) sec.

77.37 (± 1.20) sec.

200.34 (± 3.55) sec.

10.11 (± 0.85) sec.

26

5

16.20 (± 1.44) sec.

101.02 (± 2.18) sec. 3,922.66 (± 17.16) sec.

79.22 (± 2.15) sec.

18

2

4.23 (± 0.35) sec.

261.19 (± 4.74) sec.

9.88 (± 1.14) sec.

7.90 (± 0.21) sec.

21

3

6.96 (± 0.39) sec.

823.35 (± 6.45) sec.

62.10 (± 2.43) sec.

10.12 (± 0.30) sec.

24

432.77 (± 1.02) sec.

DNF

1,166.42 (± 8.70) sec.

42.29 (± 0.38) sec.

27

5201.00 (± 1.42) sec.

DNF

DNF

312.10 (± 2.51) sec.

31

2

16.73 (± 1.31) sec.

112.42 (± 1.39) sec.

39.92 (± 1.36) sec.

21.10 (± 0.71) sec.

32

3

17.33 (± 1.48) sec.

151.04 (± 1.46) sec.

44.86 (± 1.82) sec.

23.54 (± 0.59) sec.

32

417.32 (± 1.29) sec.

96.34 (± 1.21) sec.

36.21 (± 1.27) sec.

22.16 (± 0.62) sec.

34

5

18.11 (± 1.50) sec.

77.00 (± 0.00) sec.

32.05 (± 1.14) sec.

26.35 (± 0.91) sec.

38

2

34.50 (± 0.82) sec.

941.23 (± 5.12) sec.

110.79 (± 4.28) sec.

28.1 (± 1.22) sec.

423

290.90 (± 1.74) sec.

DNF

DNF

344.80 (± 4.67) sec.

46

4

1,984.52 (± 7.21) sec.

DNF

DNF

2,721.11 (± 6.72) sec.

49

5 4,016.59 (± 13.36) sec.

DNF

DNF

DNF

214

2

2.12 (± 0.21) sec.

17.34 (± 0.38) sec.

5.82 (± 0.27) sec.

20.21 (± 0.71) sec.

214

32.24 (± 0.20) sec.

17.23 (± 0.32) sec.

6.21 (± 0.24) sec.

19.20 (± 0.49) sec.

214

42.25 (± 0.21) sec.

17.80 (± 0.35) sec.

8.11 (± 0.27) sec.

15.70 (± 0.42) sec.

214

52.39 (± 0.22) sec.

17.60 (± 0.38) sec.

8.23 (± 0.23) sec.

13.10 (± 0.31) sec.

4*327,162 4*2.13

4*950,327 4*2.05

4*713,319 4*1.18

4*1,936,748 4*1.88

4*1,365,961 4*2.14

4*3,214,986 4*1.52

4*2,987,624 4*1.72

4*4,519,330 4*1.93

4*1,632,803 4*22,301,964 4*2.88

4*2,523,386

4*7,918,801 4*1.88

4*4,033,137 4*27,933,062 4*2.47

DNF 4,289.75 (± 21.08) sec.
3.57 (± 0.29) sec.

実験結果には 10 回の実行時間の平均値と標準偏差を載せる．

4 評価実験
本節では BnM 法の実行速度を実験的に評価する．
比較手法：我々は BnM 法を BnB1 [28]，Maplex2 [20]，および

KpLeX3 [16] の 3 つの最先端の既存手法と比較する．すべての実験は Intel Xeon Gold 6246R CPU 3.40 GHz and 128 GiB RAMを搭載したマシン上で C/C++によるシングルスレッドプログラ
ムとして実装し，コンパイルオプションを “-O3” とした．また
1：BnB のソースコード: https://github.com/JimNenu/codekplex
2：Maplex のソースコード: https://github.com/ini111/Maplex
3：KpLeX のソースコード: https://github.com/huajiang-ynu/kplex

データセット： 本稿では Network Repository [29] で公開されている 22 の実グラフデータセットを用いる．表 1 に詳細を示す．
表の αmax と γ はそれぞれ最大 k-plex の大きさと次数分布の偏りを示しており，γ が大きいときグラフは低次のノードを多く持つ．紙面の都合上，小さなソーシャルネットワークに対する実験結果については省略する．

4. 1 実行時間の評価
表 1 に最大 k-plex を出力するまでに要した実行時間を示す．
実行に 10,000 秒以上掛かった場合は DNF とした．また既存手法 [20, 28] と同様に，k は 2 から 5 とした．BnM 法は正確な最

3

10

2

10

1

10

0

10

−1

10

4

10

5

Number of nodes

10

6

10

10

10

BnB

Maplex

0

−1

−2

−3

10

4

(a) soc-lastfm

10

5

Number of nodes

10(b) soc-pokec

6

10

4

10

3

10

2

10

1

10

0

10

−1

10

KpLeX

Running time [sec.]

10

10Running time [sec.]

4

Running time [sec.]

Running time [sec.]

BnM
10

4

10

5

Number of nodes

106(c) soc-ﬂixster

10

1

10

0

10

−1

10

−2

10

−3

10

4

10

5

Number of nodes

106(d) soc-livejournal

図 2: スケーラビリティ
表 2: node-merging 法の効果

ときには効率的に最大 k-plex に含まれないノードを削除する．

Graphsk

4*soc-LiveMocha

2

16.23 sec.

DNF 0.05%

3

40.8 sec.

DNF 0.03%も効率的に最大 k-plex を発見できる．

4

529.31 sec.

DNF 0.03%

4. 2 node-merging 法の効果

5 8899.67 sec.

DNF 0.03%

4*soc-douban

4*soc-gowalla

4*soc-twitter-follows

4*soc-youtube

4*soc-delicious

4*soc-FourSquare

BnM BnM (w/o merge)

GRR

これにより BnM 法は巨大なソーシャルネットワークに対して

本節では BnM 法の実行時間を node-merging 法を適用しない

2

0.16 sec.

358.84 sec. 0.04%

3

0.16 sec.

291.14 sec. 0.05%

4

0.14 sec.

285.92 sec. 0.04%

証する．表 2 は各アルゴリズムの実行時間であり，BnM (w/o5

0.1 sec.

202.42 sec. 0.05%

2

1.02 sec.

9,537.81 sec. 0.01%

merge) は node-merging 法を用いない BnM 法を示す．また DNF

3

1.12 sec.

DNF 0.01%

は実行が 10,000 秒以内に終了しなかったことを示す．表 2 に

4

3.49 sec.

DNF 0.04%

は node-merging 法によってどの程度グラフが小さくなったかを

5

28 sec.

DNF 0.03%

示すグラフ削減比 (GRR) も併せて示している．ここで GRR は2

1.53 sec.

2,156.17 sec. 0.06%

3

1.28 sec.

7,829.11 sec. 0.01%

40.61 sec.

7,356.13 sec. 0.01%

50.29 sec.

7,001.65 sec. 0.01%

BnM (w/o merge) と比較して BnM 法は平均して実行時間の2

2.49 sec.

3,801.64 sec. 0.06%

319.31 sec.

7,301.28 sec. 0.25%

99.96%を削減した．表 2 から分かるように，node-merging 法

421.31 sec.

7,016.16 sec. 0.26%

は BnM (w/o merge) と比較して計算するエッジ数の 99.93%を

5

11.9 sec.

5,792.48 sec. 0.20%

削減している．これらの結果は node-merging 法によってグラ2

0.2 sec.

371.38 sec. 0.05%

フサイズが小さくなったことにより，BnM の探索空間が大幅

3

0.21 sec.

480.72 sec. 0.04%

4

0.14 sec.

301.18 sec. 0.05%

50.08 sec.

266.02 sec. 0.03%

safe-to-merge ノードをマージしたあとのグラフ G∗ の大きさに

2

621.23 sec.

DNF 0.05%

依存するが，GRR は平均して 0.07% 程度であるため，τ は非3

886.14 sec.

DNF 0.04%

4

910.26 sec.

DNF 0.04%

常に小さいことと考えられる．したがって，node-merging 法は5 3490.63 sec.

DNF 0.03%

BnM 法と比較することで，BnM 法のアプローチの有効性を検BnM (w/o merge) に対する BnM 法が参照したエッジ数の割合として計算する．

に削減されていることを示す．定理 1 で用いた τ の大きさは

safe-to-merge ノードをマージすることにより BnM 法の効率性

大 k-plex を出力するが，BnB，Maplex，および KpLeX に対しを効果的に向上させる．

てそれぞれ最大 305.2，311.0，および 9.53 倍高速である．特に4. 3 スケーラビリティ

BnM 法は soc-pokec や soc-livejournal のような γ が大きいグラ

BnM のスケーラビリティについて評価する．図 2 は表 1 中フに対して既存手法より非常に効率的である．定理 1 で示したの 4 つの大きなソーシャルネットワークである soc-lastfm，soc-

通り，BnM 法は既存手法に対して時間計算量が小さいため効率

pokec，soc-ﬂixster，および soc-livejournal の実行時間をノード的であり，これは実験結果と合致する．

数を変えながら計測した．我々は Metropolis-Hastings Random

BnB，Maplex，および KpLeX と異なり，最も計算コストがWalk [30] を用いて元のグラフからノードを 1 × 104 ，3 × 104 ，大きくなる k = 5 であっても BnM 法は多くのデータセットで

1 × 105 ，3 × 105 ，および 1 × 106 個サンプリングし，k = 5 と最大 k-plex を発見している．既存手法のグラフ削減アルゴリズ

してそれぞれのグラフに対する実行時間を評価する．なお実行ムは次数分布の偏りに関係なく全てのノードを繰り返し探索しに 10,000 秒以上要した場合の結果は図 2 には載せていない．

て削除するノードを計算する．しかし実世界のソーシャルネッ

BnM 法はほとんどのグラフにおいてノード数に対してほぼ線

トワークには低次のノードが多く，これらのノードがスケーリ

形なスケーラビリティを示す．これらの結果はソーシャルネット

フリー性により最大 k-plex になる可能性が低い．そのためグラワークの次数分布の偏りによるものである．定理 1 で示した通り，

フ削減アルゴリズムは大きな k に対して最大 k-plex の発見が困

BnM 法は γ が十分に大きいとき O(τ |VG |(1 + 1/(α − k)(γ−2) )難である．それに対して 3. 3 節で議論した通り，BnM 法はス≈ O(τ |VG |) 時間で実行可能である．つまり γ が大きいとき

ケールフリー性に基づく node-merging 法を用いて，γ が大きい

BnM 法は良いスケーラビリティを持ち，表 1 に示す通り実世

界の大規模なソーシャルネットワークは大きな γ を持つことが多い．したがって，BnM 法は大規模なソーシャルネットワーク
においてほぼ線形なスケーラビリティを実現する．

5 おわりに[12][13]

本稿では，大規模ソーシャルネットワークのための効率的な最大 k-plex 探索アルゴリズムである BnM 法を提案する．BnM 法はソーシャルネットワークのスケールフリー性に着目し，safe-[14]

to-merge ノードをマージすることでグラフを縮小する．我々の実験において BnM 法は最先端の既存手法と比較して最大 k-plex
を高速に発見できることを確認した．本稿を通じて高速な BnM[15]法を用いることで，多くのソーシャルネットワーク分析およびアプリケーションの性能向上が期待できる．

謝

[16]

辞

本研究の一部は JST さきがけ (JPMJPR2033)，JSPS 科研費(JP22K17894), JSPS 科研費 (JP22J10972) の支援を受けたもので
ある．
文

献

[1] B Balasundaram, Sergiy Butenko, I. Hicks, and S Sachdeva. Clique
Relaxations in Social Network Analysis: The Maximum k-Plex
Problem. Operations Research, 01 2007.
[2] Yoshiaki Okubo, Makoto Haraguchi, and Etsuji Tomita. Structural Change Pattern Mining Based on Constrained Maximal k-Plex
Search. In Jean-Gabriel Ganascia, Philippe Lenca, and Jean-Marc
Petit, editors, Discovery Science, pages 284–298, Berlin, Heidelberg,
2012. Springer Berlin Heidelberg.
[3] Alessio Conte, Tiziano De Matteis, Daniele De Sensi, Roberto
Grossi, Andrea Marino, and Luca Versari. D2K: Scalable Community Detection in Massive Networks via Small-Diameter k-Plexes.
KDD ’18, page 1272–1281, New York, NY, USA, 2018. Association
for Computing Machinery.
[4] Seidman, Stephen B and Foster, Brian L. A Graph-theoretic Generalization of the Clique Concept. Journal of Mathematical sociology,
6(1):139–154, 1978.
[5] Uffe Wiil, Nasrullah Memon, and Panagiotis Karampelas. Detecting
New Trends in Terrorist Networks. pages 435–440, 08 2010.
[6] Balabhaskar Balasundaram. Graph theoretic generalizations ofclique: Optimization and extensions. Texas A&M University, 2007.
[7] Michael G. Noll and Christoph Meinel. Web Search Personalization Via Social Bookmarking and Tagging. In Karl Aberer, Key-Sun
Choi, Natasha Noy, Dean Allemang, Kyung-Il Lee, Lyndon Nixon,
Jennifer Golbeck, Peter Mika, Diana Maynard, Riichiro Mizoguchi,
Guus Schreiber, and Philippe Cudré-Mauroux, editors, The Semantic Web, pages 367–380, Berlin, Heidelberg, 2007. Springer Berlin
Heidelberg.
[8] David Carmel, Naama Zwerdling, Ido Guy, Shila Ofek-Koifman, Nadav Har’el, Inbal Ronen, Erel Uziel, Sivan Yogev, and Sergey Chernov. Personalized Social Search Based on the User’s Social Network.
In Proceedings of the 18th ACM Conference on Information andKnowledge Management, CIKM ’09, page 1227–1236, New York,NY, USA, 2009. Association for Computing Machinery.
[9] George Danezis, Tuomas Aura, Shuo Chen, and Emre Kıcıman. How
to share your favourite search results while preserving privacy andquality. In International Symposium on Privacy Enhancing Technologies Symposium, pages 273–290. Springer, 2010.
[10] Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-Attention Graph
Pooling. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors,
Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages
3734–3743. PMLR, 09–15 Jun 2019.
[11] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral Clustering with Graph Neural Networks for Graph Pooling. In

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]
[27]
[28]

[29]

[30]

Proceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020.
Benjamin Doerr, Mahmoud Fouz, and Tobias Friedrich. Why Rumors Spread so Quickly in Social Networks. Commun. ACM,
55(6):70–75, jun 2012.
Amirhosein Bodaghi and Jonice Oliveira. The Theater of Fake News
Spreading, Who Plays Which Role? A Study on Real Graphs of
Spreading on Twitter. Expert Systems with Applications, 189:116110,
2022.
Yang Wang, D. Chakrabarti, Chenxi Wang, and C. Faloutsos. Epidemic Spreading in Real Networks: an Eigenvalue Viewpoint. In
22nd International Symposium on Reliable Distributed Systems,
2003. Proceedings., pages 25–34, 2003.
Lin Wang and Guan-zhong Dai. Global Stability of Virus Spreading in Complex Heterogeneous Networks. SIAM Journal on Applied
Mathematics, 68(5):1495–1502, 2008.
Hua Jiang, Dongming Zhu, Zhichao Xie, Shaowen Yao, and ZhangHua Fu. A New Upper Bound Based on Vertex Partitioning for the
Maximum K-plex Problem. In Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence, IJCAI-21, pages
1689–1696. International Joint Conferences on Artiﬁcial Intelligence
Organization, 8 2021.
Hannes Moser, Rolf Niedermeier, and Manuel Sorge. Exact Combinatorial Algorithms and Experiments for Finding Maximum kPlexes. Journal of combinatorial optimization, 24(3):347–373, 2012.
Mingyu Xiao, Weibo Lin, Yuanshun Dai, and Yifeng Zeng. A Fast
Algorithm to Compute Maximum k-Plexes in Social Network Analysis. In Thirty-First AAAI Conference on Artiﬁcial Intelligence, 2017.
Peilin Chen, Hai Wan, Shaowei Cai, Jia Li, and Haicheng Chen. Local Search with Dynamic-threshold Conﬁguration Checking and Incremental Neighborhood Updating for Maximum k-Plex Problem. In
Proceedings of the AAAI Conference on Artiﬁcial Intelligence, volume 34, pages 2343–2350, 2020.
Yi Zhou, Shan Hu, Mingyu Xiao, and Zhang-Hua Fu. Improving
Maximum k-Plex Solver via Second-Order Reduction and Graph
Color Bounding. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, volume 35, pages 12453–12460, 2021.
James Abello, Mauricio G. C. Resende, and Sandra Sudarsky. Massive Quasi-Clique Detection. Proceedings of the 5th Latin American
Symposium on Theoretical Informatics, page 598–612, 2002.
Immanuel M Bomze, Marco Budinich, Panos M Pardalos, and Marcello Pelillo. The Maximum Clique Problem. Handbook of Combinatorial Optimization, 4:1–74, 05 1999.
Benjamin McClosky and Illya V Hicks. Combinatorial Algorithms
for the Maximum k-Plex Problem. Journal of Combinatorial Optimization, 23(1):29–49, 2012.
Mingyu Xiao and Shaowei Kou. Exact Algorithms for the Maximum Dissociation Set and Minimum 3-Path Vertex Cover Problems.
Theor. Comput. Sci., 657(PA):86–97, January 2017.
Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. On
Power-Law Relationships of the Internet Topology. SIGCOMM
Comput. Commun. Rev., 29(4):251–262, 08 1999.
Albert-László Barabási and Réka Albert. Emergence of Scaling in
Random Networks. Science, 286(5439):509–512, 1999.
Réka Albert and Albert-László Barabási. Statistical mechanics ofcomplex networks. Reviews of modern physics, 74(1):47, 2002.
Jian Gao, Jiejiang Chen, Minghao Yin, Rong Chen, and Yiyuan
Wang. An Exact Algorithm for Maximum k-Plexes in Massive
Graphs. In Proceedings of the Twenty-Seventh International Joint
Conference on Artiﬁcial Intelligence, IJCAI-18, pages 1449–1455.
International Joint Conferences on Artiﬁcial Intelligence Organization, 7 2018.
Ryan Rossi and Nesreen Ahmed. The network data repository withinteractive graph analytics and visualization. In Twenty-Ninth AAAI
Conference on Artiﬁcial Intelligence, 2015.
Yingan Cui, Xue Li, Junhuai Li, Huaijun Wang, and Xiaogang Chen.
A Survey of Sampling Method for Social Media Embeddedness Relationship. ACM Comput. Surv., 02 2022. Just Accepted.