各種の疑似クリーク列挙アルゴリズムの実験的性能比較

各種の疑似クリーク列挙アルゴリズムの実験的性能比較

ジェイ 泓杰

大久保 好章

原口 誠

∗

Hongjie ZHAI

Yoshiaki OKUBO

Makoto HARAGUCHI

北海道大学大学院情報科学研究科

Graduate School of Information Science and Technology, Hokkaido University

Abstract: In the problem of finding pseudo-cliques, namely k-plexes, it becomes harder to enu-merate all of them as we allow more number of disconnection among vertices in them. Particularly, there often exist a huge number of possible solutions with medium or small size which cannot be regarded as dense vertex sets. To overcome the difficulty, the authors have proposed two algo-rithms, J-CoreMaxKPlex and MetaClique, which can exclusively enumerate dense pseudo-cliques among them. A constraint on connectivity based on the notion of j-core is taken into account in the former and a structural constraint based on the notion of meta-cliques in the latter. In this report, we empirically observe performance of the algorithms for several graphs and then show their characteristics, comparing with an improved standard maximal k-plex enumerator.

1

はじめに

グラフやネットワークにおいて，クリークは最も密 なコミュニティを表現しており，高速なクリーク列挙 器が提案されている [1, 7]. 一方，現実のコミュニティ 検出では，隣接関係に関して少数の例外を許した疑似 クリークも必要となり，クリークの緩和モデルとして これまで様々ものが考察されてきた [2]．本稿では，そ うした緩和モデルの一つである k-plex [3, 5] に密結合 性を要求する制約を加味したモデルの有効性と課題に ついて論じる． k-plex とは非接続数上限制約を満たす無向グラフの 頂点集合であり，特に k = 1 の場合はクリークとなる． k の値がごく小さな場合は，クリーク列挙器に準じる 実行時間を期待でき，多くの先行研究では 1≤ k ≤ 4 程度の値に対してその有効性を論じてきた．一方，よ り大きな k に対しては，長い鎖や，決して密とは言え ない頂点集合も k-plex 制約を満たし，それゆえに解の 総数が容易に爆発してしまう．疎な可能性を排除する 制約が必要である． 非パス性制約・サイズ制約を付加的に追加した k-plex 列挙器（標準 k-plex 枚挙器とよぶ）でもある程度そう した k-plex を排除できるが，本稿では誘導グラフの 密結合を直接的に保障する接続数下限制約を導入した j-核性 k-plex について考察する．すなわち，k-plex X は，X の誘導グラフにおける頂点次数は j 以上でなけ ∗_{連絡先：原口 誠}   〒 060-0814  札幌市北区北 14 条西 9 丁目   北海道大学大学院情報科学研究科    E-mail: [email protected] ればならない．j 核性制約から，k-plex の問題点の一 つであった鎖や小さすぎる頂点集合は自然に排除され る．j-核性 k-plex は，全域的 j-核と呼ばれる j-核性を 持つ最大の頂点集合の部分集合として出現するが，逆 に，全域的 j-核における一部の k-plex Y は 必ずしも j-核性を持つとは限らない．そうした現象は，Y のサ イズが大なところでは決して起こらず，（厳密にはサイ ズが j + k 未満でのみ）生じる．この事実に基づき， k-plex の成長・拡大過程において，将来 j-核性を持つ k-plex に成長できる可能性を持たないものを枝刈るこ とが可能になる．これを局所的な j-核性 の検証と呼ぶ が，探索アルゴリズムとしては オーバーヘッド 要因で あり，解の総数とともにそのコストと枝刈効果を標準 k-plex との比較により評価する． 一方，これまでの（疑似）クリーク列挙手法では，密 に重なりあう（疑似）クリークを，全体を一つにまと めることなく独立した（疑似）クリークとして列挙し， それゆえに，解の総数を増大させる要因の一つになっ ていた．重なり具合にもよるが，全体として疑似クリー クとしてみなせる場合は複数のクリークを一つの疑似 クリークとしてまとめて提示する方が，解の総数を抑 え，より意味のある塊として提示できる．この立場か ら，メタクリーク，すなわちクリークを構成要素とす るクリークで全体が頂点集合として k-plex となるもの を k-クリーク族とよび，その中で極大なもののみを列 挙する手法について考察する [12]．j-核性制約とは異 なり，構造制約を課すことになる．j-核性 k-plex のと きと同様に，付加的な制約を課した k-plex を基準モデ ルとして，k-クリーク族 の総数と計算コストをテスト 人工知能学会研究会資料 SIG-FPAI-B404-05

