可変接続数下限を用いた孤立性 j-核

人工知能学会研究会資料
SIG-FPAI-B502-15
可変接続数下限を用いた孤立性 j-核
Isolated Variable j-Core Based on
Vertex-Dependent Connection Lower Bound
趙奇1
Q. ZHAO
原口誠 1 ∗
M. HARAGUCHI
大久保好章 1 富田悦次 2
Y. OKUBO E. TOMITA
北海道大学大学院情報科学研究科
Graduate School of Information Science and Technology, Hokkaido University
2
電気通信大学先進アルゴリズム研究ステーション
Advanced Algorithms Research Laboratory, The University of Electro-Communications
1
Abstract: In this paper, we are concerned with a problem of enumerating maximal isolated
cliques (MIC) in a given undirected graph. Each target to be extracted is defined as a maximal
subset X of vertices which is a clique and satisfies an isolatedness. Our isolation concept is based
on the notion of variable j-coreness which imposes a connection lower bound depending on each
vertex in X. Based on a standard clique enumerator, we design a depth-first algorithm for the
problem. In our algorithm, we can prune many hopeless cliques from which we can never obtain
our solution. It is noted that our solution MICs can be divided into two classes, fixpoint solutions
and non-fixpoint solutions, where the latter ones are not trivial to detect. Based on a degree
descending order of vertices, we show a theoretical property of non-fixpoint MICs and present an
eﬀective method of detecting them.
1
はじめに
所与のネットワークからの，孤立性の高い密な部分
グラフの抽出に向けて，本稿では，極大な孤立性の高
いクリークの全列挙問題について考察する．
ネットワークからのコミュニティ抽出においては，現
実的なコミュニティ構造のモデルとして疑似クリーク
を考えることが自然である [1]．これまで，様々な疑似
クリークの列挙法が提案され，それらを用いたコミュ
ニティ抽出が議論されてきたが，疑似クリークの総数
は一般に膨大となり，とりわけ，オーバーラップする多
数の疑似クリーク群が観測されることから，結果とし
てコミュニティの境界が不鮮明なものとなる．こうし
た問題を解決するためには，境界が鮮明な疑似クリー
ク，すなわち，外部との接続性を考慮した孤立性の高
い疑似クリークのモデル ([5]) が不可欠である．その足
掛かりを得るために，本稿では，孤立性の高いクリー
ク抽出問題について議論する．
孤立性を考慮したクリークのモデルとして，c-孤立
クリークが提案されている [4]．そこでの抽出対象は，
∗ 連絡先：原口誠
〒 060-0814 札幌市北区北 14 条西 9 丁目
北海道大学大学院情報科学研究科
E-mail: [email protected]
極大クリークの中で孤立性の高いものに限定されるが，
言うまでもなく，極大でないクリークの中にも，孤立
性の高いものが存在することから，多数の孤立クリー
クが見落とされていることが想像できる．また，その
孤立性の定義は，コミュニティ全体としての外部接続
数を考慮したものであり，個々の頂点の孤立性は考慮
されない．結果として，外部との接続度合いの高い少
数の頂点を含むクリークが抽出されてしまう．
本稿で考察する極大孤立性クリークは，こうした問
題点を解消したモデルと位置付けることができる．極
大孤立性クリークは，孤立性を有するクリークの中で
極大なものを指し，文献 [4] の枠組みでは見落とす多
くの孤立クリークを救済できる．また，本稿での孤立
性は，コミュニティを構成する各頂点に依存した内部
接続数下限を要請する可変 j-核性に基づくものであり，
適切な内部接続数下限関数を定めることで，個々の頂
点の孤立性を制御できる．
本稿では，所与のグラフ G における極大孤立性ク
リークの全列挙問題に対するアルゴリズムについて考
察する．詳細については本論で述べるが，極大孤立性
クリークは G のある極大クリークの可変 j-核として
出現する．よって，素朴な列挙法として，G の極大ク
リーク C を列挙し，その可変 j-核を求めることが考
− 49 −
えられる．極大クリーク列挙については，文献 [2] に
代表される実用上十分高速なアルゴリズムが提案され
ており，また，可変 j-核演算も，|C| と最大次数の積
のオーダで実行できる．しかし，解となる極大孤立性
クリークを包含する極大クリークは一般に複数存在す
ることから，解の重複枚挙の回避が不可欠となり，そ
の処理は単純ではない．本稿では，標準的な深さ優先
クリーク探索処理に，極大孤立性クリークが有する性
質に基づく枝刈り機構と解の判定機構を組み込むこと
で，極大孤立性クリークを重複なく高速に全列挙する
手法を提案する．
2
準備
V を頂点集合，Γ(v) を頂点 v ∈ V の隣接頂点集合
とする無向グラフを G = (V, Γ) と表す．特に，Γ(v)
は v 自身を含まないとする．|Γ(v)| を頂点 v の次数
と呼び，deg(v) で参照する．頂点集合 X ⊆ V と頂点
v ∈ X について，Γ(v) ∩ X を ΓX (v) と表し，|ΓX (v)|
を degX (v) で参照する．
頂点集合 X ⊆ V について，X に誘導される G の部
分グラフを G[X] と表す．特に，G[X] における任意の
異なる頂点のペアが隣接する時，G[X] を G のクリー
クと呼ぶ．表記を簡略化するため，クリーク G[X] を，
それを誘導する頂点集合 X により参照する．
クリーク X ⊆ V と頂点 v ∈ (V \ X) について，
X ∪ {v} がクリークである時，v を X の候補頂点と呼
び，X の候補頂点の集合を Cand(X) と表す．なお，以
下では，頂点集合 X ∪ {v} を Xv と略記する．定義よ
∩
り，Cand(X) = v∈X Γ(v) であり，特に，X ⊆ Y な
るクリーク X と Y について，Cand(X) ⊇ Cand(Y )
となる．
3
3.1
可変 j-核と孤立性 jτ -核
いま，頂点集合を定義域，非負の実数を値域とする
関数 j : V → R≥0 を考える．頂点集合 X ⊆ V につい
て，各頂点 x ∈ X が degX (x) ≥ j(x) を満たす時，X
は可変 j-核性を有するという．定数 j-核性とは異なり，
可変 j-核性は，部分グラフ内部の接続数下限を頂点毎
に定めたものであり，より柔軟に密な部分グラフを扱
うことができる．
定数 j-核性と同様，可変 j-核性を有する頂点集合 X
と Y について，X ∪ Y もまた可変 j-核性を有すること
は容易にわかる．よって，任意の頂点集合 X ⊆ V につ
いて，可変 j-核性を有する X の最大部分集合が存在
し，これを G[X] の可変 j-核と呼ぶ．以下では，G[X]
の可変 j-核を corej (X) で参照する．
定数 j-核同様，可変 j-核についても次の単調性が成
り立つ．
観察 1 (可変 j-核演算の単調性) X1 ⊆ X2 なる任
意の頂点集合 X1 , X2 ⊆ V について，corej (X1 ) ⊆
corej (X2 ) である．
頂点集合 X の可変 j-核を求める手続きは単純であ
る．具体的には，G[X] において次数が j(x) 未満の頂
点 x を X から順次除去する操作を繰り返す．一般に，
ある頂点の除去は，その他の頂点次数を減少させるこ
とから，こうした頂点除去操作を，除去可能な頂点が
なくなるまで繰り返せばよい．
3.2
孤立性を考慮した可変 jτ -核
可変 j-核においては，関数 j により頂点毎に部分グ
ラフ内部の接続数下限を与えるが，これは，外部への
接続数上限を暗に考慮していることを意味する．内部
接続数の増加に伴い，外部接続数は必然的に減少する
ことから，本稿では，頂点次数のうち，内部接続に用
いる割合の下限を定めるパラメータ τ (0 < τ ≤ 1.0) を
用いて，任意の頂点 x ∈ V について，
可変 j-核
jτ (x) = τ · deg(x)
所与のグラフ G = (V, Γ) の頂点集合 X ⊆ V につい
て，各頂点 v ∈ X の G[X] における次数が定数 j 以
上である，すなわち，degX (v) ≥ j を満たす時，X は
(定数) j-核性を有するという [3]．
定義より，定数 j-核性を有する頂点集合 X と Y に
ついて，X ∪ Y もまた定数 j-核性を有する．すなわち，
任意の頂点集合 X ⊆ V について，定数 j-核性を有す
る X の最大部分集合が存在し，これを G[X] の定数
j-核と呼ぶ [3]．
本稿では，これを拡張した可変 j-核性の概念を新た
に導入する．
(1)
なる関数 jτ を定義する．頂点 v の外部接続数の上限
値は (1.0 − τ ) · degG (v) で与えられることから，τ を
大きくすることで，外部との接続が殆ど無い可変 jτ -核
が得られることになる．特に，τ = 1.0 の場合は，外
部接続数が 0 となり，すなわち，完全孤立状態の可変
jτ -核となる．この様に，τ は jτ -核の孤立性を制御す
ることから，ここではそれを孤立性パラメータと呼ぶ．
なお，jτ -核演算においても，観察 1 で述べた単調性
が成り立つことは言うまでもない．
頂点集合 X の可変 jτ -核を求める手続きは，先の
可変 j-核と同様であり，G[X] において次数が jτ (x)
未満の頂点 x を X から順次除去する操作を繰り返せ
− 50 −
procedure JCore(G, X, τ ):
begin
Create vert with |X|-elements;
head = 0; tail = |X| − 1;
for each v ∈ X do
degX (v)
then // v is a core candidiate
if τ ≤ deg(v)
vert[tail] = v; d(v) = degX (v); index(v) = tail;
tail--;
else // v must be removed
vert[head] = v; d(v) = degX (v); index(v) = head;
head++;
endif
endfor
head = 0;
while head ≤ tail do
v = vert[head];
for each w ∈ ΓX (v) do
if tail < index(w) then // w is a core candidate
d(w)--;
d(w)
if τ < deg(w) then // w must be removed
tail++;
if tail ̸= index(w) then
vert[index(w)] = vert[tail]; vert[tail] = w;
endif
endif
endif
endfor
head++;
endwhile
while head ≤ |X| − 1 do
print vert[head]; head++;
endwhile
end
定義 2 (極大孤立性クリーク列挙問題)
所与のグラフ G = (V, Γ) と孤立性パラメータ τ につ
いて，G の極大孤立性クリークをすべて抽出する問題
を極大孤立性クリーク列挙問題と呼ぶ．
G の極大クリークは，必ずしも jτ -核性を満たす頂点
集合とはならないことに注意する．一般に，極大孤立
性クリークは，ある極大クリークの可変 jτ -核として出
現する．よって，それらの素朴な列挙法として，G の
極大クリーク C を列挙し，その可変 jτ -核，すなわち，
corejτ (C) を求めることが考えられる．極大クリーク
列挙については，文献 [2] に代表される実用上十分高
速なアルゴリズムが提案されており，また，corejτ (C)
の演算も，|C| と最大次数の積のオーダで実行できる
ことから，こうした素朴なアプローチも然程悪くない
様に思える．しかし，解となる極大孤立性クリークを
包含する極大クリークは一般に複数存在することから，
解の重複枚挙の回避が不可欠となり，その処理は単純
ではない．以下では，標準的な深さ優先クリーク探索
処理に，極大孤立性クリークが有する性質に基づく枝
刈り機構を組み込むことで，極大孤立性クリークを重
複なく高速に全列挙する手法を与える．
図 1: 可変 jτ -核抽出アルゴリズム
5
ばよい．可変 jτ -核抽出アルゴリズムの疑似コードを
図 1 に示す．アルゴリズム中，vert は頂点の配列であ
り，頂点 v が格納された vert におけるインデックス
は index(v) で参照できるものとし，また，頂点 v の
次数情報も d(v) で参照できるものとする．
主要な処理は，後半の while ループであり，そこで
は，X 中の各頂点について，その隣接頂点をチェック
する．よって，グラフ G の最大次数を D とすると，計
算量は |X| · D のオーダとなる．
4
本稿で提案する極大孤立性クリークの全列挙法は，標
準的な深さ優先クリーク探索を基礎とする．探索過程
で得られるクリークが，後に議論する性質を満たした
段階で，それが解として出力すべき極大孤立性クリー
クか否かの判定を行う．また，クリーク探索過程にお
いて，解に到達し得ないクリークが生成された場合は，
直ちにバックトラックすることで，無駄な探索枝の展
開を抑制する．
5.1
極大孤立性クリーク
前節で議論した孤立性を考慮した可変 jτ -核に基づ
き，ここでは，本稿における抽出ターゲットとなる極
大孤立性クリークについて述べ，その列挙問題を定義
する．
定義 1 (極大孤立性クリーク)
G = (V, Γ) をグラフ，τ を孤立性パラメータとする．
G のクリーク X ⊆ V が次を満たす時，X を孤立性ク
リークと呼ぶ：X は jτ 核性を満たす，すなわち，任
意の頂点 v ∈ X について，|X| > τ · deg(v) である．
特に，X を真に包含する G の孤立性クリークが存
在しない時，X は極大であると言い，これを極大孤立
性クリークと呼ぶ．
極大孤立性クリークの全列挙
深さ優先クリーク探索
所与のグラフ G = (V, Γ) の任意のクリークは，V に
関する集合列挙木を辿ることで，重複なく，かつ，完
全に列挙することができる．
いま，V 上の全順序 ≺ を仮定し，任意の頂点集合は
≺ に従いソーティングされているとする．ここで，頂
点集合 X の最後尾の頂点を tail(X) で参照する．
クリーク X は，Cand(X) 中の候補頂点 v を用いて，
より大きなクリーク Xv へと拡張できる．クリークは
逆単調性を有する，すなわち，クリークの任意の部分
集合もまたクリークであるから，初期クリーク X = ∅
(Cand(X) = V ) から，こうした拡張処理を繰返すこ
とで，すべてのクリークを生成することができる．そ
の際，X の拡張処理に用いる頂点 v ∈ Cand(X) を
− 51 −
tail(X) ≺ v なるものに限定することで，重複のない
クリーク列挙が実現される．
上記処理は，クリーク探索に関する標準的な手法と
なっており，特に，メモリ効率の観点から，実際の探
索過程では深さ優先戦略が採用される．
5.2
有望なクリーク
極大孤立性クリークの全列挙手法の詳細を議論するに
あたり，可変 jτ -核性に関するいくつかの重要な性質を
明らかにしておく．なお，以下の議論では，クリーク X
とその候補頂点集合 Cand(X) について，corejτ (X ∪
Cand(X)) を ext(X) と表記する．
観察 2 クリーク X と，X ⊆ Y なる孤立性クリーク
Y について，
観察 2 より，有望なクリーク X(⊆ ext(X)) につい
て，極大孤立性クリーク Y は必ず ext(X) の部分集合と
して出現する．よって，X の拡張処理は，ext(X) \ X
中の頂点のみを用いて行えば十分である．以下では，
ext(X) \ X を K(X) と表記し，これを X に関する
K-候補集合と呼ぶ．
X が不動点解 (X = ext(X)) の時，かつ，その時に
限り，K(X) = ∅ となることは容易にわかる．
観察 4 K(X) = ∅ なる有望なクリーク X は極大孤立
性クリークである．
一方，この逆は必ずしも真ではなく，X が極大孤立
性クリークであっても，K(X) = ∅ になるとは限らな
い．つまり，不動点解以外の解を漏れ無く抽出するた
めには，以下で議論する K(X) ̸= ∅ なる X の処理が
重要となる．
X ⊆ Y ⊆ ext(X) = corejτ (X ∪ cand(X))
5.4
が成り立つ．
証明： Y は X ⊆ Y なるクリークであるから，X ⊆
Y ⊆ X ∪ cand(X) なる関係がある．いま，可変 jτ -核
演算の単調性から，corejτ (Y ) ⊆ corejτ (X ∪ cand(X))
であり，特に，Y は可変 jτ -核性を有することから，
Y = corejτ (Y ) となる．よって，X ⊆ Y ⊆ ext(X) =
corejτ (X ∪ cand(X)) が示される．
上記性質は，クリーク X の拡張処理によって解を得
るための必要条件を与える．X ⊆ ext(X) の場合，X
を拡張することで解に到達できる可能性がある．一方，
X ̸⊆ ext(X) の場合，X の拡張処理によって解が得ら
れる可能性はないことから，X の拡張処理を直ちに，
かつ，安全に打ち切ることができる．以下では，前者
の場合の X を有望なクリークと呼ぶ．
5.3
不動点解としての極大孤立性クリーク
観察 2 より，(有望な) クリーク X を真に包含する孤
立性クリーク Y が存在する場合は，X は ext(X) の真
部分集合，すなわち，X ⊂ ext(X) であることが容易
にわかる．逆に，X = ext(X) = corejτ (X ∪ cand(X))
の場合，X は可変 jτ -核性を満たし，かつ，それを真
に包含する孤立性クリークが存在しないことを意味す
る．よって，X それ自身が極大な孤立性クリークとな
り，解として出力すべきものであることがわかる．
観察 3 クリーク X について，X = ext(X) が成り立
つ時，X は極大孤立性クリークであり，特にこれを不
動点解と呼ぶ．
偽 K-候補を伴う極大孤立性クリーク
有望なクリーク X について，K(X) ̸= ∅ なる場合を
考える．K(X) が空でないことから，X を真に包含す
る孤立性クリークが存在する様に思えるが，こうした
場合でも，X が極大孤立性クリークとなる可能性があ
る．すなわち，K(X) 中の頂点は見かけだけの偽 K-候
補であり，実際の拡張処理には何ら寄与しない．こう
した偽候補を検出し，不動点解ではない解 X を抽出す
るためには，K(X) 中の任意のクリーク C について，
X ∪ C が可変 jτ -核性を満たさないことを確かめれば
十分であるが，その計算負荷は無視できない．そこで，
本稿では，頂点間の順序を工夫することで，偽候補を
伴う極大孤立性クリークの性質を明らかにし，それに
基づく偽候補の検出法を与える．
いま，所与のグラフ G の頂点集合 V 上に，次数降
順の全順序 ≺ を導入する 1 ．
任意の u, v ∈ V について，
u ≺ v ⇔ deg(u) ≥ deg(v).
以下では，任意の頂点集合は ≺ に従ってソーティング
されていると仮定する．
有望なクリーク X の拡張には K-候補集合 K(X) 中
の頂点を用いることは先に述べたが，特に，tail(X) ≺ x
なる頂点のみを考えればよい．つまり，こうした頂点
の集合を N L(X) とすると，
N L(X) = {x ∈ K(X) | tail(X) ≺ x}
となる．
ここで，偽候補を伴う極大孤立性クリークについて，
次の性質が成り立つ．
1 次数が同じ頂点間には適当な順序を与える．
− 52 −
観察 5 K(X) ̸= ∅ なる極大孤立クリーク X について，
N L(X) = ∅ である．
証明： N L(X) ̸= ∅ と仮定する．X は可変 jτ -核性
を有するクリークであるから，任意の頂点 x ∈ X に
ついて，degX (x) = |X| − 1 ≥ τ · deg(x) である．こ
こで，頂点順序 ≺ より，任意の頂点 v ∈ N L(X) につ
いて，deg(x) ≥ deg(v) が成り立つ．また，N L(X) ⊆
Cand(X) より，v は X のすべての頂点と隣接する
から，degXv (v) = |X| > |X| − 1 ≥ τ · deg(v) を得
る．これより，Xv は可変 jτ -核性を有するクリークと
なるが，このことは X の極大性と矛盾する．よって，
N L(X) = ∅ であることが示される．
観察 5 より，探索過程における有望なクリーク X に
ついて，K(X) ̸= ∅，かつ，N L(X) = ∅ である場合の
み，X が極大孤立性クリークか否かを調べればよいこ
とがわかる．その際，素朴には，部分グラフ G[K(X)]
の任意の (非空な) クリーク C について，X ∪ C の可
変 jτ -核性を調べる必要があるが，実際にはそれをせず
に済ますことが可能である．
5.5
偽 K-候補の検出処理
有望なクリーク X について，K(X) ̸= ∅，かつ，
N L(X) = ∅ であると仮定する．いま，∅ ⊂ C ⊆ K(X)
なるクリーク C で，X ∪ C が可変 jτ -核性を満たすも
のが存在するか否かを調べたい．この時，次の性質が
成り立つ．
観察 6 C ⊆ K(X) なる X ∪ C が可変 jτ -核性を有す
るために必要な各頂点 x ∈ C の G[K(X)] における最
小次数は
max{0, τ · deg(x) − |X|}
で定義される関数 jK(X) : K(X) → R≥0 を考える．
頂点 x ∈ K(X) について，jK(X) (x) は，x を含む
K(X) の部分集合であるクリーク C と X の和集合が
可変 jτ -核性を有するために必要な G[K(X)] における
最小次数を与える．よって，こうした可変 jτ -核性を
有する X ∪ C が存在するならば，C は G[K(X)] の
極大クリーク Qi の部分集合であり，特に，Qi の可変
jK(X) -核の部分集合となる．
ここでの主目的は，X が偽候補を伴う極大孤立性ク
リークであるか否かを確かめることであるから，可変
jτ -核性を有する X を考えれば十分である．この時，Qi
の可変 jK(X) -核，すなわち，corejK(X) (Qi ) について，
corejK(X) (Qi ) ̸= ∅ の場合は，X ∪ corejK(X) (Qi ) は jτ 核性を有するクリークとなり，X が極大孤立性クリー
ク (解) ではないことがわかる．
逆に，G[K(X)] の任意の極大クリーク Qi について，
corejK(X) (Qi ) = ∅ ならば，X は抽出すべき極大孤立
性クリークとなり，結果として K(X) 中の頂点が偽候
補であったことが判明する．
上記処理においては，G[K(X)] の極大クリークを列
挙する必要があるが，その負荷はそれほど高くならない
ことが期待できる．なぜなら，K(X) ⊆ cand(X) より，
K(X) 中の頂点 v は，任意の x ∈ X と隣接する必要が
あり，こうした頂点 v は高々minx∈X {deg(x)}−|X|+1
しか存在しない．また，K(X) ̸= ∅，かつ，N L(X) = ∅
となるのは，X のサイズがある程度大きくなってから
であると予想されることから，実際の K(X) のサイズ
は然程大きくはならず，効率的な極大クリーク列挙器
を用いることで，高速に処理可能であると期待できる．
さらに，実際は，極大クリークに至る途中段階のク
リーク C において，corejK(X) (C) ̸= ∅ になり次第，X
が解ではないと判定できることから，こうした処理を
組み込むことで，X が解であるか否かの判定をさらに
高速化できることを付け加えておく．
である．
証明： C ⊆ K(X) なる頂点集合 X ∪ C が可変 jτ -核性
を有するためには，頂点 x ∈ C の G[X ∪C] における次
数 degX∪C (x) は，少なくとも τ ·deg(x) 必要となる．い
ま，Xx はクリークであるから，G[C] における x の次
数 degC (x) は少なくとも τ · deg(x) − |X| であることが
わかる．よって，C ⊆ K(X) より，G[K(X)] における x
の次数もまた，少なくとも τ ·deg(x)−|X| となる．ここ
で，τ ·deg(x)−|X| は負の値をとることもあるが，頂点
次数は非負であるから，これは max{0, τ ·deg(x)−|X|}
と表せる．
以下，各頂点 x ∈ K(X) について，
jK(X) (x) = max{0, τ · degG (x) − |X|}
(2)
6
極大孤立性クリークの全列挙アル
ゴリズム
これまでの議論に基づく極大孤立性クリークの全
列挙アルゴリズムの疑似コードを図 2 に示す．図中，
MaxCliqueEnum(·) は，引数として与えたグラフの
すべての極大クリークを順次出力する手続きである．
なお，当疑似コードは，解の列挙処理全体の流れに重
点を置いて記述されたものであり，実際の計算手続きに
おいては様々な工夫が可能である．例えば，手続き Expand における N ewExt は，N ewExt ← corejτ (Xv ∪
(K ∩ N ewCand)) としてよい．N ewCand を (拡張前
の) K 中の頂点に限定することで，jτ -核演算の対象と
なる頂点集合がより小さくなり，結果としてより小さ
− 53 −
procedure Main(G, τ ):
[Input] G = (V, Γ): an undirected graph.
τ : an isolation parameter (0 < τ ≤ 1.0).
[Output] All maximal jτ -cored cliques.
[Global Variables] G, τ
begin
Sort V in degree decsending order;
Expand(∅, V , V );
end
procedure Expand(X, Ext, Cand):
begin
K ← Ext \ X;
N L ← {v ∈ K | tail(X) ≺ v};
if K = ∅ then
Output X; // as a fixpoint solution
return;
endif
if N L = ∅ then
if X is j(x)-cored then
if SolWithFalseCand(X, K) == true then
Output X; // as a solution with false candidates
endif
endif
return;
endif
for each v ∈ N L
N ewCand ← Cand ∩ Γ(v);
N ewExt ← corejτ (Xv ∪ N ewCand);
if Xv ⊆ N ewExt then
Expand(Xv, N ewExt, N ewCand);
endif
endfor
end
procedure SolWithFalseCand(X, K):
begin
Let jK be a function defined as
jK (x) = max{0, τ · degG (x) − |X|} for each x ∈ K;
for each Q presented by MaxCliqueEnum(G[K]) then
if corejK (Q) ̸= ∅ then
return false; // X is not a solution
endif
endfor
return true; // X is a solution with false candidates
end
図 2: 極大孤立性クリーク列挙アルゴリズム擬似コード
な N ewCand が得られることが期待できる．これは，
Xv を拡張する際の候補頂点が減少することを意味し，
探索処理全体の効率化に寄与する．
また，手続き SolWithFalseCand において極大ク
リーク列挙木を用いているが，先に述べた通り，実際は，
生成途中段階のクリーク C において，corejK(X) (C) ̸= ∅
になり次第 false を返すことで，X が解でないこと
をより早期に検出可能となる．
7
おわりに
本稿では，孤立性疑似クリークの高速列挙に向けた
第一歩として，極大孤立性クリークの全列挙問題に対
する高速アルゴリズムについて議論した．クリークの
拡張処理が解へ到達するための必要条件を明らかにし，
それに基づく枝刈り機構を組み込むことで，無駄な探
索枝の展開処理を強力に抑制する．また，偽候補を伴
う解の検出法を与えることで，不動点解以外の解も漏
れ無く抽出可能である．
著者等は先行研究 [6, 7] において，グラフの構造変
化の観点から孤立性クリーク，および，孤立性疑似ク
リークの抽出を行っている．特に，[6] での解は本稿に
おける抽出対象をより限定したものに相当し，その実
験結果から，極大孤立性クリークも相当数存在するこ
とが示唆される．一方，先行研究では，可変 jτ -核性や
その性質を陽に利用した探索処理を行っていないこと
から，提案アルゴリズムの有効性については今後の実
験により確認したい．提案アルゴリズムは現在実装の
最終段階にあり，実験結果については口頭発表時に報
告したいと考えている．
参考文献
[1] Pattillo, J., Youssef, N. and Butenko, S.: Clique
Relaxation Models in Social Network Analysis, Handbook of Optimization in Complex Networks: Communication and Social Networks,
Springer Optimization and Its Applications 58,
pp. 143 – 162, 2012
[2] Tomita, E., Tanaka, A. and Takahashi, H.: The
Worst-Case Time Complexity for Generating All
Maximal Cliques and Computational Experiments, Theoretical Computer Science 363(1), pp.
28 – 42, Elsevier, 2006
[3] Batagelj, V. and Zaversnik, M.: An O(m) Algorithm for Cores Decomposition of Networks,
CoRR 2003., cs.DS/0310049 OpenURL
[4] Ito, H. and Iwama, K.: Enumeration of Isolated
Cliques and Pseudo-Cliques, ACM Transactions
on Algorithms, 5(4), Article 40, 2009
[5] ジェイ泓杰・原口誠・大久保好章・富田悦次：j核性を持つ極大疑似クリークの全列挙，第 13 回情
報科学技術フォーラム - FIT 2014, 第一分冊, pp.
33 - 35, 2014
[6] エラウィンディサラ・原口誠・大久保好章・富田悦
次：クリーク全列挙に基づく構造変化検出アルゴリ
ズム，情報処理学会研究報告，Vol. 2011-MPS-087
No. 32, 2012
[7] Okubo, Y., Haraguchi, M. and Tomita, E.:
Structural Change Pattern Mining Based on
Constrained Maximal k-Plex Search, Proc. of the
15th Int’l Conf. on Discovery Science - DS’12,
Springer-LNAI 7569, pp. 284 – 298, 2012
− 54 −

Download Report