WEKO3
アイテム
階層的スケールフリーネットワークにおける万能定数時間アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/142302
https://ipsj.ixsq.nii.ac.jp/records/142302fad95096-96b1-493c-836e-67086397fa65
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL15153002.pdf (607.0 kB)
|
Copyright (c) 2015 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2015-06-05 | |||||||
| タイトル | ||||||||
| タイトル | 階層的スケールフリーネットワークにおける万能定数時間アルゴリズム | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 電気通信大学／科学技術振興機構, CREST | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| The University of Electro-Communications (UEC) / CREST, JST | ||||||||
| 著者名 |
伊藤, 大雄
× 伊藤, 大雄
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | ビッグデータへの劣線形時間アルゴリズムによるアプローチが最近有望視されている．代表的なビッグデータであるスケールフリーネットワークには階層的構造があることが指摘されており，我々はそれを利用した自然な多重グラフのクラス HSF (Hierarchical Scale-Free multigraphs) を定義する．そして，このクラスにおいて，超有限性 (hyperfiniteness) が成立することを証明する．この結果から 「本クラスの多重グラフにおいては，すべての性質が定数時間検査可能である」 という驚くべき結論を導くことができる．これは疎でかつ次数上限の無いグラフモデルに対する初めての万能検査アルゴリズムであり，現実の複雑ネットワーク上の超高速アルゴリズムの構築を可能とする基礎理論である． | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2015-AL-153, 号 2, p. 1-4, 発行日 2015-06-05 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 2188-8566 | |||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