する．k-クリーク族の場合，事前に部品となる極大ク リークを列挙しておく必要があり，そうしたオーバー ヘッドにも拘わらず高速列挙が可能となるかが一つの ポイントである．また，実際のネットワークにおいて， そうしたクリーク族の総数を調べることも，単純なト ライアングルの総数に基づく指標などと比較し，構造 面も考慮にいれた新たな構造指標として使うことも視 野にいれている．

2

準備

本稿では，多重辺，および，自己ループ辺を含まな い単純無向グラフを扱うものとし，以降ではこれを単 にグラフ，あるいは，ネットワークと呼ぶ． 頂点集合 V ，辺集合 E ⊆ V × V のグラフを G = (V, E) と表記する．G における頂点 v ∈ V の隣接頂 点集合を ΓG(v) とし，|ΓG(v)| を (G における) v の次 数と呼ぶ．頂点 v の次数を degG(v) で参照することも ある． グラフ G = (V, E) の頂点集合 X ⊆ V について， G[X] = (X, E∩ (X × X)) で定義されるグラフを，X による G の誘導部分グラフと呼ぶ．特に，G[X] にお ける任意の異なる頂点のペアが隣接する時，G[X] を G のクリークと呼ぶ．表記を簡略化するため，クリー ク G[X] を，それを誘導する頂点集合 X により参照 する． クリークの緩和モデルである k-plex は次の通り定義 される． 定義 1 (k-Plex) グラフ G = (V, E) の頂点集合 X ⊆ V を考える．こ こで，任意の x∈ X に対し，|X−Γ(v)| ≤ k である時， G[X] (または単に X) を k-plex と呼ぶ．特に X が連 結なとき連結 k-Plex と呼ぶ． k-Plex X と頂点 v /∈ X について，Xv = X ∪ {v} も k-plex となる時，v を X の (k-plex ) 候補と呼び， 候補集合を Cand(X) と記す． 極大 k-Plex X は部分 k-Plex Xj にその候補 xj+1∈ Cand(Xj) を追加する操作を繰り返すことにより構成 できる．極大 k-Plex 枚挙器は，k-Plex 列 {Xj}j を 探索パスとして持つ探索木の展開により，全ての極大 k-Plex を重複なく列挙することで実現できる． ∅ = X0⊂ X1= X0x1⊂ X2= X1x2⊂ · · · ⊂ Xn= Xn₋₁xn={x1, ..., xn} k-Plex 増加列 一方，連結 k-Plex X の場合は連結部分集合列の構 成法が基本となる． ∅ = X0⊂ X1= X0x1⊂ X2= X1x2⊂ · · · ⊂ Xn = Xn−1xn={x1, ..., xn} ⊂ · · · ⊂ X ただし，Γ(xn)∩ Xn₋₁̸= ∅． 連結集合増加列において，X が k-Plex の場合は，列中 の連結集合 Xj は全て k-Plex である．すなわち，xj+1 は Xj の k-plex 候補でもある．よって，連結 k-Plex の探索においては，k-Plex の候補で Xj と直接隣接し た k-Plex 候補だけを選択・追加するだけで良い．

3

サイズ下限制約付き極大

k-Plex

抽出アルゴリズム

