トランザクショングラフのクラスタリング

SCAN16と呼ばれる既存のハイパフォーマンスなグラフクラスタリングアルゴリズムの実装が存在し135、これがトランザクションのグラフに対して実行されます。 この実装ではコアとなるノードをまず決めて、そこから互いに二次の距離にあるノード間の構造的類似度に基いてクラスタを拡張していく仕組みを取っています。 以下にアルゴリズムの詳細を述べます。

アカウントの集合VVをノード、アカウント間の1000XEM以上の送金トランザクションに前述の重みを付けたもの(7.2節: アウトリンク行列を参照)をエッジEEとし、VVEEからなるグラフをGGとします。 トランザクショングラフGGを構成するアカウントを構造的類似度に基いてクラスタリングすることで、クラスタ、ハブ、外れ値を検出することができます。 アカウントuuとアカウントvv間の構造的類似度σ(u,v)\sigma(u,v)は以下の式で求まります。

σ(u,v)=Γ(u)Γ(v)Γ(u)Γ(v) \sigma(u,v) = \frac{|\Gamma(u)\cap\Gamma(v)|}{\sqrt{|\Gamma(u)||\Gamma(v)|}}

ここで.|.|はグラフの濃度(cardinality)(訳注: ノードの数)で、Γ(u)\Gamma(u)uu自身を含む構造的隣接ノード集合で、以下のように定義されます。

Γ(u)=vVu,vEu. \Gamma(u) = {v \in V | {u,v} \in E} \cup {u}.

NϵN_{\epsilon}は、所与の閾値ϵ\epsilonに基いて選ばれた、構造的類似性を持つアカウントの集合です。以下のように定義されます。

Nϵu=vΓ(u)σ(u,v)ϵ. N_{\epsilon}{u} = {v \in \Gamma(u) | \sigma(u,v) \geq \epsilon}.

コアノードは軸としてクラスタを拡張していくのに用いられ、以下のように定義されます。

Kϵ,μNϵ(u)μ K_{\epsilon,\mu} \Longleftrightarrow |N_{\epsilon}(u)| \geq \mu

μ\muは、コアとみなされるのに最低限必要な、条件ϵ\epsilonを満たす近隣のアカウントの数です。クラスタリングの間、コアアカウントを中心(pivot)にクラスタが形成されます。 クラスタの最初のメンバーはNϵN_{\epsilon}です。これはすなわちμ\muはクラスタの最小サイズをコントロールするものだということです。 NEMではμ\muは4でϵ\epsilonは0.3です。 特定のϵ,μ\epsilon,\muの元で、uuがコアであり、 vvNϵ(u)N_{\epsilon}(u)のメンバーであるとき、 「アカウントvvuuに対して構造的直接到達性(direct structure reachability)uϵ,μvu \mapsto_{\epsilon,\mu} v を持つ」と言います

μϵ,μvKϵ,μ(μ)vNϵ(μ) \mu \mapsto_{\epsilon,\mu}v \Longleftrightarrow K_{\epsilon, \mu}(\mu) \land v \in N_{\epsilon}(\mu)

SCANアルゴリズムの場合、 コアとなるアカウントを軸に、構造的直接到達性のあるアカウントを取り込んでいくことでクラスタを形成していきますが、 これには隣接するアカウント(一次の距離)及びそれに隣接するアカウント(二次の距離)との構造的類似度を計算する必要があります。

改良版SCANでは、軸から二次の距離にあるアカウントとの類似度のみを考慮します。 アカウントuuから二次の距離にあるアカウントの集合H(u)H(u)は以下で定義されます。

H(u)=vV(u,v)E(v,w)E H(u) = {v \in V|(u, v) \notin E \land (v,w) \in E }

ただしアカウントwwwNϵ(u)\uw \in N_{\epsilon}(u) \backslash {u}です。 軸から二次の距離にある各コアアカウントに対してクラスタが形成、すなわちコアアカウントの、基準エプシロン(ϵ\epsilon)を満たす近隣(epsilon neighbors i.e. (Nϵ)(N_{\epsilon}))がクラスタに加えられます。 このように、軸から二次の距離にあるアカウントに対して計算を行うときには、軸から構造的直接到達性を持つアカウントは計算対象から除外されます。

考慮対象となる、二次の距離にあるアカウントをどんどん広げていく際には、以下のの定義に基いて判定が行われます。

H(un)={vV(u,v)Evi=0n1Nϵ(ui)H(ui)}. H(u_n) = \left\{ v \in V|(u,v) \notin E \land v \notin \bigcup_{i=0}^{n-1}N_{\epsilon}(u_i) \cup H(u_i) \right\}.

全アカウントを処理した後、全ノードを以下に述べる基準に基いてチェックします。

  1. アカウントが複数のクラスタに属する場合、そのクラスタを結合する。
  2. その後、どのクラスタにも属さないアカウントを調べ、複数のクラスタと結合していればハブ、そうでなければ外れ値と判定する。

構造的類似性σ\sigmaの計算がアルゴリズム内でもっとも時間のかかるところですので、クラスタの拡張に際して二次の距離にあるアカウントのみを考慮することで計算負荷が減るというのがポイントです。

出力されたクラスタはNCDawareRankのレベル間近似度行列の作成に用いられます。 というのも、これがトランザクショングラフのほぼ完全に分解可能な(nearly completely decomposable)性質を反映するものであるからです。

5. http://db-event.jpn.org/deim2014/final/proceedings/D6-2.pdf

results matching ""

    No results matching ""