時間変化するネットワークに対するZDDを用いた媒介中心性計算

• Item type: SIG Technical Reports(1)
• 公開日: 2024-08-29
• タイトル: 時間変化するネットワークに対するZDDを用いた媒介中心性計算
• タイトル / 言語: en
• タイトル: Computing Betweenness Centrality in Time-varying Network using Zero-suppressed Binary Decision Diagram
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 奈良先端科学技術大学院大学先端科学技術研究科
• 著者所属: 奈良先端科学技術大学院大学先端科学技術研究科
• 著者所属: 奈良先端科学技術大学院大学先端科学技術研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, Nara Institute of Science and Technology
• 著者名: 安藤, 大輝; 中畑, 裕; 笠原, 正治
• 著者名(英): Daiki, Ando; Yu, Nakahata; Shoji, Kasahara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ネットワークの頂点の重要性を測る尺度に媒介中心性がある．従来，媒介中心性はネットワーク構造が時間変化しない，静的なネットワークを対象としてきた．一方，実世界のネットワークが静的であることは稀であり，時間変化するネットワークの媒介中心性についても研究されている．媒介中心性の計算には全最短パスの数え上げを要する．ネットワークの時間変化を考慮した結果，4 つの最短の定義が生まれるが，それらの最短パスの列挙には #P 困難に分類されるケースが存在する．そこで本研究では，ZDD を用いた最短パス列挙を基に，媒介中心性を効率良く計算する手法を提案する．また，計算機実験により，各最短パスに対する媒介中心性の計算時間および ZDD サイズを比較する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Betweenness Centrality (BC) is a measure of the importance of the vertices in a network. BC has been extensively studied for a variety of static networks whose topologies don’t change over time. However, real-world networks are rarely static, we can consider BC in time-varying networks as well. BC value of a vertex quantifies how many shortest paths go through this vertex. Thus, BC computation is closely related to counting shortest paths. Four different shortest paths can be defined in time-varying networks, while some of four shortest paths can be enumerated in polynomial time, others are computationally hard (#P-hard). We devise a method of BC computation for time-varying networks using Zero-suppressed binary Decision Diagrams (ZDD). In several experiments, we compare the construction time of ZDD and sizes of ZDDs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2024-AL-199, 号 1, p. 1-7, 発行日 2024-08-29
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会