定義からも明らかな通り k-plex は逆単調性を有する ことから，k-plex 抽出のみが目的であれば包含関係のも とで極大なものを抽出すれば十分である．極大 k-plex の列挙アルゴリズムとしては，永きに渡り Pemp [5] の みが知られていたが，著者らは文献 [13] において，よ り高速化されたアルゴリズムを提案した．これを極大 k-plex 抽出の基準モデルとする実験を行なうにあたり， ここではその概略についてまとめる． 定義に忠実に従い極大な k-plex を抽出すると，そこ には，疑似クリークとして明らかに望ましくない頂点 集合が膨大に含まれる．極端な場合，独立集合やパス さえも極大 k-plex となり得るが，これらが抽出に値す る疑似クリークであるとは考え難い．このことを踏ま え，文献 [13] では次に定義される極大 k-plex 抽出問 題に対する列挙アルゴリズムが提案されている 定義 2 (極大 k-plex 抽出問題) グラフ G = (V, E) と k > 1 なる自然数 k について， 極大 k-plex 抽出問題とは，次の条件を満たす G の極 大 k-plex X ⊆ V をすべて列挙するタスクである： (1) 非自明性：|X| > k，(2) 連 結 性： G[X] は連結， (3) 非パス性： G[X] はパスでない． アルゴリズム Pemp は，非自明性と連結性のみを満た す極大 k-plex を抽出対象とするが，MaxKPlex ではさら に非パス性を考慮することで，明らかに不要な k-plex をターゲットから除外している． MaxKPlex は，既に得られた k-plex の拡張処理を再 帰的に繰返す深さ優先探索により，極大 k-plex を列 挙する．特にそこでは，解となる極大 k-plex 族を真 k-plex 性 に基づいて分割し，各領域に属する k-plex が有する頂点間距離に関する性質を利用した探索を行 なうことで，全体の列挙処理を高速化している． 後に議論する j-核性制約，および，メタクリーク制 約を考慮したアルゴリズムは，k-plex を抽出対象とす る点では同様であるが，解となる k-plex のクラスが異 なり，パラメータ設定により抽出クラスを一致させる ことはできない．しかし，それぞれの所与のパラメー タ設定から，解となる k-plex のサイズ下限値 α が決 まることから，MaxKPlex によりサイズ α 以上の極大 k-plex を候補として抽出し，それを後処理することで，

それらシステムと同様の解を得る素朴なアプローチは 可能である．そこで，本稿では，サイズ下限制約を設 けた MaxKPlex を，MS-MaxKPlex と呼び，比較対象の 基準モデルとする． 具体的には，MaxKPlex の探索処理に，下限サイズ α による分枝限定操作を組込むことで，サイズが α に満 たない極大 k-plex に到達する拡張処理を枝刈るものと する．

4

j-

核性を有する極大

k-Plex

抽出

アルゴリズム

k-plex 抽出においては，連結性を考慮することで，出 力すべき解の総数は大幅に減少するが，先に述べた通 り，それでもなお膨大な数の解を許してしまう．本節 では，j-核性制約によって可能な解の数を削減した，よ り効率的な疑似クリークの列挙法について述べる． まず，ここでの抽出ターゲットを次の通り定める． 定義 3 (j-核性極大連結 k-Plex) グラフ G = (V, E) の頂点集合 X ⊆ V を考える．こ こで，任意の頂点 v∈ X に対して，degG[X](v)≥ j の とき，X は j-核性を有するという．また，j-核性を有 する最大の頂点集合を j-核 [4] と呼ぶ． 解： j-核性極大連結 k-Plex X を パラメー タ j, k に対する解として定める． j-核とは，次数に関する下限値を設定し，誘導グラ フにおける各頂点の次数が下限制約を満たす頂点集合 のうち，最大のものを指す．すなわち，j-核性は，抽 出ターゲットとなる疑似クリークに対する必要条件で あり，少なくとも全体の j-核に属さない頂点は考察の 対象外となる．これは，k の値を上げたときに無力で あった伝統的な k-Plex 枚挙器と比較して，無駄な頂点 集合を最初から枝刈するのと等価である． 大きな塊を抽出する観点からは，先に j-核をとり，そ の中での密結合部分を検出するトップダウンな方法論 も有望である．しかし，ここでは，比較的に小規模だ が従来の検出器では困難であった疑似クリークにター ゲットを絞っており，先に j-核に絞り込んだ上で，ボ トムアップに疑似クリークを組み立てていく方式によっ て j-核性極大連結 k-Plex を列挙するものとする． 抽出アルゴリズムの詳細については文献 [11] に譲る が，以下で探索処理におけるいくつかのポイントを述 べておく． まず，サイズが大きな k-Plex は j-核性を持つこと を指摘しておこう． 観察 1 ： |X| ≥ j + k な k-plex X は j-核性である． すなわち，k-plex は，サイズが大な場合には妥当な クリーク緩和モデルであることがわかる．問題はサイ ズが小な k-plex で生じ，本稿では j-核性によって，疑 似クリークとはみなせない極大 k-Plex を排除する． k≤ |X| < j + k の場合，j-核性までは主張できない が，連結 k-Plex の構成に関して有益な下記の事実が成 り立つ． 観察 2 ： |X| ≥ k な k-plex に対し，Cand(X) ⊆ D1(X)，ただし，Dℓ(X) は X から（最短）距離 ℓ で 到達できる頂点集合を表す． すなわち，k + j >|X| ≥ k の範囲では，現在の k-Plex X と隣接した頂点のみを，X に追加可能な候補 として考えておけば，連結 k-Plex の構成を目的とする 限り十分であることがわかる．これに加えて，j-核性 まで勘案すると，次の通りさらに k-Plex 候補を削減で きる． 観察 3 ： j +k >|X| ≥ k なる 連結 k-Plex X に対し， Cand(X)⊆ D1(X)．さらに，y∈ Cand(X)−corej(X∪

Cand(X)) ならば Xy を含む j-核性 連結 k-Plex は存 在しない．ただし，corej(Z) は Z の j-核を表す． 上記の事実により，実際の追加可能な候補は k-Plex 候補からさらに絞り込まれ，j-核性 k-Plex に拡大され る可能性を持つものだけに限定できる． |X| < k の場合は，k-Plex 候補は距離 1 以内とは限 らないが，k≤ |X| < k +j の場合と同様に，「X から遠 くない点」に限定した誘導グラフにおける j-核を求め ることにより，X を拡大してできる j-核性 k-Plex に 含まれることがありえない点を排除することができる． 観察 4 ： 連結 k-Plex X で|X| < k なものを考える． (4-1) X から距離が k−|X|+2 以上の w に対し，Xw を含む連結 k-Plex は存在しない． (4-2) U (X) = corej ( X∪ k−|X|+1 ∪ i=1 Di ) とする．w ∈ Cand(X)−U(X) に対し，Xw を含む j-核性連 結 k-Plex は存在しない．X ⊆ U(X) のとき， U1(X) = U (X)∩ D1(X) が「実際に追加可能な 候補」となる． (4-3) X−U(X) ̸= ϕ のとき，X を含む j-核性連結 k-Plex は存在しない． X と素な U1(X) の要素 u は，あくまでも Xu を含 む j-核性連結 k-Plex が存在する可能性があることのみ を保障する．したがって，「実際に追加可能な候補」u を追加する過程で Xu を含む j-核性連結 k-Plex が存

