狠狠撸

狠狠撸Share a Scribd company logo

20140925 multilayernetworks

?Download as PPTX, PDF?
?
T
tm1966

Brief explanation of Kivela's "Multilayer Networks". http://arxiv.org/abs/1309.7233

1 of 10
Download to read offline
Multilayer Networks輪読会 4.2.5から4.4まで 村田刚志(东工大)
4.2.5 inter-layer diagnostics ? ここまでは、monoplexネットワークの特徴量をmulti-layerに拡張したもの ばかり – multi-layerならではの新たなものが欲しい ? layer内networkを比較する特徴量 – global overlap[45]: 2つのlayerで共有する辺の数 – global inter-clustering coefficient[259]:layerにまたがるクラスタ係数 – layer間の隣接行列要素の相関[19] – degree of multiplexity[178]:(複数の型の辺をもつ頂点ペア数)/(全ての頂点ペ ア数) – 次数やlocal clustering coefficientの相関[19,104,182,250,259] ? 純粋にmulti-layerに特有の特徴量 – interdependence[234,250]:最短パスの中で、複数のlayer辺が使われる割合 – 全頂点が全layerにあるmultiplex network以外の特徴量 ? 頂点のmultiplexity degree [285]:その頂点が存在するlayerの数 ? [67]:社会ネットでmultiplexity degreeが1のものと2以上のもの(bridge)を比較 – layer毎に別communityと解釈なら、assortativityやmodularityも特徴量[226]
4.3 Models of Multiplex Networks ? 人工multiplex networksを作る単純な方法 – 通常の生成モデル(ER random graph や configuration model)を用いて各層を作り、次に layer間を辺でつなぐ[125,199,231][125,217] – 各層を独立に作ったmultiplex networkから始め て、次に(ノードのラベルを変えるなどして)layer間 の相関を作り出す方法[104] ? Exponential random graph models (ERGMs)は multilevel networksやmultiplex networksを扱 える?(??) = exp ? ? ? ?? ? ? [122,273,274][153] model parameter を表すベクトル network diagnostics 正規化関数（異 種辺の△)のベクトル
microcanonical/canonical network ensembles[256,316] ? microcanonical ensembles – 制約集合を厳密に満たすネットワークの集合 ? canonical network ensembles – Shannon entropy最大化:平均的に制約を満たす – multiplex networkよりも辺の重なりに対して有効 ? (空間に埋め込まれた)spatial networksのモデ ル化に使われる[150]
他の生成モデル ? 優先的選択などの手法をmultiplex networkに拡 張したもの – Criado[95](一部の頂点だけを含んだ)layerを増やすこ とでmultiplex networkの成長をモデル化 – 優先的戦略で辺や頂点を追加するもの[182,214,250] ? layer間の辺が作られる確率は、layer内の次数(からなる関 数)に比例 attachment kernel ? attachment kernelがaffine(平行移動を伴う線形写像) ? 異なるlayerに頂点が異なる回数だけ生成されるのを許すモ デル ? 非線形のattachment kernel
4.4 Models of interconnected networks ? monoplexネットワークの生成モデルを他のmultilayer に一般化 – 動的プロセスの研究にモデルは有効 ? 似通ったネットワークモデルの研究 – interacting network, node color, node type, module – block modelやmixture modelによるモデル化も ? 単純な方法は各layerを作って、異なるlayer間をランダ ムに辺で結ぶ(lattice, ER random graph, configuration network, BA network) – 均一にランダムにする必要はない ? layer間を結之悿胜霊槁预侵行男预嗓浃铯毪窝芯 ? SIRでの伝搬にどう影響するかの研究
configuration modelの拡張 ? 複数の次数分布を多変数で表す ??(?1, … , ??) layer αの頂点がlayer βの頂点kβ個とつながる確率 – [10,200] – Soderberg ?(?1, … , ??) layer独立な多次元分布+ ??? – Newman – Gleeson – [17] node-colored graphのERモデル – [9] node-colored 2部グラフのconfiguration model layerαとβ間 の辺の割合 ??(?) 各layerの次数分布+ mixing matrix layer間の 辺の割合 結合確率行列P ??? (?) layerαの頂点がk個のlayerβ の頂点とつながる確率 ? layer内-layer間の次数相関を取り入れたモデ ル ??? (?, ?′) layerα内で次数kの頂点がk’個のlayerβの頂点とつながる確率 ??? (???, ???, ?′ ??, ?′ ??) layer内次数layer間次数
configuration model ? (2頂点をランダムに選んで辺を追加する) random graphでは次数分布がポアソン分布 ? 任意の次数分布のネットワークを生成する手 法 – 与えられた次数の切り株を用意 – 切り株の間をランダムにつなぐ 頂 点 次 数 a 2 b 2 c 3 d 3 e 4 a b c d e b c d e a a b d c e
Stochastic block model (1) http://tuvalu.santafe.edu/~aaronc/courses/5352/fall2013/ ? 与えられたグラフの背後にある生成モデルの パラメータ – k:グループ数 予め与える – ? :各頂点のグループID パラメータ – M:グループ間の結合確率の行列(k*k) ? モデルからグラフを生成 – 頂点iとjの間の辺をMzizjの確率で生成(ziとzjは頂 点iとjが属するグループのID) ? グラフからモデルを推定
Stochastic block model (2) http://tuvalu.santafe.edu/~aaronc/courses/5352/fall2013/ ? M(stochastic block matrix)と生成されるグラフ – グループ内:ランダムグラフ、グループ間:ランダム 2部グラフ 対角成分0.50 それ以外0.01 →グループ内が密 対角成分0.01 それ以外0.12 →グループ間が密

