モチーフとグラフレットからみるネットワーク構造
ネットワーク構造を理解するための指標には様々なものがあります。ノード次数やページランクといったノードを対象としたミクロ指標から、ネットワークの直径や最大連結成分といったネットワーク全体を対象としたマクロ指標まで、それぞれネットワークを多角的に理解するための助けになります。本記事では、ミクロとマクロの中間にあるメソスケール的なネットワーク構造の理解のため、モチーフとグラフレットの概念と、その活用方法について考察します。
モチーフ
モチーフとは“ネットワーク内にみられる、有意に繰り返し現れるパターン”のことを指します。ネットワークを観察すると小さなパターン（図１）から構成されていることがわかります。この“パターン”は部分グラフと呼ばれます。これら部分グラフのなかで、観察しているネットワークの中に頻繁に出現するものをモチーフと呼びます。これをレゴに例えると、レゴブロックのお城（＝ネットワーク全体）の中でよく使われているレゴの形（＝部分グラフ）をみつけることに相当します。
（以下テクニカルな部分でスキップ可）
図１のような部分グラフがネットワークに出現する頻度を計ることでネットワーク構造の特徴を定量化することを考えます。単純に部分グラフの出現回数を計数するだけでは比較に使えません。そこで、部分グラフiがネットワークにどの程度有意に出現するか、の指標としてSignificance Profile（以下、SPと呼ぶ）と呼ばれる統計量を用います（Milo et. al., 2004）。
まず、以下のZiを計算します。
ここでそれぞれの記号は、
を表し、stdは標準偏差を表します。また、ランダム化されたネットワークには任意のモデルを用いることができ、例えば各ノードの次数を保ったモデルであるコンフィギュレーションモデルが使えます。このZiを以下の式の通り規格化したものがSPです。規格化により、異なるサイズのネットワーク間の比較が可能になります。
総じてSPは、各部分グラフが“ランダム化されたネットワーク内と比べてどれくらい有意にネットワークに出現するか”、の指標といえます。
（テクニカルな部分おわり）
この“部分グラフがどの程度有意にネットワークに出現するか”の指標（SP指標）を用いることで、ネットワークに特徴的なパターンを抽出・比較することができ、ネットワーク構造に関する示唆を得ることができます。例えば図２では、この指標をノード数３の部分グラフについて、いくつかの異なる種類のネットワークにおいて計算しています。まず、ネットワークの種類によって頻出するパターンが大きく異なることがみてとれます。また例えば、インターネットやソーシャルネットワークでは（上から3番目の図）、双方向に全結合になっているパターン13が比較的出現しやすいことがみてとれます。これは“友達の友達は友達”といった現象を捉えています。
グラフレット
モチーフでは、ノード間のつながりのパターンを考えましたが、これにノードの位置も考慮した概念がグラフレットになります。ノード数２〜５までの全グラフレットを網羅したものが図３になります。
グラフレットを利用してネットワークの各ノードの周辺ネットワーク構造を定量化する指標に、グラフレット次数ベクトルがあります。この計算方法を図４で説明します。まずノード数３のグラフレットには３つの異なる位置が存在します（図中1,2,3）。ネットワークにおいてノードAを含むノード数３の部分グラフ（図中カラーで囲っている部分）において、ノードAが各“位置”に相当する回数を計数することでグラフレット次数ベクトル（例では[0,2,1]）を作成できます。例ではノード数３のグラフレットを使用しましたが、ノード数２〜５のものを組み合わせることで表現力を高める（ベクトルの次元を増やす）ことができます。
このベクトルを用いることでノード周辺のローカルなネットワーク構造を表現・比較することができ、例えばネットワーク構造からみたノードのラベルづけに活用できます。
計算量の問題
モチーフを抽出するためには、ネットワークから全ての部分グラフを抽出する、それぞれを分類する、という２ステップが必要になります。これに必要な計算時間は、モチーフのノード数に対して指数関数的に増大していきます。そのため実際は、ノード数が３〜５のサイズのモチーフを用いることが多いです。モチーフ抽出の計算効率化のアルゴリズムは現在もアクティブな研究エリアになっています（Jazayeri and Yang, 2020）。
活用方法
これまで述べた通り、モチーフやグラフレットを活用してネットワークの構造を理解することができます。例えば、SNSなどのコミュニティサービスにおいて以下に挙げるような活用例が考えられます。
- モチーフを用いたつながりの分析
a) ハブユーザーとそれ以外でどのようなコニュニケーションパターンの違いがあるのか、といったサービス全体の構造の把握
b) サービスを継続してくれるユーザーとそうでないユーザーで、サービス内コンテンツ遷移パターンの違いの抽出 → サービス継続に重要なアクティビティパターンに誘導するようなUIの変更を考える - グラフレットを用いた周辺ネットワーク構造の似たユーザーの抽出
既知の不正・規約違反のユーザーのローカルなコミュニケーションパターンからグラフレット次数ベクトルを作成し、これに似た特徴を持つユーザーを抽出する→このユーザーを人力での監視対象に追加する
最後に
弊社では今後, ネットワーク科学、そして社会科学全般を活用した事業活用の取組みを推進していきます。ディスカッションなどはお気軽にDeNA 安達 (ai_social_ds_my@dena.jp) にご連絡ください。
参考文献
- Network Motifs: Simple Building Blocks of Complex Networks. Milo et. al., Science, 2002
- Superfamilies of Evolved and Designed Networks. Milo et. al., Science, 2004
- Biological Network Comparison Using Graphlet Degree Distribution. Pržulj, Bioinformatics, 2007
- Motif discovery algorithms in static and temporal networks: A survey. Jazayeri and Yang, Journal of Complex Networks, 2020