在しないことが判明する場合があり，それは事実 (4-3) の条件，すなわち，j-核計算による点消去が X の点に まで及ぶ場合である． 以上の議論をまとめよう．j-核性極大連結 k-Plex Z に至る構成列 ϕ = X0⊂ X1⊂ · · · ⊂ X_|Z|= Z s.t. Xi= Xi−1xi において，途中の Xiは j-核性とは限らない．実際，j-核 性制約は単調でも逆単調でもなく，本稿においては， 「j-核性連結 k-Plex に成長する可能性」のある候補のみに 絞り込む計算を行っている．また特に，U (Xi= Xi−1xi) の計算は，U (Xi₋₁) から再帰的に求まることにも注意 したい．このために，探索ノードとしての Xi には， U (Xi) も保持させておく必要がある． 全体の処理の流れにおいては，まず前処理として全 体の j-核をとり，処理対象をその誘導グラフに限定す る．全体の j-核は複数の連結成分に分解されるので，j-核性極大連結 k-Plex の生成は j-核の連結成分 C 毎に 行なうものとする． 各連結成分 C に関する探索過程においては，クリー ク探索の高速化に多大に寄与する「右候補枝刈」を導入 している．すなわち，重なりあう極大クリーク C1, C2 の共通部分 C1∩ C2に表れる頂点は，重なり合わない C1−C2もしくは C2−C1中の点のみを種にして極大ク リークへと成長させることが可能である．k-Plex に対 しても以下で述べるほぼ同様な性質が言える． 観察 5 (右候補枝刈)： X を連結 k-Plex, u∈ U1(X) , Ru = {y ∈ U(X) | y ∈ Γ(u), X−Γ(u) ⊆ Γ(y)} と

する．Ru の部分 Z で Z∪ X が k-plex ならば XuZ も k-plex ．つまり，極大連結 k-Plex は u を含めて U1(X)−Ru の候補を追加することにより生成できる． X において追加すべき候補は U1(X)−Ru に属する 頂点にさらに絞り込まれる．右候補枝刈によって極大 k-Plex の生成が妨げられることはなく，また，求める 解は j-核性極大 k-Plex であることから，右候補枝刈は， 解の生成に関して安全な枝刈規則となっている． 以降，上述のアルゴリズムを J-CoreMaxKPlex と呼 ぶ．

5

k-Plex

性を満たす極大メタクリー

ク抽出アルゴリズム

