MF Researcher Database

Researchers Database

Advance

Yasuhito Asano

    Department of Information Networking for Innovation and Design　Professor
    Course of　Information Networking for Innovation and Design　Professor
    Information Networking for Innovation and Design collaboration Hub for University and Business　Researcher
Last Updated :2024/04/23

Researcher Information

J-Global ID

Research Areas

  • Informatics / Web and service informatics

Published Papers

Books etc

  • ネットワーク・大衆・マーケット –現代社会の複雑な連結性についての推論–
    浅野 孝夫; 浅野 泰仁 (Joint translation)共立出版 2013/06
  • アルゴリズムデザイン
    浅野 孝夫; 浅野 泰仁; 平田 富夫; 小野 孝男 (Joint translation)共立出版 2008/07
  • 組合せ最適化
    浅野孝夫; 平田 富夫; 小野 孝男; 浅野 泰仁 (Joint translation)シュプリンガー・フェアラーク東京 2005/11

MISC

  • Yasuhito Asano; Zhenjiang Hu; Yasunori Ishihara; Hiroyuki Kato; Makoto Onizuka; Masatoshi Yoshikawa  IEEE International Conference on Big Data and Smart Computing, BigComp 2019, Kyoto, Japan, February 27 - March 2, 2019  1  -4  2019  [Refereed]
  • Automatic Generation of Plot for Education by Teacher–Student Dialogue Style
    Hironori Ito; Yasuhito Asano; Masatoshi Yoshikawa  International Conference on Education and Multimedia Technology (ICEMT 2017)  2017/07  [Refereed]
  • 中村 雄太; 浅野 泰仁; 吉川 正俊  情報処理学会関西支部支部大会講演論文集  8p  2017
  • 戴 憶菱; 浅野 泰仁; 吉川 正俊  情報処理学会関西支部支部大会講演論文集  3p  2017
  • Xinpeng Zhang; Yasuhito Asano; Masatoshi Yoshikawa  2017 IEEE 33RD INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE 2017)  43  -44  2017  [Refereed]
  • Kazuki Takise; Yasuhito Asano; Masatoshi Yoshikawa  24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2016)  72:1-72:4  2016/10  [Refereed]
  • Yiling Dai; Yasuhito Asano; Masatoshi Yoshikawa  Proceedings of the 9th International Conference on Educational Data Mining (EDM2016), Tiffany Barnes, Min Chi and Mingyu Feng (eds.)  pp. 347-350  -352  2016/07  [Refereed]
  • 初期レビューを用いた長期間評価推定
    吉川 正俊; 川本淳平; 俵本 一輝; 浅野泰仁  第7回データ工学と情報マネジメントに関するフォーラム(DEIM 2015)  2015/03
  • クラシック音楽の理解支援を目指して: 箇所表現を利用した内容記述間対応付け
    栗林拓; 浅野泰仁; 吉川 正俊  情報処理学会第77回全国大会, 4S-04  2015/03
  • Improving Document Similarity Computation by Model Performance Prediction
    Jiyi Li; Toshiyuki Shimizu; Yasuhito Asano; Masatoshi Yoshikawa  第7回データ工学と情報マネジメントに関するフォーラム (DEIM 2015)  2015/03
  • 北林 宏樹; 大西 恒彰; 張 信鵬; 浅野 泰仁; 吉川 正俊  電子情報通信学会技術研究報告 = IEICE technical report : 信学技報  114-  (173)  25  -30  2014/08
  • 北林宏樹; 大西恒彰; 張信鵬; 浅野泰仁; 吉川正俊  研究報告データベースシステム（DBS）  2014-  (5)  1  -6  2014/07
  • 北林宏樹; 大西恒彰; 張信鵬; 浅野泰仁; 吉川正俊  研究報告情報基礎とアクセス技術（IFAT）  2014-  (5)  1  -6  2014/07
  • User Intention in Image Retrieval and Small-Granularity Query Topic Intention Detection
    Jiyi Li; Qiang Ma; Yasuhito Asano; Masatoshi Yoshikawa  第5回データ工学と情報マネジメントに関するフォーラム(DEIM 2013)  2013/03
  • グラフマイニングによるソーシャルグラフの成長分析
    山段 裕貴; 浅野 泰仁; 吉川 正俊  第5回データ工学と情報マネジメントに関するフォーラム(DEIM 2013)  2013/03
  • Wikipediaのリンク構造を利用した関係性ラベルの抽出手法
    瀬戸口 司; 浅野 泰仁; 吉川 正俊  第5回データ工学と情報マネジメントに関するフォーラム(DEIM 2013)  2013/03
  • クラシック音楽の内容記述に特化した検索手法
    栗林 拓; 浅野 泰仁; 吉川 正俊  第5回データ工学と情報マネジメントに関するフォーラム(DEIM 2013)  2013/03
  • マイクロブログにおけるユーザの繋がりを利用した意見収集
    河村 崇博; 浅野 泰仁; 吉川 正俊  第5回データ工学と情報マネジメントに関するフォーラム(DEIM 2013)  2013/03
  • 情報ネットワークにおける関係の抽出のための減衰流の計算の高速化
    野島 裕輔; 浅野 泰仁; 吉川 正俊  第4回データ工学と情報マネジメントに関するフォーラム (DEIM2012)  2012/03
  • エンティティ間の類似関係取得のためのWikipedia 事象モデル構築手法に関する考察
    内藤 稔; 浅野 泰仁; 吉川 正俊  第4回データ工学と情報マネジメントに関するフォーラム (DEIM2012)  2012/03
  • 投稿日時とユーザの広がりに基づくツイート分類手法
    伊藤 勇也; 浅野 泰仁; 吉川 正俊  第3回データ工学と情報マネジメントに関するフォーラム(DEIM 2011)  2011/03
  • 島田 裕司; 浅野 泰仁; 吉川 正俊  研究報告データベースシステム（DBS）  2010-  (34)  1  -8  2010/11
  • 押野 泰平; 浅野 泰仁; 吉川 正俊  研究報告データベースシステム（DBS）  2010-  (27)  1  -8  2010/11
  • 感情解析のための分布モデルと相互強化型解析手法
    俵本 一輝; 川本 淳平; 浅野 泰仁; 吉川 正俊  第2回データ工学と情報マネジメントに関するフォーラム(DEIM 2010)  2010
  • Morihiro Kyohei; Zhang Xinpeng; Asano Yasuhito; Yoshikawa Masatoshi  情報科学技術フォーラム講演論文集  8-  (2)  149  -150  2009/08
  • 張 信鵬; 浅野 泰仁; 吉川 正俊  論文集  23-  1  -4  2009
  • 時系列データを用いたWebグラフマイニング
    押野 泰平; 浅野 泰仁; 吉川 正俊  第1回データ工学と情報マネジメントに関するフォーラム(DEIM 2009)  2009
  • Wikipediaを用いた事象の日付情報の推定
    島田 裕司; 浅野 泰仁; 吉川 正俊  第1回データ工学と情報マネジメントに関するフォーラム(DEIM 2009)  2009
  • Yasuhito Asano; Yu Tezuka; Takao Nishizeki  IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS  E91D-  (2)  200  -208  2008/02
  • ASANO Yasuhito; MIZUKI Takaaki; NISHIZEKI Takao  IPSJ SIG Notes  2004-  (101)  9  -16  2004/10
  • ASANO Yasuhito; YOSHIDA Yusuke; NISHIZEKI Takao; TOYODA Masashi; KITSUREGAWA Masaru  IPSJ SIG Notes  2004-  (52)  51  -58  2004/05