More Related Content

20140925 multilayernetworks

  • 2. 4.2.5 inter-layer diagnostics ? ここまでは、monoplexネットワークの特徴量をmulti-layerに拡張したもの ばかり – multi-layerならではの新たなものが欲しい ? layer内networkを比較する特徴量 – global overlap[45]: 2つのlayerで共有する辺の数 – global inter-clustering coefficient[259]:layerにまたがるクラスタ係数 – layer間の隣接行列要素の相関[19] – degree of multiplexity[178]:(複数の型の辺をもつ頂点ペア数)/(全ての頂点ペ ア数) – 次数やlocal clustering coefficientの相関[19,104,182,250,259] ? 純粋にmulti-layerに特有の特徴量 – interdependence[234,250]:最短パスの中で、複数のlayer辺が使われる割合 – 全頂点が全layerにあるmultiplex network以外の特徴量 ? 頂点のmultiplexity degree [285]:その頂点が存在するlayerの数 ? [67]:社会ネットでmultiplexity degreeが1のものと2以上のもの(bridge)を比較 – layer毎に別communityと解釈なら、assortativityやmodularityも特徴量[226]
  • 3. 4.3 Models of Multiplex Networks ? 人工multiplex networksを作る単純な方法 – 通常の生成モデル(ER random graph や configuration model)を用いて各層を作り、次に layer間を辺でつなぐ[125,199,231][125,217] – 各層を独立に作ったmultiplex networkから始め て、次に(ノードのラベルを変えるなどして)layer間 の相関を作り出す方法[104] ? Exponential random graph models (ERGMs)は multilevel networksやmultiplex networksを扱 える?(??) = exp ? ? ? ?? ? ? [122,273,274][153] model parameter を表すベクトル network diagnostics 正規化関数（異 種辺の△)のベクトル
  • 4. microcanonical/canonical network ensembles[256,316] ? microcanonical ensembles – 制約集合を厳密に満たすネットワークの集合 ? canonical network ensembles – Shannon entropy最大化:平均的に制約を満たす – multiplex networkよりも辺の重なりに対して有効 ? (空間に埋め込まれた)spatial networksのモデ ル化に使われる[150]
  • 5. 他の生成モデル ? 優先的選択などの手法をmultiplex networkに拡 張したもの – Criado[95](一部の頂点だけを含んだ)layerを増やすこ とでmultiplex networkの成長をモデル化 – 優先的戦略で辺や頂点を追加するもの[182,214,250] ? layer間の辺が作られる確率は、layer内の次数(からなる関 数)に比例 attachment kernel ? attachment kernelがaffine(平行移動を伴う線形写像) ? 異なるlayerに頂点が異なる回数だけ生成されるのを許すモ デル ? 非線形のattachment kernel
  • 6. 4.4 Models of interconnected networks ? monoplexネットワークの生成モデルを他のmultilayer に一般化 – 動的プロセスの研究にモデルは有効 ? 似通ったネットワークモデルの研究 – interacting network, node color, node type, module – block modelやmixture modelによるモデル化も ? 単純な方法は各layerを作って、異なるlayer間をランダ ムに辺で結ぶ(lattice, ER random graph, configuration network, BA network) – 均一にランダムにする必要はない ? layer間を結之悿胜霊槁预侵行男预嗓浃铯毪窝芯 ? SIRでの伝搬にどう影響するかの研究
  • 7. configuration modelの拡張 ? 複数の次数分布を多変数で表す ??(?1, … , ??) layer αの頂点がlayer βの頂点kβ個とつながる確率 – [10,200] – Soderberg ?(?1, … , ??) layer独立な多次元分布+ ??? – Newman – Gleeson – [17] node-colored graphのERモデル – [9] node-colored 2部グラフのconfiguration model layerαとβ間 の辺の割合 ??(?) 各layerの次数分布+ mixing matrix layer間の 辺の割合 結合確率行列P ??? (?) layerαの頂点がk個のlayerβ の頂点とつながる確率 ? layer内-layer間の次数相関を取り入れたモデ ル ??? (?, ?′) layerα内で次数kの頂点がk’個のlayerβの頂点とつながる確率 ??? (???, ???, ?′ ??, ?′ ??) layer内次数layer間次数
  • 8. configuration model ? (2頂点をランダムに選んで辺を追加する) random graphでは次数分布がポアソン分布 ? 任意の次数分布のネットワークを生成する手 法 – 与えられた次数の切り株を用意 – 切り株の間をランダムにつなぐ 頂 点 次 数 a 2 b 2 c 3 d 3 e 4 a b c d e b c d e a a b d c e
  • 9. Stochastic block model (1) http://tuvalu.santafe.edu/~aaronc/courses/5352/fall2013/ ? 与えられたグラフの背後にある生成モデルの パラメータ – k:グループ数 予め与える – ? :各頂点のグループID パラメータ – M:グループ間の結合確率の行列(k*k) ? モデルからグラフを生成 – 頂点iとjの間の辺をMzizjの確率で生成(ziとzjは頂 点iとjが属するグループのID) ? グラフからモデルを推定
  • 10. Stochastic block model (2) http://tuvalu.santafe.edu/~aaronc/courses/5352/fall2013/ ? M(stochastic block matrix)と生成されるグラフ – グループ内:ランダムグラフ、グループ間:ランダム 2部グラフ 対角成分0.50 それ以外0.01 →グループ内が密 対角成分0.01 それ以外0.12 →グループ間が密