本節では，メタクリーク制約によって，構造的な観 点から抽出対象を定めた疑似クリーク列挙手法につい て述べる． k-plex は，その誘導部分グラフにおける各頂点の非 接続数の上限を定めた疑似クリークであるが，ここで はこうした頂点集合が，重複する極大クリークの集ま りとして構成されるモデルを考え，これを k-クリーク 族と呼び，形式的には次の通り定義する． 定義 4 (k-極大クリーク族 (k-MCS)) 所与のグラフ G における任意の極大クリークの族を C = {C1, C2, . . . , CN} とする．この時，次を満たす C の部分族_{M = {Ci} 1, . . . , Cim} を，C に関する k-極大 クリーク族と呼ぶ： k-plex 性：∪Ci∈MCi は k-plex である． 極大性：_{M は，条件 (1) を満たす C の極} 大な部分族である． C を構成部品と考えると，k-クリーク族とは，k-plex を構成可能な極大な部品集合となる．以下では，部品 集合から構成可能な k-クリーク族を列挙する問題につ いて考える． k-plex の逆単調性から，k-クリーク族M を構成す る任意の部品 (極大クリーク) ペアは必ず k-plex を構 成する．よって，部品集合_{C = {C1}, C2, . . . , CN} の各 部品を頂点とし，任意の Ci, Cj ∈ C について，Ci∪ Cj が k-plex を構成する時に，辺 (Ci, Cj) を作成するこ とで構築される k-クリークグラフ G′= (V′=C, E′⊆ C × C) を考えると，k-クリーク族 M は，G′ _のクリー ク，すなわち，メタクリーク (クリークに関するクリー ク) を構成することがわかる．このことから，k-クリー ク族の列挙問題は，k-plex 制約を満たす G′ の極大ク リーク探索問題と等価となる．クリークの列挙処理に ついては，[1, 7] 等をはじめとして，実用上十分高速な アルゴリズムが知られていることから，k-クリーク族 の列挙においても，その技術を活かしたアルゴリズム 設計が可能となる． 所与の k の値に対して，部品となる極大クリークの サイズが比較的大きな場合は，k-クリーク族が十分密 な塊を形成することが期待できる．一方，部品サイズ がそれほど大きくない場合には，必ずしもそうはなら ないことから，こうした場合においても，より密な塊 を形成する k-クリーク族を抽出可能とするために，部 品間の重複度合いをボンド値 [6] により評価する． 定義 5 (ボンド値) 任意の部品 Ci, Cj ∈ C について，Ci と Cj 間のボン ド値 Bond(Ci, Cj) を Bond(Ci, Cj) = _|C|C_ii∩C_∪Cj_j|_| と定め る． ここでは，ボンド値の下限制約 b を与えることで， k-plex 性を満たすと同時に，Bond(Ci, Cj) > b を満た す部品間にのみ辺を有する k-クリークグラフを考える． 所与のグラフ G における k-クリーク族の列挙処理 の流れは次の通りである．部品の最小サイズ s とボン ド下限値 b に対し，G におけるサイズ s 以上の極大ク

表 1: グラフデータ詳細 グラフ名 頂点数 辺数 密度 GEOM 7343 11898 0.00044 ca-GrQc 5242 14484 0.00105 WattStrg 50000 500000 0.00040 リークを，既存の高速アルゴリズムにより列挙して部品 族_{C を得る．次に，k-plex 性とボンド値下限制約を満} たす任意の部品間に辺を作成し，k-クリークグラフ G′ を構築する．こうして得られた G′ において，k-plex 性を満たす極大メタクリークを列挙することで，解と なるすべての k-クリーク族を得る． 極大メタクリークの列挙は，k-plex 性を満たす頂点 集合の拡張処理を基本とする深さ優先探索により行な う．初期頂点集合 X =∅ を，Cand(X) 中の頂点によ り順次拡張し，解が得られる，もしくは，拡張処理が 続行できなくなった時点で，バックトラックして他の 頂点による拡張処理を繰返す． 以降，このアルゴリズムを MetaClique と呼ぶ．

6

実験

本節では，J-CoreMaxKPlex，および，MetaClique それぞれのアルゴリズムの特徴を，MS-MaxKPlex との 比較実験を通して観察する． 実験にはベンチマークとして広く公開されている論文 共著者ネットワークである GEOM [8] および ca-GrQc [9] と，Watts-Strogatzs モデル [10] に従って生成したス モールワールド性を有するネットワーク WattStrg を 用いた．各グラフの頂点数・辺数・密度を表 1 に，ま た，次数分布を図 1 にまとめる．

6.1

