著者

秋葉 拓哉 林 孝紀 則 のぞみ 岩田 陽一

出版者

一般社団法人 人工知能学会

雑誌

人工知能学会論文誌 (ISSN:13460714)

巻号頁・発行日

vol.31, no.2, pp.B-F71_1-12, 2016-03-01 (Released:2016-02-18)

参考文献数

39

---

Estimating the relevance or proximity between vertices in a network is a fundamental building block of network analysis and is useful in a wide range of important applications such as network-aware searches and network structure prediction. In this paper, we (1) propose to use top-k shortest-path distance as a relevance measure, and (2) design an efficient indexing scheme for answering top-k distance queries. Although many indexing methods have been developed for standard (top-1) distance queries, no methods can be directly applied to top-k distance. Therefore, we develop a new framework for top-k distance queries based on 2-hop cover and then present an efficient indexing algorithm based on the recently proposed pruned landmark labeling scheme. The scalability, efficiency and robustness of our method are demonstrated in extensive experimental results. It can construct indices from large graphs comprising millions of vertices and tens of millions of edges within a reasonable running time. Having obtained the indices, we can compute the top-k distances within a few microseconds, six orders of magnitude faster than existing methods, which require a few seconds to compute these distances. Moreover, we demonstrate the usefulness of top-k distance as a relevance measure by applying them to link prediction, the most fundamental problem in graph data mining. We emphasize that the proposed indexing method enables the first use of top-k distance for such tasks.

著者

秋葉 拓哉

雑誌

情報処理

巻号頁・発行日

vol.53, no.12, pp.1298-1304, 2012-11-15

---

ここ数年で,プログラミングコンテストにおける日本の実力は大きく向上し,今では世界的な強豪国の1つとなった.本稿では,まず,ACM-ICPC を始めとするプログラミングコンテストの紹介を改めて行い,プログラミングコンテストの面白さや意義,批判などについて議論すると共に,世界トップレベルの選手がどうやって育つのか,日本はなぜ強豪国となったか,などについて解説する.

著者

秋葉 拓哉 稲葉 一浩

雑誌

情報処理

巻号頁・発行日

vol.56, no.12, pp.1198-1201, 2015-11-15

---

20年の歴史を持ち「なんでもあり」で有名な ICFPプログラミングコンテストにて,今年,日本チームが優勝と準優勝を達成しました.ICFPプログラミングコンテストの魅力や各チームの戦術を紹介します.

著者

秋葉 拓哉 中村 謙弘 高口 太朗

出版者

人工知能学会

雑誌

人工知能学会全国大会論文集 (ISSN:13479881)

巻号頁・発行日

vol.30, 2016

著者

秋葉 拓哉 林 孝紀 則 のぞみ 岩田 陽一

出版者

一般社団法人 人工知能学会

雑誌

人工知能学会論文誌 (ISSN:13460714)

巻号頁・発行日

pp.B-F71, (Released:2015-10-27)

参考文献数

39

---

Estimating the relevance or proximity between vertices in a network is a fundamental building block of network analysis and is useful in a wide range of important applications such as network-aware searches and network structure prediction. In this paper, we (1) propose to use top-k shortest-path distance as a relevance measure, and (2) design an efficient indexing scheme for answering top-k distance queries. Although many indexing methods have been developed for standard (top-1) distance queries, no methods can be directly applied to top-k distance. Therefore, we develop a new framework for top-k distance queries based on 2-hop cover and then present an efficient indexing algorithm based on the recently proposed pruned landmark labeling scheme. The scalability, efficiency and robustness of our method are demonstrated in extensive experimental results. It can construct indices from large graphs comprising millions of vertices and tens of millions of edges within a reasonable running time. Having obtained the indices, we can compute the top-k distances within a few microseconds, six orders of magnitude faster than existing methods, which require a few seconds to compute these distances. Moreover, we demonstrate the usefulness of top-k distance as a relevance measure by applying them to link prediction, the most fundamental problem in graph data mining. We emphasize that the proposed indexing method enables the first use of top-k distance for such tasks.

著者

秋葉 拓哉

出版者

情報処理学会 ; 1960-

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.53, no.12, pp.1298-1304, 2012-11-15

---

ここ数年で,プログラミングコンテストにおける日本の実力は大きく向上し,今では世界的な強豪国の1つとなった.本稿では,まず,ACM-ICPC を始めとするプログラミングコンテストの紹介を改めて行い,プログラミングコンテストの面白さや意義,批判などについて議論すると共に,世界トップレベルの選手がどうやって育つのか,日本はなぜ強豪国となったか,などについて解説する.

著者

秋葉 拓哉 稲葉 一浩

出版者

情報処理学会 ; 1960-

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.56, no.12, pp.1198-1201, 2015-11-15

---

20年の歴史を持ち「なんでもあり」で有名な ICFPプログラミングコンテストにて,今年,日本チームが優勝と準優勝を達成しました.ICFPプログラミングコンテストの魅力や各チームの戦術を紹介します.

著者

秋葉 拓哉

雑誌

研究報告自然言語処理(NL) (ISSN:21888779)

巻号頁・発行日

vol.2015-NL-222, no.8, pp.1-1, 2015-07-08

---

物事の関係が現れるほぼあらゆる場面で,データはグラフとして表現され処理される.特に近年では,インターネット及びワールド・ワイド・ウェブの普及に伴い,ソーシャルネットワークやウェブグラフを始めとする非常に大規模なグラフデータが偏在している.そのため,大規模グラフデータから有用な情報を効率的に引き出すことは現代社会の様々な場面において重要な役割を担っている.本講演では,基本的なネットワーク解析の手法,小規模グラフデータで用いられてきた古典的なアルゴリズム,大規模なグラフの処理に向けた課題とそれに立ち向かう現代の研究などについて扱う.

著者

秋葉 拓哉

雑誌

情報処理

巻号頁・発行日

vol.57, no.11, pp.1128-1136, 2016-10-15

---

本稿は,プログラミング経験のない読者を対象とし,コンピュータやプログラミングを一切用いずにコンピュータの背後にある数学やアルゴリズムについて説明する.具体的には,カードとコインを用いた並び替えゲームによりソートアルゴリズムを,迷路により右手法と幅優先探索を,そして石取りゲームにより2進法を説明する.

著者

大坂 直人 秋葉 拓哉 吉田 悠一 河原林 健一

出版者

人工知能学会

雑誌

人工知能学会全国大会論文集 (ISSN:13479881)

巻号頁・発行日

vol.29, 2015

---

バイラルマーケティングは,高影響力の少人数に商品の試供品を与え,消費者間の口コミ効果を通した販売促進を行う.ソーシャルネットワークからそのような頂点集合を選ぶ問題は影響最大化と呼ばれ,効率的手法が研究されてきたが,多くは静的であり,巨大かつ動的な現実のグラフの実時間処理は計算時間的に困難である.本研究は頂点・辺の追加・削除を即座に反映し,影響力推定・影響最大化クエリを高速に処理する索引を提案する.