Gift history
Please access after login.


Wait a moment...

【NEM技術勉強会】7.4 トランザクショングラフのクラスタ化

767
3
2019-02-22 10:37:05
0.00 mXYM
(0)

前回は、PoIのインポータンスというのが、グーグル検索で使われているページランキングシステムとほぼ同じもので、NEMではより多くのアカウントから1000XEM以上送られた実績があるアカウントほどポイントが高くなることが分かりました。

 

さて、今回はNCDawareRankを計算する上で必要になるトランザクションの構造を計算するクラスタリングというものについてです。NTTソフトウエアの日本語の論文が引用されていたので、それを見ながら解説していきます。


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

 

トランザクショングラフ(ネットワーク構造)のクラスタ化には、SCANアルゴリズムの改良バージョンを使用します(日本語論文)。この方式では、コアノードを見つけてから、それと関係するノードをひとまとまりのクラスタとします。クラスタの定義には、ノード間の「類似性」を利用しています。類似性評価には、隣の隣(2ホップ)のノードまでを考慮します。

 

アカウントuとアカウントvの類似性は、以下の式で表せます。7.2のアウトリンクマトリックスで説明した、1000XEM以上のトランザクションを行ったことのあるアカウントをすべて調べ上げて、その中でuともvとも取引があるアカウントが占める割合を計算します。

難しい式が出てきましたが、同じ相手とXEMをやり取りしているアカウント同士(同じ取引所を使っていたり、同じ人から1000XEM以上の投げネムをもらっているなど)だと、σは1になり、まったく共通の取引アカウントが無い場合(取引所も違えば、同じ人とはネム取引もしていない)は0になります。

 

実際に共有しているアカウントの数Nは、以下の式で求めます。

例えば、εをNEMでは0.3としています。共通の取引アカウントの割合が3割以上ある、親密度の高いアカウントの数がN個ですよということで、Nが大きいほど他のアカウントとの取引が盛んかつ、共通の取引先が多い(つまり仲良しグループみたいなもの)ということです。このNの値が4以上あると、NEMではコアアカウントとして、クラスタリングの起点としています。

 

このあたりの説明は、論文の引用が多いのでがっつり割愛します。気になる人は、論文のほうにちゃんと書いてあるので読んでみてください。難しいですけどね。論文内の定義5から定義9によって、複数のクラスタと接続するハブノードや、どこにも属さない外れノードについても定義されています。

 

SCANにおいては、直接リンク関係があるノード同士の類似性を計算するのに、関連ノードを全部計算します。NEMで使用している改良版では、コアアカウントから2ホップ距離のアカウントまでだけ計算して計算量を減らします。

 

2ホップ距離というのは、例えば同じ取引所でXEMを買っているアカウント同士のことです。お互いに直接やり取りはなくて、同じ取引先を使っていれば2ホップです。ネムログの場合だと、同じ人から投げネムをもらっていれば2ホップ。直接投げたことがあれば1ホップという感じで、ネムログコミュニティーならだいたいみんなが2ホップ距離内にいると思います(ただし、インポータンス計算に使われるアカウントは、10000XEM以上承認残高があり、累計1000XEM以上の投げネムがあった場合のみですが)。

 

参考のために、SCAN(Algorithm1)とNEMの採用した改良SCAN(Algorithm2)のコードモデルをおいておきます。forやwhileループが分解されて高速化されている事が、分かるらしいです(僕にはよくわからない)。大規模計算では、ループを展開すると速くなることがあり、コンパクトな分かりやすいコードの方が時間がかかるということはよくあります。ループの繰り返し数や、ループの深さを一つ減らすだけで大きく時間を短縮できる場合が多いのです。

 

 

最終的に、グラフに所属するすべてのアカウントの属性が計算されます。

一つのアカウントが複数のクラスタに所属する場合には、それらのクラスタは合体されます。

どのクラスタにも属さないアカウントは、2つ以上のクラスタと接続があればハブアカウント。

ひとつしか接続がなければ外れアカウントと定義されます。

ここで、0というのはないはずです。そのアカウントはどのアカウントともXEM取引が無かったアカウントということになりますから、最初の1000XEM取引があるアカウントのみ考慮するところで弾かれているはずです。

2ホップ距離のノードのみを考慮することで、計算コストが削減できます。