J-CoreMaxKPlex と MS-MaxKPlex の比

較

極大 k-plex に j-核性を考慮することの有用性を確 認するために，J-CoreMaxKPlex と MS-MaxKPlex によ り出力される解の総数を，種々の j および k の値にお いて観察する． j-核性を要請することで，出力される極大 k-plex の サイズは j + 1 以上となる．そこで，J-CoreMaxKPlex の入力パラメータ j に対して，MS-MaxKPlex の最小サ イズ制約を j + 1 に設定する．特に，サイズが k + j の極大 k-plex は，必ず j-核性を有することから，両者 の解総数の差異は，サイズが j + 1 以上，かつ，j + k 未満の範囲に存在する中規模の極大 k-plex の中で，j-核性の観点で密でないものの数となる． ✥ ✥ ✥ ✥ ✥ ✥ ✥✁✂✄ ✥✁✂☎ ✥✁✂✆ ✥✁✂✝ ✞ ✟ ✠ ✄ ☎ ✆ ✝ ✥ ◆ ✡ ☛ ☞ ✌ ✍ ✎ ✏ ✑ ✎ ✒ ✡ ✓ ✔ ✎ ✕ ❦ ✲ ✖ ✒ ✌ ✗ ✌ ✘ ❥ ✙✚✛✜✢✁ ✣❂✠ ✣❂✟ ✣❂✞ ✣❂ ✤ 図 2: GEOM における解総数 ✥ ✥ ✥ ✥ ✥✁✂ ✄ ✥✁✂☎ ✥✁✂✆ ✥✁✂✝ ✞ ✟ ✠ ✄ ☎ ✆ ✝ ✥ ◆ ✡ ☛ ☞ ✌ ✍ ✎ ✏ ✑ ✎ ✒ ✡ ✓ ✔ ✎ ✕ ❦ ✲ ✖ ✒ ✌ ✗ ✌ ✘ ❥ ✙✚✛✜✢✁ ✣❂✠ ✣❂✟ ✣❂✞ ✣❂ ✤ 図 3: ca-GrQc における解総数 各グラフにおいて，k を固定し，j を変動させた場 合の両システムによる解総数を，図 2∼図 4 にまとめ る．図中，実線は J-CoreMaxKPlex による結果，点線 は MS-MaxKPlex による結果を示している． 両システムによる解総数の差をより明確に示すため に，解総数の差分を直接プロットしたものが，図 5∼ 図 7 である． サイズが j + 1 以上，かつ，j + k 未満の範囲は，k の値が大きくなるにつれて広がるが，その範囲に属す る j-核性を満たさない極大 k-plex の数が指数的に増大 していることが見て取れる．ここで注目すべきことは， これら差分の挙動が，MS-MaxKPlex による出力総数の 挙動とほぼ同様である点である．このことは，サイズ j + 1 以上の極大 k-plex のほとんどが，サイズ j + k 未満であり，それらは j-核性の観点から密結合とは考 えられないものであったことを意味する．この様に，j-核性を考慮することで，こうした望ましくない膨大な 極大 k-plex を排除することが可能となる． j の値が大きくなるにつれて，解総数の差分は減少 していく傾向にあることから，サイズが比較的大な極 大 k-plex のみに注目する場合は，MS-MaxKPlex が出

