狠狠撸

狠狠撸Share a Scribd company logo

Multiplex_Network_usui

?
?
Shohei Usui
Shohei Usui

7/12轮読会

1 of 22
Download to read offline
輪読会 ? 第一回multilayer networks輪読会 ? Mason A. Porter氏のサーベイ論文の輪読 ?http://arxiv.org/abs/1309.7233 ? 一人10分を目安にしてください(発表10分，質疑5分 程度) ? スライドシェアーして，メールしてください！ 1
輪読会 ? Multilayer networkに関する基礎知識の獲得 ? 第二回以降で読む文献を探す 2 ぜひ，第二回以降もご参加ください！！
1.Introduction, 2. Multilayer Networks 東京大学大学院工学系研究科 システム創成学専攻大橋?鳥海研 D1 臼井翔平 3 Multilayer Network
研究の発展 ? Move beyond simple graphs ?investigate more realistic frameworks ? e.g. ?Edges can be directed ?Edges have di?erent strengths ?Edges are active only at certain times ?Edges exist only between nodes that belong to di?erent sets ?“networks of networks” ? See Sction 2.4 4
categorize edges ? 一種類の関係のみのネットワークで社会システムを 表すことは現実を過度に単純化 ? 複数種類の関係を用いたmultiple social network の研究が重要 ? J. Scott. Social Network Analysis. SAGE Publications, 2012. ? S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994. 5
Multilayer network ? F. Roethlisberger and W. Dickson. Management and the worker. Cambridge University Press, 1939. ? ホーソンの実験 ? relations between 14 individuals via 6 di?erent types of social interactions 6
様々なmultilayer network ? “multiplex networks” ? M. Gluckman. The judicial process among the Barotse of Northern Rhodesia. Manchester University Press, 1955. ? L. M. Verbrugge. Multiplexity in adult friendships. Social Forces, 57(4):1286–1309, 1979. ? “multirelational networks” ? S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994. ? “multi-stranded” relationships ? J. C. Mitchell, editor. Social Networks in Urban Situations: Analyses of Personal Relationships in Central African Towns. Manchester University Press, 1969. 7
様々なmultilayer network ? “multilevel networks” ?several types of nodes or hierarchical structures ?See Section 2.8 ? exponential random graph models (ERGMs) ? D. Lusher, J. Koskinen, and G. Robins. Exponential Random Graph Models for Social Networks. Cambridge University Press, 2013. ? meta-networks and meta-matrices ? K. M. Carley and V. Hill. Structural change and learning within organizations, 2001. ? methods for identifying social roles using blockmodeling and relational algebras 8
In the computer-science and computational linear-algebra communities ? studied various types of multilayer networks ?tensor-decomposition methods ? D. M. Dunlavy, T. G. Kolda, and W. P. Kegelmeyer. Multilinear algebra for analyzing data with multiple linkages. In J. Kepner and J. Gilbert, editors, Graph Algorithms in the Language of Linear Algebra, Fundamentals of Algorithms, pages 85–114. SIAM, Philadelphia, 2011. ? T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Rev., 51(3):455–500, 2009. ?multiway data analysis ? E. Acar and B. Yener. Unsupervised multiway data analysis: A literature survey. IEEE Trans. Knowl. Data Eng., 21(1):6–20, 2009. ? See Section 4.2.4, 4.5.2 9
the singular value decomposition (SVD) ? most widespread methods ? C. D. Martin and M. A. Porter. The extraordinary SVD. Am. Math. Monthly, 119:838–851, 2012. ? extremely successful in many applications ? used to extract communities or to rank nodes ? D. M. Dunlavy, T. G. Kolda, and W. P. Kegelmeyer. Multilinear algebra for analyzing data with multiple linkages. In J. Kepner and J. Gilbert, editors, Graph Algorithms in the Language of Linear Algebra, Fundamentals of Algorithms, pages 85–114. SIAM, Philadelphia, 2011. ? T. Kolda and B. W. Bader. The TOPHITS model for higher-order web link analysis. In Proceedings of the SIAM Data Mining Conference Workshop on Link Analysis, Counterterrorism and Security, 2006. ? T. G. Kolda, B. W. Bader, and J. P. Kenny. Higher-order web link analysis using multilinear algebra. In Proceedings of the 5th IEEE International Conference on Data Mining (ICDM 2005), pages 242–249, 2005 10
データマイニングでの利用 ? 伝統的な方法で表現できないNetworked systems はデータマイニングの視点からも研究されている ? E.g. ?情報ネットワークはmultiple networkを考慮する一般的な フレームワーク ?ネットワークダイナミクス ?“organizational theory” ? organizations, people, resources, and other types of entities 11
multiple networksの流行 ? ここ2年で突然multiple networksが流行 ? Multilayer networksの論文の流行は，用語の爆発 を生んだ ?コンセンサスの欠落は問題 ? Multiplex networkにおける多くの概念を定める事も 重要 ?Degree, transitivity, centrality, diffusion 12
本論文 ? Multilayer networkを定義 ?ほとんどのmulti networksから成るcomplex systemを表 現可能 ? 既存の研究からmultilayer networkを表すのに自然 なマッピングを発見 ? 既存の概念を制約に従って分類(table 1) 13
Table 1 14
ネットワークの一面性 ? 2面性(Multiplexity)を持つネットワーク ?E.g. multiplex and temporal ?より多くの面をはっきりと列挙することで現実を再現 ? ネットワークの一面にのみ関心を持った点には注意 をするべき ?一つの面による多層ネットワークはマルチプレックス性の 固有の「新しい物理学」をすでに与えます 15
本論文の着眼 ? 主に着目 ?edge-colored multigraph ?ネットワークのシーケンス ? Some attention ?interdependent networks ?networks of networks. 16
本論文の構成 ? Section 2 ?a general formulation for multilayer networks ? Section 3 ?既存のデータセットの紹介 ?研究に有用な他のタイプのデータを検討 ? Section 4 ?Multilayer networkの性質やダイナミクスを分析するため のmodel, methods, diagnosticsの紹介 17
2 Multilayer Networks ? the most general notion of a multilayer network structure ?by defining various constraints for that structure ? reduce the rank of a tensor ?By constraining the space ?“flattening” the tensor. ? 計算するために，matricesよりtensorsの方が便利 18
Section 2の構成 ? 多数のmultilayer-networkの構造を検討 ?Multiplex networks ?Networks of networks ?etc… ? 最後に以下のネットワークの関係性を述べる ?multilayer networks ?Hypergraphs ?temporal networks ?certain other types of networks. 19
Interconnected systems ? cascading failuersで研究が進んでいる ?increasing connectivity has the potential to increase large-scale events. ?monoplex networkとは異なる方法でrandom failuerを減 らす 20
図1 ? 実線：全単射，点線：単射 ? それぞれのサブグラフは制約(Table1)によって特徴 付られる 21
22