Research Grants & Projects

  • 日本学術振興会：科学研究費助成事業
    Date (from‐to) : 2023/04 -2026/03 
    Author : 舩山 朋子; 本間 信生; 浅野 泰仁; 内田 恭敬; 大久保 英一
  • 日本学術振興会：科学研究費助成事業
    Date (from‐to) : 2022/04 -2025/03 
    Author : 浅野 泰仁; 小倉 淳
  • 日本学術振興会：科学研究費助成事業
    Date (from‐to) : 2020/04 -2023/03 
    Author : 内田 恭敬; 本間 信生; 大久保 英一; 舩山 朋子; 堀 和芳; 浅野 泰仁
     
    足裏からの生体情報を得るために設置するセンサ位置の最適化を目的として、タブレットにリアルタイムで歩行時の圧力分布を表示できるインソールセンサを用いて測定を行った。当初からの予定とは異なり、メーカーの都合でセンサからの生データおよび画像データが得られないこととなったため、保存された画像の画面の動画を利用して圧力分布の分析を行った。インソールセンサからの信号は左右のそれぞれの足のつま先、かかと、内足および外足の合計8点である。微小な血流の変化測定ができるかは生データが得られていないため現状では確認できなかった。運動制限の有無や場所の違いについて作業療法士による分析を、タブレット画面を録画して検討した。制限の有無については、センサ数によらず比較的容易に判別できることがわかった。また、制限部位に関しては測定条件を十分検討したデータでないため若干偏りがあるが、判定者に依存することわかった。しかし、つま先や内足周辺のデータを得ることで精度良く分類することができることが初期的な機械学習により明らかとなった。これにより長時間測定時に膨大となるデータに対処するために必要なセンサ数を減らすための方針を見出すことができた。体調不良に関するアンケート調査を行った結果との相関も検討し、データマイニングに活用できるアンケート項目の改善点や、機械学習による分類の基礎も検討した。 改良したセンサアレイシステムを用いて透析患者の透析前後での体調変化として歩行バランスの分析を行い、歩行速度とセンサを左右の足で踏む数の差を特徴量として用いた機械学習により被験者の状態が3通り程度に分類することができ、下肢の血流や病気の症状との関連が指摘できる基礎的なデータを得た。 足裏調音に関してはノイズに影響されない方法の検討が重要であることからピエゾセンサの配置の検討が重要であることも分かった。
  • 日本学術振興会：科学研究費助成事業
    Date (from‐to) : 2018/04 -2023/03 
    Author : 浅野 泰仁
     
    前年度に引き続き，協調型輸送・協調型交通のモデル構築およびその実装，そして性能検証実験を行った． 協調型輸送については，これまで，中継(荷物を中継しながら複数の輸送者が運ぶこと)オンデマンド市街地配送モデルについて，新しい効率化手法を構築してきたが，今年度はさらに市街地をモデル化した道路ネットワークデータを用いて，市街地規模で想定される配送スケジュールに実用可能な速度が出るかどうかの性能検証実験を行った．また,市街地配送にも応用可能なネットワークアルゴリズムの実験検証を他種データ(遺伝子ネットワークデータ)に対して行い，予備的な成果を査読付き国際会議BIBM 2021に投稿し採録された.これらの結果をまとめた論文を現在執筆中であり，令和4年度に査読付き論文誌に投稿予定である． 協調型交通については，これまで複数のプロバイダがアライアンスを構築してデータ統合を行うモデル(調停者モデル・プロバイダモデル・ユーザモデルの3種類)を北京大学の胡教授，大阪大学の鬼塚教授，京都大学の吉川教授らとともに構築してきたが，今年度は，分散データ統合およびトランザクションの機能を実装したDejimaアーキテクチャを用いてデモシステムを実装した．このデモシステムを用いて，協調型交通に欠かせない，車両の予約・送迎・賃走等のサービスに相当するデータ更新トランザクションが，複数のプロバイダのデータに対して想定通りに稼働することを確かめた．さらに，上記の共同研究者らとこのモデルに基づく大規模なトランザクション実験による性能検証を含む成果を論文にまとめ，国際会議SIGMOD 2022に投稿した． また，前述のアライアンスデータ統合モデルをさらに発展させ，階層型アライアンスモデルを提案し，既存アーキテクチャによる実現性および問題点を議論した．この成果は国際ワークショップSFDI 2021の招待論文として採録された．
  • 日本学術振興会：科学研究費助成事業
    Date (from‐to) : 2020/04 -2022/03 
    Author : 浅野 泰仁
     
    令和3年度は，時系列的単一細胞遺伝子発現データを，前年度までに収集したものに加えて，本研究費を用いて長浜バイオ大学・小倉教授等と協力することでさらに拡充した．炎症進行に伴う変化に重要な役割を果たす遺伝子の候補を発見するための遺伝子相関ネットワーク上のランキング手法として，正負の重みの辺(それぞれ遺伝子同士の細胞内発現量の正の相関と負の相関に対応)を同時に用いた手法を提案し，筑波大学・島野研究室，東京大学・村上研究室，東京理科大学・松島研究室等からのフィードバックを得て，改良の方針を策定した．さらにランキング以外の手法として，Web上の関連ページ群発見手法であるLouvain法を遺伝子相関ネットワークに適用し，遺伝子のクラスタリングを行うことで，炎症進行メカニズムの既知の成果に対して整合する機能を持つ遺伝子群の分類が可能になることを示した．また，PCAと(異常検知に使われてきた)deviation netを組み合わせた深層学習を用いて，発病前の細胞と炎症初期段階の細胞とを分類する手法も提案し，上記の単一細胞遺伝子発現データに対して性能検証実験を行い，既存の分類手法より高い精度が得られることを確かめた． 結果として，生物学的にはまだ未検証の点は多いものの，遺伝子相関ネットワークが単一細胞遺伝子発現データに対する(ランキング，クラスタリング等のデータマイニングや機械学習的手法を含む)ネットワーク分析の基盤として有用であることを確かめたと言える．これらの結果について，ランキング関連のものについては論文にまとめ，国際会議BIBM 2021の査読付きワークショップに採録された．また分析に必要なネットワークアルゴリズムに関する成果を査読付き国際会議SFDI2021の招待論文として発表した.さらに他の結果についても，論文投稿準備中である．
  • 日本学術振興会：科学研究費助成事業
    Date (from‐to) : 2018/04 -2022/03 
    Author : 吉川 正俊; 浅野 泰仁; 中野 圭介; 鬼塚 真
     
    本研究の目標である信頼性の高い自律分散環境の実現には，表現力の高い双方向変換言語が不可欠である．本年度は，一般的な双方向変換言語がもつべき表現力について計算論的アプローチによって考察し，その部分的な解として対合とよばれる関数に対する計算モデルを構築した．また，自律分散環境における更新伝播の不整合関係の検出アルゴリズムについても実装を進めた． また，時間変化するクエリワークロードの特性を捉えることで，スキーママイグレーションコストとクエリワークロードの実行コストを最小化するスキーマ最適化の研究に取り組んだ．特に，1) ワークロードを階層的に要約することで候補解を枝刈りする手法を考案し，2) 解を局所探索することにより大量クエリに対して高速に最適解を探索する手法を考案し，探索解の精度劣化を押さえながら最適化時間を1/10に削減できることを確認した． さらに，CDMSのアプリケーションとなるライドシェアリングサービスアライアンスの分散データ統合について研究し，3種類のモデル(集中型の調停者ビューモデル，非集中型のプロバイダビューモデル及びユーザビューモデル)を提案した．また，開発中の共有型実体化ビューアーキテクチャ(Dejima 1.0及びBCDS)によるこれらのモデルの実現性を明らかにした．差分プライバシを利用した分散環境における連合学習では，局所差分プライバシとシャッフルモデルを用いた手法を開発し，従来手法に比べ効用が大幅に改善することを示した．位置情報プライバシについては，利用者がどの位置同士は敵対者から区別ができないようにしたいかを示すポリシーを遵守しながら差分プライバシーを満足する手法を考案しプロトタイプを開発した．
  • 日本学術振興会：科学研究費助成事業
    Date (from‐to) : 2018/04 -2020/03 
    Author : 浅野 泰仁
     
    松島研究室で作成された単一細胞シークエンス時系列データ(ブレオマイシン投与による肺線維症誘導マウスの遺伝子発現の時系列データ)を調査し，炎症進行に伴う変化を分析するための「遺伝子相関ネットワーク」(注: 遺伝子間の物理的なつながりを表すモデルではなく，発現量の相関が高い遺伝子対を辺でつないだ独自のネットワークモデル)を提案した．本モデルの構築には単一細胞シークエンスデータのノイズ除去を行う最新手法MAGICを活用することで，分析に適したネットワークが得られることを確認した．さらに，時系列データの各時点ごとに得られたネットワークの変化を捉えやすくするために，全時点に対して遺伝子の位置を統一した可視化手法を提案した．これらを用いて炎症進行に伴う変化を分析したところ，遺伝子相関ネットワークにおいて、細胞ごとの発現の増減で負の相関関係にある遺伝子対に相当する辺に特徴的な時系列変化を発見することができた．この結果は炎症進行と遺伝子相関ネットワークの変化が何らかの関係を持つことを示唆していると考えられる．この結果を論文にまとめ，第39回医療情報学連合大会・第20回日本医療情報学会学術大会において発表した．また，シークエンス時系列データに適用できる機械学習について検討した．さらに，連携研究者と協力して，糖尿病マウス等を作成し，単一細胞シークエンス時系列データを取得し，上記の手法を適用することで遺伝子相関ネットワークを構築した結果，やはり上記同様の，負の相関関係にある遺伝子対に相当する辺に特徴的な時系列変化を発見することができた．
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2017/04 -2020/03 
    Author : Uchida Yasutaka
     
    A flexible pressure sensor is used to measure the state of getting up from the bed and the subsequent start of walking. Measurement of pseudo-body condition changes and differences between subjects can be classified by a device that applies machine learning. A survey of dialysis patients was scheduled to be conducted, but this was postponed because it coincided with the spread of the new coronavirus. Also, we examined and improved the cloud services to be used and collected information on daily activities and physical conditions. Using these results, we conducted qualitative analysis results and text mining analysis, and showed that it was possible to associate words that were not related in each analysis. From the long-term spectral analysis of the pulse wave, we found a peak that is considered to represent a physiological phenomenon.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2016/04 -2019/03 
    Author : Yoshikawa Masatoshi; CAO Yang
     
    It is important to collect, analyze, and utilize personal data for pubic welfare as well as protecting privacy. In this research, we have developed a market mechanism for personal data exchange which allows each individual to specify an upper limit of the degree of disclosure of her personal data. Recently, differential privacy, which can express privacy information leakage risk mathematically, is widely studied. However, since differential privacy was developed for static data, We have extended the notion of differential privacy to be applicable to time series data.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2015/04 -2019/03 
    Author : Asano Yasuhito; Zhang Xinpeng; Shimizu Toshiyuki
     
    We have studied fundamental techniques for discovering and organizing knowledge about implicit relationships between concepts. We have also studied applications of connecting different kinds of data utilizing implicit relationships of concepts contained in the data. Implicit relationships between concepts are different from explicit relationships such as "A is a part of B" which are described explicitly on documents or data; they are relationships obtained by analyzing documents or data and connecting discovered explicit relationships found on several parts. We have established network analysis methods and text analysis techniques required as fundamental techniques for discovering such relationships. We have also established several analysis methods for particular kinds of data to apply the techniques above.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2015/04 -2018/03 
    Author : Asano Takao; ASANO YASUHITO
     
    We have done algorithmic researches on interdisciplinary topics on highly connected giant network world from the viewpoint of informatics, economics and sociology. Specifically, we proposed an algorithm for the Steiner forest problem, which is a kind of generalization of the Steiner tree problem and one of most important problems in computer science, and evaluated its approximation performance by computational experiment and by comparing the known algorithms for the Steiner forest problem. We also considered a combinatorial auction problem and gave characterizations for the existence of a Nash equilibrium in such a combinatorial auction. These results were published in Journal of Information Processing Society of Japan (and will be published in IEICE Transactions on Fundamentals). Furthermore, we considered the dial-a-ride problem with regret minimization and the result will be published as a paper in Journal of Japan Society of Mechanical Engineers.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2011 -2013 
    Author : ASANO Yasuhito
     
    In this work, we have aimed to construct the following two fundamental technologies (1)-(2) for developing collective intelligence: (1) methods for complementing collective intelligence from the Web utilizing information structure of the collective intelligence, and (2) methods for organizing and presenting obtained knowledge. The results for (1) include a method for complementing lacked text information on the Wikipedia from the Web and a method for finding lacked visual information on the Wikipedia, especially images for explaining the relationship of specified two entities, from the Web. The results for (2) include a method for presenting images collected from the Web for explaining the relationship of specified two entities, by combining knowledge on Wikipedia for the relationship.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2011 -2013 
    Author : ASANO Takao; ASANO Yasuhito
     
    We considered routing and scheduling problems on a network as a combinatorial auction problem for maximizing the social welfare of all participants on the network and investigated the existence of a stable solution (Nash equilibrium) which all participants agree on. We gave a characterization for the existence of a Nash equilibrium in such a combinatorial auction when valuations by all participants satisfy symmetric and subadditive properties. By this characterization, we obtained an algorithm for deciding a Nash equilibrium exists. Furthermore, we showed that, if valuations by all participants satisfy symmetric and submodular properties, Nash equilibrium always exists and we can find such a Nash equilibrium in polynomial time.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2009 -2012 
    Author : IWAIHARA Mizuho; YOSHIKAWA Masatoshi; MA Qiang; ASANO Yasuhito
     
    The aim of this project is to develop technologies for extracting useful information from social contents. Wiki-style contents are edited by many contributors. We developed an algorithm to accurately reconstruct derivation of contents from edit histories. We also analyzed tendencies of users’ privacy settings, and utilized these findings in recommending appropriate settings to users. We further developed efficient access control methods for contents.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2008 -2011 
    Author : YOSHIKAWA Masatoshi; MA Qiang; ASANO Yasuhito; SHIMIZU Toshiyuki; IWAIHARA Mizuho; SUZUKI Yu
     
    We have studied management methods for annotation data on information, and coreference analysis in order to keep the quality of information on Web servers high. We have developed a system for storage and retrieval of RDF data representing knowledge resource as well as integrated usage system of retrieval engines and user generated knowledge resource Wikipedia. Also, we have developed a system for consistency analysis and a method for incremental update of causal relation networks.
  • 日本学術振興会：科学研究費助成事業
    Date (from‐to) : 2009 -2010 
    Author : 吉川 正俊; 岩井原 瑞穂; 馬 強; 浅野 泰仁; 清水 敏之; 鈴木 優
     
    集合知の体系化として,Wikipediaの記事間のハイパーリンクを利用し,減衰流を用いて記事が表す事項間の関係の強弱を計測する新たな手法を開発した.減衰流による関係の強さの尺度は,既存の尺度である距離連結度,共引用の概念を包含したものとなり,他の尺度よりも高い精度を持つことを明らかにした.出発点から到達点に至る流路に存在する節点を説明オブジェクトとし,それを基に,入力された二つの項目の関係の全体または一部を説明する画像をWebから検索するアルゴリズムを開発した.さらに,Wikipediaの記事において,記事項目に対応するオブジェクトと何らかのオブジェクトとの関係を表す画像が,記事にふさわしいかどうかを判定する手法を開発した. 集合知の信頼度推定としては,Wikipedia記事の多くの著者らによる記事の変更履歴に基づき,既存の素性に加え,新たに筆者グループ間における記事の更新を取り消し合う状況を表す素性を導入した手法を開発し,Wikipediaの情報の信頼度推定精度が向上することを確認した. また,大量のニュース記事からの因果関係抽出による因果関係ネットワークの増分構築手法を開発した.トピックと内容を独立して事象を表現するモデルを用いて事象間の同一性判定を類似トピック内に限定することによる計算量の削減を実現した.さらに,事象を表現する語彙の役割(SVO構造)と意味(概念)を考慮してネットワークを構築する手法を提案し,事象の内容を表す語の役割を考慮し,WordNetやオントロジーを用いて概念レベルで事象の類似性を計算することで,ネットワーク構築の一貫性を保つことを可能とした.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2009 -2010 
    Author : ASANO Yasuhito
     
    We have systemized knowledge about events useful for analyzing causal relationships and helping judgments of information credibility. The summary of our work is the following (1)-(3) : (1) Time graph pattern mining methods for analyzing propagation of eventual knowledge. (2) A model of eventual knowledge and a method of extracting eventual knowledge. (3) A method for computing the strength of the relationship between two objects and obtaining objects elucidating the relationship. We have also applied ideas used in this method to helping a user to judge the credibility of an image on Wikipedia.
  • 日本学術振興会：科学研究費助成事業
    Date (from‐to) : 2006 -2007 
    Author : 浅野 泰仁
     
    本研究では,Web上のコミュニティ(関連するページの集合)を求める情報検索手法として代表的なFlakeらの最小カット法の問題点を調べることによって,スパムリンクに関する様々な知見を得た.これをもとに,スパムリンクを自動的に除去することで,悪質なスパムページが情報検索の結果から除かれるような高精度の手法を提案した.具体的には,Webページの重要度を計算する著名なアルゴリズムであるHITSを改良した.HITSアルゴリズムは,Kleinbergによって提案された当時は高い精度を持っていたが,現在のWebにおいてはスパムページの増加により精度が低くなっていた.本研究では,スパムリンクを自動的に除去してHITSの精度を高めるために,2つの手法を提案した.1つは,Webページが属するホストが利用しているDNSサーバーの名前を用いてスパムリンクの集合である「リンクファーム」を発見し除去する手法である.もう1つは,ページの信頼度を計る手法としてGyongiらによって提案されたTrustRankと呼ばれる手法のアイディアをHITSに適合するように工夫して,ページがスパムでない確率を評価することができるようにした「トラストスコア」である.これら2つの手法をHITSに組み込むことで,その精度を大幅に高めることができた.本研究の成果は,"Improvements of HITS Algorithm for Spam Links"という表題で,APWeb/WAIM国際会議にregular paperとして採録された.なお,本会議のregular paperの採択率は9%以下であった.また、この成果はIEICEの論文誌にも採録された.
  • 日本学術振興会：科学研究費助成事業
    Date (from‐to) : 2004 -2007 
    Author : 西関 隆夫; 周 暁; 伊藤 健洋; 三浦 一之; 浅野 泰仁
     
    (1)平面的グラフの折れ曲がりなし直交描画問題について,グラフが3連結立方グラフの細分であれば,折れ曲がりなし直交描画を線形時間で求めることのできるアルゴリズムを与えた. (2)直並列グラフの直交描画で折れ曲り数最少のものを求める線形アルゴリズムを開発した. (3)平面グラフの格子凸描画において,別個に研究されてきた標準分解,リアライザ,シュナイダーラベリング,順序つき全域木がすべて同等であることを証明した. (4)VLSIレイアウトに平面グラフの内部矩形描画が応用できる.与えられた平面グラフが内部矩形描画できるかどうか判定し,できるならば内部矩形描画を高速に求めるアルゴリズムを与えた. (5)電力供給問題のモデル化であり,一般には強NP困難問題として知られる,需要・供給付きグラフの分割問題について研究し,分割数を最少・最多にする問題,および指定された個数の連結成分への分割を求める問題に対して,グラフが木(または部分k-木)であるときに厳密解を求める多項式時間(または擬似多項式時間)アルゴリズムを与えた. (6)購入した計算機を用いてウェブ文書データを解析し,サイトのデータを抽出し,このデータからサイトを点とするサイト間グラフを構築した.さらに,サイト間グラフの特徴を利用して,著名な情報検索手法であるmax-flow based methodの品質を大幅に改善する手法を確立し,実験によってその性能を検証した.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2005 -2006 
    Author : NISHIZEKI Takao; ZHOU Xiao; ITO Takehiro
     
    In this project, we consider the coloring problem, the disjoint path problem and the drawing problem for structured graphs such as trees, series-parallel graphs and partial k-trees, and succeeded in obtaining efficient algorithms for these classes of graphs. We also establish the foundation for the unified methodology of designing efficient algorithms for structured graphs. For trees, we obtain a fully polynomial-time approximation scheme (FPTAS) for the partitioning problem of trees having supply and demand. For series-parallel graphs, we first obtain a sufficient condition for the existence of a list total coloring, and then give a linear-time algorithm to find a list total coloring. For partial k-trees, we succeeded in obtaining three algorithms : the first is a linear-time algorithm for the total coloring problem ; the second is a pseudo-polynomial-time algorithm for the uniform partitioning problem ; and the third is a pseudo-polynomial-time algorithm for the partitioning problem on graphs with supply and demand. Concerning graph drawing, we obtain a linear-time algorithm to find an orthogonal drawing of series-parallel graphs with the minimum number of bends, and give a graph decomposition applicable to a convex drawing. In conclusion, we succeeded in designing efficient algorithms for various problems, and laid the foundation of unified methodology to design efficient algorithms for combinatorial problems, especially for the partition problems to edge-disjoint subgraphs. These results are published in seven journal papers and five proceedings papers of international conferences.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2004 -2006 
    Author : ZHOU Xiao; NISHIZEKI Takao
     
    In a field of a computational complexity theory and algorithm theory, various combination problems on graphs have been studied. It is known that the most of such problems, including a lot of practical problems, are NP-hard. On the other hand, it is known that some of these problems can be solved in polynomial time for restricted classes of graphs, named partial k-trees. However, in my best knowledge there exist polynomial-time algorithms for solving some particular problems on partial k-trees and no general methods for it. In this research, I investigated existing algorithms for partial k-trees and find some algorithms to solve some combination problems of a part k tree including a [g, f]-coloring algorithm, a multiple coloring algorithm, a cost coloring algorithm, etc. It succeeded to find some conditions for solving some combination optimization and building the methodology that could generate efficient algorithm to solve those problems automatically. Furthermore, for a small k, say one (trees) or two (series-parallel graphs), it succeeded to develop polynomial-time algorithm for solving cost coloring problem, multiple coloring problem, etc. Inspection of effectiveness of the technique was possible theoretically. In this research, I have published 17 journal papers and 20 international conference papers. As a result of having been provided, I give many linear-time algorithms. Its impact in a field of a linear-time algorithm theory is very big.
  • 日本学術振興会：科学研究費助成事業
    Date (from‐to) : 2004 -2005 
    Author : 浅野 泰仁
     
    1 東京大学生産技術研究所喜連川研から提供を受けた,約3億のURL(ページ)と約10億のリンクを含むテキストデータを用いて,我々の提案したフィルタ法を用い,約600万のディレクトリベースドサイトを抽出した.なお,この手法の誤り率は5%以下ということも検証した.ディレクトリベースドサイトは我々が提案したサイトのモデルである. 2 Web上の情報検索手法の一つに,コミュニティ(関連するページの集合)を求めるものがある.代表的なものとしてFlakeらの最小カット法があるが,サイトを用いることが最小カット法にどれだけ有用であるかはわかっていなかった. 我々は,最小カット法がページを用いていたがゆえに内包していた問題点を明らかにした.なお,問題点は,ページを用いていたのでは「相互リンク」を正しく利用することができないことなど,全部で4つある. 我々はこれらの問題点に対する解決法を提案し,サイトを用いた上記の手法に適用した結果,精度も既存の手法の約46%から約72%へと大幅に向上させることに成功した.コミュニティの大きさも既存の手法の2倍程度となった.また,提案した解決法の効果を詳しく解析し,サイトを効果的に用いることがWeb情報発見手法に大きく役立つことを示した.この結果はWeb分野の権威ある国際会議WISE 2005に再録された.雑誌にもこの結果を投稿中である. 3 多くの問題を解く基礎となる組み合わせ最適化分野において,Vygen, Korte著の"Combinatorial Optimization"の翻訳に参加した.訳書は,「組み合わせ最適化」(訳:浅野孝夫,平田富夫,小野孝男,浅野泰仁)としてシュプリンガー・フェアラーク社から2005年に発行された.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2003 -2004 
    Author : NISHIZEKI Takao; ZHOU Xiao; RAHMAN Md.Saidur; MIURA Kazuyuki; ASANO Yasuhito
     
    In a rectangular drawing, all the faces including the outer face must be drawn as rectangles. Thomassen gave a necessary and sufficient condition for a plane graph to have a rectangular drawing. However, the condition applies only for a graph of maximum degree Δ three. In this research, we first introduce a new drawing style called an inner rectangular drawing, in which all inner faces must be rectangles but the outer face can be an axis-parallel polygon like an L-shape or T-shape polygon. We then give a necessary and sufficient condition for a plane graph to have an inner rectangular drawing not only for Δ≦3 but also for general Δ. We also give an efficient algorithm to find an inner rectangular drawing. These results solve an open problem for these thirty years, and have many practical applications.v We propose another new drawing style called a box-rectangular drawing, which is a generalization of a rectangular drawing and a box-orthogonal drawing. We then obtain an efficient algorithm to find a box-rectangular drawing. The algorithm takes time linear in the number of vertices in a given graph, and hence the time complexity is optimal, and cannot be improved any more. A conventional method for designing a VLSI layout uses a rectangular drawing, and may produce a layout in which some modules would be adjacent although they should not be adjacent. A new method using our algorithm produces a layout without such an unwanted adjacency of modules. For other drawing styles such as a straight-line drawing, a convex drawing, and a rectangle-of-influence drawing, we obtain new efficient algorithms for finding drawings of small area. In particular, we succeeded in obtaining an algorithm to find a straight-line drawing of a four-connected plane graph. The algorithm requires one quarter of the area required by the known algorithm.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2002 -2004 
    Author : ASANO Takao; ASANO Yasuhito
     
    The objective of this research is to investigate a systematic approach to network approximation algorithms with performance guarantees from both theoretical and practical points of veiw and to clarify its usefulness and bound on the development of algorithmic researches which will be important for information technology in this centuary. To achive this objective, we have done the following researches. We made an investigation on semi-definite programming and linear programming techniques, which are considerd to be potential systematic approaches to designing and analyzing network approximation algorithms with performance guarantees. More specifically, we surveyed the recent trends by translating the book of Approximation Algorithms written by V.V.Vazirani and the book of Combinatorial Optimization written by B.Korte and J.Vygen. These two books are considered to be the best books describing the most recent progress in network algorithms and approximation algorithms in the world. Through this survey, we obtained some power and applied this power to developing new network approximation algorithms. Acutually, we proposed the current best approximation algorithm for MAX SAT. We also proposed several algorithms for exploiting inforamtion from the Web based on network approximation algorithms. These proposed algorithms were published in high standard international conferences and Journal. In view of this, we believe, the objective of this research is satisfactorily achieved.

Other link

researchmap