✥ ✥ ✥ ✥ ✥ ✥ ✥ ✥ ❋ ✁ ✂ ✄ ☎ ✂ ✆ ✝ ✞ ❉✟ ✠✡✟✟ ✥ ✥ ✥ ✥ ✥ ✥ ✥ ❋ ✁ ✂ ✄ ☎ ✂ ✆ ✝ ✞ ❉✟ ✠✡✟✟ ✥ ✥ ✥ ✥ ✥ ✥ ✥ ✥ ❋ ✁ ✂ ✄ ☎ ✂ ✆ ✝ ✞ ❉✟ ✠✡✟✟ 図 1: 各グラフの次数分布 ✥ ✥ ✥ ✥✁✂✄ ✥✁✂☎ ✥✁✂✆ ✝ ✞ ✟ ✄ ☎ ✆ ✠ ✥ ◆ ✡ ☛ ☞ ✌ ✍ ✎ ✏ ✑ ✎ ✒ ✡ ✓ ✔ ✎ ✕ ❦ ✲ ✖ ✒ ✌ ✗ ✌ ✘ ❥ ✙✚✛✜✢✁ ✣❂✞ ✣❂✝ ✣❂ ✤ 図 4: WattStrg における解総数 図 5: GEOM における解総数の差分 ✥ ✥ ✥ ✥ ✥ ✥✁✂✄ ✥✁✂☎ ✥✁✂✆ ✥✁✂✝ ✞ ✟ ✠ ✄ ☎ ✆ ✝ ✥ ❉ ✡ ☛ ☛ ☞ ✌ ☞ ✍ ✎ ☞ ✏ ☛ ✑ ✏ ✒ ✓ ✔ ✡ ✏ ✍ ✕ ✓ ✖ ✗ ☞ ✌ ✘ ❥ ✲✙✚✛✜ ✁ ❦❂✠ ❦❂✟ ❦❂✞ ❦❂ ✢ 図 6: ca-GrQc における解総数の差分 ✥ ✥ ✥✁✂✄ ✥✁✂☎ ✥✁✂✆ ✝ ✞ ✟ ✄ ☎ ✆ ✠ ✥ ❉ ✡ ☛ ☛ ☞ ✌ ☞ ✍ ✎ ☞ ✏ ☛ ✑ ✏ ✒ ✓ ✔ ✡ ✏ ✍ ✕ ✓ ✖ ✗ ☞ ✌ ✘ ❥ ✲✙✚✛✜ ✁ ❦❂✞ ❦❂✝ ❦❂ ✢ 図 7: WattStrg における解総数の差分

10 100 1000 10000 100000 1e+06 1e+07 1e+08 1e+09 3 4 5 6 7 8 9 10 Number of Solution k-Plexes j-value k=5 k=4 k=3 k=2 図 8: GEOM における解総数 力する解を後処理することで，j-核性 k-plex を選別す るアプローチも不可能ではない．しかし，それらは従 来のクラスタリング手法でも十分検出可能であるとの 意味で，面白味はないとも考えられ，むしろサイズが 中規模なものの中にこそ，真に興味深いものが期待で きよう．j-核性の考慮は，それらを見つけ出すための ひとつの有望なアプローチになり得ると考えられる．

6.2

MetaClique と MS-MaxKPlex の比較

ここでは，所与のグラフにおける k-plex 抽出にお いて，メタクリーク制約を考慮することの効果につ いて観察する．具体的には，クリーク族の部品となる 極大クリークの最小サイズ j を種々変動させた際の MetaClique による解総数，および，計算時間を， MS-MaxKPlex によるそれらと比較する． 部品の最小サイズ j が決まると，出力される k-ク リーク族の頂点集合としてのサイズは j + 1 以上とな る1_{．よって，MetaClique の入力パラメータ j に対し} て，MS-MaxKPlex の最小サイズ制約を j + 1 に設定す ることで，MetaClique が出力する k-クリーク族に対 応する k-plex は，MS-MaxKPlex が出力するいずれか の極大 k-plex の部分集合となり，メタクリーク制約が もたらす効果が確認できる． 両者が出力する解の総数を図 8 と図 9 にまとめる． ここで，MetaClique のボンド下限制約は 0.1 である． メタクリーク制約により，MetaClique による解総数 が著しく減少していることがわかる．k が大きくなる につれてその度合いは指数的に大きくなっている．こ こで，解総数に対して k の値が及ぼす影響が，両者に おいて大きく異なる点は興味深い．MS-MaxKPlex の解 総数は，k の値に対して指数的に増大しているが，一 1_{単一部品からなるクリーク族は考えない．} 10 100 1000 10000 100000 1e+06 1e+07 1e+08 1e+09 3 4 5 6 7 8 9 10 Number of Solution k-Plexes j-value k=5 k=4 k=3 k=2 図 9: ca-GrQc における解総数 0.01 0.1 1 10 100 1000 3 4 5 6 7 8 9 10

Computation Time [sec.]

j-value k=4 k=3 k=2 図 10: GEOM における計算時間 方，MetaClique の解総数は比較的安定している．この ことは，クリーク族の総数が，グラフの特徴付けを与 える際の重要な指標のひとつになり得る可能性を示唆 していると思われる． 図 10 と図 11 に，両システムによる計算時間を示す． 図中，実線は MetaClique による結果，点線は MS-MaxKPlex による結果である．なお，この計算時間は，部品を生 成するためのクリーク列挙処理も含むものである． 解総数と同様，MetaClique による計算時間は k の 値に影響を受けず安定している．これらグラフにおい ては，部品生成処理のオーバーヘッドはほぼ無視でき ると考えられる． 今回の実験においては，ボンド制約下限値の違いに よる解総数・計算時間の挙動の違いは観測できなかっ た．その要因として，部品のペアに対してボンド制約 を課していることが挙げられる．これを部品集合に対 する制約とすることで，下限設定の違いがより顕著に 現れるものと思われる．