なぜなら、2つのアカウントの接続構造類似度を示すσの計算が、最も計算量を必要とする部分だからです。

計算で得られたクラスタ情報は、NCDawareRankのレベル間類似性行列(M)を構築するのに使われます。

 

これらの計算によって、どのアカウントがどのクラスタに属するかが決定されました。クラスタに属さないものはハブか外れアカウントに分類されます。では、一体なんのためにこのような分類をしたのでしょうか?それは、前々回の記事に出てきたMという行列を作るためです。

 

この画像が、

この行列に変換されました。この中で、1,2,3が同じクラスタ。4,5,6も同じクラスタ。7がはずれアカウントです。でも3の取扱がちょっと難しかったですよね。2つのクラスタに属しつつ、ひとつの外れアカウントとも接続しています。この取り扱いを矛盾なく行えるようにすべてのアカウントをクラスタ、ハブ、外れアカウントに分類するのが、このクラスタリングの役目と考えてください。アウトリンク行列だけでは、7のようなアカウントが計算に入れてもらえず、いつまでもインポータンスが上がらない可能性があるのを、救出するためのもののようです。


コメント:

今回のクラスタリングは、まだまだ発展途上の技術で、NEMが採用した改良版のSCANも、オリジナルと比べて3割から7割くらいの速度向上にとどまるとあります(論文参照)。

現実問題として、ネムログなどの活発なコミュニティーでも、投げネムのほとんどは1000XEMに達しないので、このクラスタリングでは考慮されないと思われます。なんだか、すごくもったいない気がします。今の取引量なら、1000XEM以上のトランザクションという制限を100XEMあるいは10XEMまで下げても、インポータンス計算に支障は出ないと思うので、カタパルト実装の際にはぜひとも引き下げを検討してもらいたいです。そうすれば、せっかくのPoIがPoSの劣化版なんて言われることもなくなるでしょう。

 

今回も読んでくださってありがとうございます。

 

目指せ北海道

 

 

Writer
歯の神経の中にいる「歯髄(しずい)細胞」を再生医療に活用するための研究をしています。再生医療の実用化に足りないものは細胞のトレーサビリティだと気づき、Symbolのブロックチェーン技術を使って、細胞の流通や製造管理のための「ShizuiNet」を開発中。現在、実用化のための大学発ベンチャー起業を準備しています。しずいノード(symbol.shizuilab.com)を運用しており、委任ハーベスト収入は研究開発費として使わせていただきます。下記リンクからノード実績を御覧いただけます。

Comment
Login required to post comment
Loading...
https://symbol-sakura-16.next-web-technology.com:3001,https://symbol.harvest-monitor.com:3001,https://hideyoshi-node.net:3001,https://harvest-01.symbol.farm:3001,https://criptian-xym-node.net:3001,https://35665.xym.stir-hosyu.com:3001,https://yuna.keshet.finance:3001,https://cryptocat-xym-node.com:3001,https://misaki-xym.com:3001,https://ik1-305-12844.vs.sakura.ne.jp:3001,https://17107.xym.stir-hosyu.com:3001,https://23639.xym.stir-hosyu.com:3001,https://sym-main-01.opening-line.jp:3001,https://sym-main-02.opening-line.jp:3001,https://sym-main-03.opening-line.jp:3001,https://sym-main-04.opening-line.jp:3001,https://sym-main-05.opening-line.jp:3001,https://sym-main-06.opening-line.jp:3001,https://sym-main-07.opening-line.jp:3001,https://sym-main-08.opening-line.jp:3001,https://sym-main-09.opening-line.jp:3001,https://sym-main-10.opening-line.jp:3001,https://symbol-node-01.kokichi.tokyo:3001,https://50038.xym.stir-hosyu.com:3001,https://27423.xym.stir-hosyu.com:3001,https://angel.vistiel-arch.jp:3001,https://xym.stakeme.tokyo:3001,https://00-symbol-node.yagiyoshi.com:3001,
6BED913FA20223F8,051FAEC15105C808,73019335A785A3AE,5289A9B0DBB7EB25,6B245EAF1302E444,2C4A4893229DD0A9,63509D495CAD7B80,481D74291A71FD1F,009388A38C91A8B2,4E94920841641B77,027C6AD49DE2C9F9,