ネットワーク構造の Assortativity とは何か

研究所の輪読会で以下の論文を読んでいて、ネットワークにおける Assortativity という語句が出てきた。意味を知らなかったのでまとめる。

Qingyun Wu, Zhige Li, Huazheng Wang, Wei Chen, and Hongning Wang. 2019. Factorization Bandits for Online Influence Maximization. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD ’19). Association for Computing Machinery, New York, NY, USA, 636–646.

Assortativity とは

ネットワークにおける Assortativity とは「あるノードからの、何らかの観点で類似している別のノードへの接続性」である。Wolfram は「同類選択性係数」と訳していた。これをモデルに追加すると、現実のネットワークに振る舞いを近づけることができる。類似性を決める指標は色々あるが、ノードの次数（ノードに接続されたエッジの数）に関連したものが用いられることが多い。

次数が近いノード間の相関は、ソーシャルネットワークのような混合パターンに見られることが多い。この傾向が Assortative mixing や Assortativity と呼ばれている。一方で、高次のノードが低次のノードに接続する傾向がある場合は、Disassortative mixing や Disassortativity と呼ばれる。

Assortativity を測る指標

Assortativity は、しばしば2つのノード間の相関として測られる。

つまり、同じくらいの数のエッジを持つノード同士が接続されており、相関が強いネットワークは Assortativity がある。

「あるノードからの、何らかの観点で類似している別のノードへの接続性」を言い換えて、「あるノードから別のノードへの接続がある場合の、2つのノード間の類似性」として測っていると理解した。

Assortativity coefficient

Assortativity coefficient は、2つのノード間の次数のピアソンの積率相関係数である。相関係数なので-1から1の範囲を取り、1ならばネットワークは完全に assortative、0ならば non-assortative、-1ならば disassortative と見なせる。

N 個のノードと M 個のエッジを持つ無向ネットワーク X について、c を正規化係数、A を X の隣接行列、k_i をノード i の次数、x_i をノード i の特性の値（連続変数）とおくと、Assortativity coefficient r は次の式で表される。

$$r=c\sum_i\sum_j(A_{ij}-\frac{k_ik_j}{2M})x_ix_j$$ Assortativity coefficient の異なる3つのネットワークを可視化すると、値が高いほどクラスタのようなものが見えることがわかる。

Neighbor connectivity

Neighbor connectivity は、次数 k のノードの近傍のノードの次数の平均により相関を測る。

次数 k のノードのエッジが次数 k’ のノードと接続される条件付き確率 P(k’|k) を用いて、

$$\langle k_{nn}\rangle=\sum_{k’}k’P(k’|k)$$

が増加すればネットワークは Assortativity を持ち、減少すれば Disassortativity を持つ。

参考

ネットワーク構造の Assortativity とは何か

Assortativity とは

Assortativity を測る指標

Assortativity coefficient

Neighbor connectivity

HIROKA Zaitsu