0.01 0.1 1 10 100 1000 10000 3 4 5 6 7 8 9 10

Computation Time [sec.]

j-value k=5 k=4 k=3 k=2 図 11: ca-GrQc に計算時間

7

おわりに

本稿では，極大連結 k-plex に対する現時点で最も高 速な標準列挙器と j-核性 k-plex の列挙器を主として解 の総数の観点から比較し，接続欠損数である ｋ の値 が大となるにつれ，総数において顕著な違いが現れる ことが明らかになった．これは列挙される解のチェック の手間を大幅に軽減させると同時に，探索時のオーバ ヘッドをかけたとしても，ターゲットを絞り込んだピ ンポイントな列挙が有利になることを示している．ま た，メタクリークに関しても同様な結果を得たが，特 に，解の総数が接続例外数パラメータ k に依存しない 点は興味深く，ネットワークの構造指標として従来の クリーク数に代わる可能性を持つと考えている．今後 の課題としては，ターゲットとなる頂点集合サイズと 各種パラメータの関係をより詳細に分析し，その結果 を探索手法として組み込み，小∼中規模の密な誘導グ ラフの探査性能を高めることである．大規模グラフに おいて，サイズが比較的に小∼中規模の密結合グラフ は通常の可視化やグラフクラスタリングでは実際的に 抽出困難であることを考えれば，こうした領域での探 査能力は今後ますます重要になると思われる．

参考文献

[1] Tomita, E., Tanaka, A. and Takahashi, H.: The Worst-Case Time Complexity for Generating All Maximal Cliques andComputational Experi-ments, Theoretical Computer Science 363(1), pp. 28 - 42, Elsevier, 2006.

[2] Pattillo, J., Youssef, N. and Butenko, S.: Clique Relaxation Models in Social Network Analysis,

Thai, M. T. and Pardalos, P. M. (eds.), Hand-book of Optimization in Complex Networks: Communication and Social Networks, pp. 143 -162, Springer, 2012.

[3] Seidman, S. B. and Foster, B. L.: A Graph Theo-retic Generalization of the Clique Concept, Jour-nal of Mathematical Sociology 6, pp. 139 - 154, Taylor and Francis, 1978.

[4] Seidman, S. B.: Network Structure and Mini-mum Degree, Social Networks, 5, pp. 269 - 287, 1983.

[5] Wu, B. and Pei, X.: A Parallel Algorithm for Enumerating All the Maximal k-Plexes, Proc. of the PAKDD 2007 Workshops, LNAI-4819, pp. 476 - 483, 2007.

[6] Omiecinski, E. R.: Alternative interest mea-sures for mining associations in databases, IEEE Transactions on Knowledge and Data Engineer-ing 15(1), pp. 57-69, 2003.

[7] Eppstein, D. and Strash, D.: Listing All Maxi-mal Cliques in Large Sparse Real-World Graphs, Proc. of the 10th Int’l Symposium on Experimental Algorithms SEA’11, LNCS6630, pp. 364 -375 (2011)

[8] Batagelj, V. and Mrvar, A.: Pajek Datasets,

http://vlado.fmf.uni-lj.si/pub/networks/data/, 2006.

[9] Leskovec, J. and Krevl, A.: SNAP Datasets: Stanford Large Network Dataset Collection, http://snap.stanford.edu/data, 2014. [10] Watts, D. J. and Strogatz, S. H.: Collective

Dy-namics of Small-World Networks, Nature 393, pp. 440 – 442, 1998.

[11] ジェイ 泓杰・原口 誠・大久保 好章・富田 悦次：誘導 グラフの次数下限制約に基づく疑似クリークの列 挙法，情報処理学会研究報告，Vol. 2014-MPS-100, No. 27, 2014.

[12] Zhai, H.: Enumeration of Maximal Clique Sets with Pseudo Clique Constraints, Master The-sis, Graduate School of Information Science and Technology, Hokkaido University, 2015.

[13] 大久保 好章・原口 誠：解集合の分割に基づく極 大 k-Plex 抽出の高速化，人工知能学会研究会資 料，SIG-FPAI-B403, pp. 48 – 55, 2015.