More Related Content

Multiplex_Network_usui

  • 1. 輪読会 ? 第一回multilayer networks輪読会 ? Mason A. Porter氏のサーベイ論文の輪読 ?http://arxiv.org/abs/1309.7233 ? 一人10分を目安にしてください(発表10分，質疑5分 程度) ? スライドシェアーして，メールしてください！ 1
  • 2. 輪読会 ? Multilayer networkに関する基礎知識の獲得 ? 第二回以降で読む文献を探す 2 ぜひ，第二回以降もご参加ください！！
  • 4. 研究の発展 ? Move beyond simple graphs ?investigate more realistic frameworks ? e.g. ?Edges can be directed ?Edges have di?erent strengths ?Edges are active only at certain times ?Edges exist only between nodes that belong to di?erent sets ?“networks of networks” ? See Sction 2.4 4
  • 5. categorize edges ? 一種類の関係のみのネットワークで社会システムを 表すことは現実を過度に単純化 ? 複数種類の関係を用いたmultiple social network の研究が重要 ? J. Scott. Social Network Analysis. SAGE Publications, 2012. ? S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994. 5
  • 6. Multilayer network ? F. Roethlisberger and W. Dickson. Management and the worker. Cambridge University Press, 1939. ? ホーソンの実験 ? relations between 14 individuals via 6 di?erent types of social interactions 6
  • 7. 様々なmultilayer network ? “multiplex networks” ? M. Gluckman. The judicial process among the Barotse of Northern Rhodesia. Manchester University Press, 1955. ? L. M. Verbrugge. Multiplexity in adult friendships. Social Forces, 57(4):1286–1309, 1979. ? “multirelational networks” ? S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994. ? “multi-stranded” relationships ? J. C. Mitchell, editor. Social Networks in Urban Situations: Analyses of Personal Relationships in Central African Towns. Manchester University Press, 1969. 7
  • 8. 様々なmultilayer network ? “multilevel networks” ?several types of nodes or hierarchical structures ?See Section 2.8 ? exponential random graph models (ERGMs) ? D. Lusher, J. Koskinen, and G. Robins. Exponential Random Graph Models for Social Networks. Cambridge University Press, 2013. ? meta-networks and meta-matrices ? K. M. Carley and V. Hill. Structural change and learning within organizations, 2001. ? methods for identifying social roles using blockmodeling and relational algebras 8
  • 9. In the computer-science and computational linear-algebra communities ? studied various types of multilayer networks ?tensor-decomposition methods ? D. M. Dunlavy, T. G. Kolda, and W. P. Kegelmeyer. Multilinear algebra for analyzing data with multiple linkages. In J. Kepner and J. Gilbert, editors, Graph Algorithms in the Language of Linear Algebra, Fundamentals of Algorithms, pages 85–114. SIAM, Philadelphia, 2011. ? T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Rev., 51(3):455–500, 2009. ?multiway data analysis ? E. Acar and B. Yener. Unsupervised multiway data analysis: A literature survey. IEEE Trans. Knowl. Data Eng., 21(1):6–20, 2009. ? See Section 4.2.4, 4.5.2 9
  • 10. the singular value decomposition (SVD) ? most widespread methods ? C. D. Martin and M. A. Porter. The extraordinary SVD. Am. Math. Monthly, 119:838–851, 2012. ? extremely successful in many applications ? used to extract communities or to rank nodes ? D. M. Dunlavy, T. G. Kolda, and W. P. Kegelmeyer. Multilinear algebra for analyzing data with multiple linkages. In J. Kepner and J. Gilbert, editors, Graph Algorithms in the Language of Linear Algebra, Fundamentals of Algorithms, pages 85–114. SIAM, Philadelphia, 2011. ? T. Kolda and B. W. Bader. The TOPHITS model for higher-order web link analysis. In Proceedings of the SIAM Data Mining Conference Workshop on Link Analysis, Counterterrorism and Security, 2006. ? T. G. Kolda, B. W. Bader, and J. P. Kenny. Higher-order web link analysis using multilinear algebra. In Proceedings of the 5th IEEE International Conference on Data Mining (ICDM 2005), pages 242–249, 2005 10
  • 11. データマイニングでの利用 ? 伝統的な方法で表現できないNetworked systems はデータマイニングの視点からも研究されている ? E.g. ?情報ネットワークはmultiple networkを考慮する一般的な フレームワーク ?ネットワークダイナミクス ?“organizational theory” ? organizations, people, resources, and other types of entities 11
  • 12. multiple networksの流行 ? ここ2年で突然multiple networksが流行 ? Multilayer networksの論文の流行は，用語の爆発 を生んだ ?コンセンサスの欠落は問題 ? Multiplex networkにおける多くの概念を定める事も 重要 ?Degree, transitivity, centrality, diffusion 12
  • 13. 本論文 ? Multilayer networkを定義 ?ほとんどのmulti networksから成るcomplex systemを表 現可能 ? 既存の研究からmultilayer networkを表すのに自然 なマッピングを発見 ? 既存の概念を制約に従って分類(table 1) 13
  • 15. ネットワークの一面性 ? 2面性(Multiplexity)を持つネットワーク ?E.g. multiplex and temporal ?より多くの面をはっきりと列挙することで現実を再現 ? ネットワークの一面にのみ関心を持った点には注意 をするべき ?一つの面による多層ネットワークはマルチプレックス性の 固有の「新しい物理学」をすでに与えます 15
  • 16. 本論文の着眼 ? 主に着目 ?edge-colored multigraph ?ネットワークのシーケンス ? Some attention ?interdependent networks ?networks of networks. 16
  • 17. 本論文の構成 ? Section 2 ?a general formulation for multilayer networks ? Section 3 ?既存のデータセットの紹介 ?研究に有用な他のタイプのデータを検討 ? Section 4 ?Multilayer networkの性質やダイナミクスを分析するため のmodel, methods, diagnosticsの紹介 17
  • 18. 2 Multilayer Networks ? the most general notion of a multilayer network structure ?by defining various constraints for that structure ? reduce the rank of a tensor ?By constraining the space ?“flattening” the tensor. ? 計算するために，matricesよりtensorsの方が便利 18
  • 19. Section 2の構成 ? 多数のmultilayer-networkの構造を検討 ?Multiplex networks ?Networks of networks ?etc… ? 最後に以下のネットワークの関係性を述べる ?multilayer networks ?Hypergraphs ?temporal networks ?certain other types of networks. 19
  • 20. Interconnected systems ? cascading failuersで研究が進んでいる ?increasing connectivity has the potential to increase large-scale events. ?monoplex networkとは異なる方法でrandom failuerを減 らす 20
  • 22. 22