IPSJ SIG Technical Report Vol.2009-DBS-149 No /11/ Bow-tie SCC Inter Keyword Navigation based on Degree-constrained Co-Occurrence Graph

Size: px

Start display at page:

Download "IPSJ SIG Technical Report Vol.2009-DBS-149 No /11/ Bow-tie SCC Inter Keyword Navigation based on Degree-constrained Co-Occurrence Graph"

みがねやたけ
4 years ago
Views:

1 1 2 1 Bow-tie SCC Inter Keyword Navigation based on Degree-constrained Co-Occurrence Graph Satoshi Shimada, 1 Tomohiro Fukuhara 2 and Tetsuji Satoh 1 We had proposed a navigation method that generates directed graph based on co-occurrence words, and leads users to the related document in the document space. In the method, because of to reduce user s load, maximum outdegree of nodes is constrained. However, the correlation of the threshold and the characteristic of generated graph was not clear. In this paper, we describe the experiment that to clarify this correlation using the newspaper article. And we discuss about utility of the generated graph by considering SCC (Strong Connected Components) in the Bow-tie structure. 1 Graduate School of Library, Information and Media Studies, University of Tsukuba 2 Research into Artifacts, Center for Engineering, The University of Tokyo 1. Wikipedia Comprehensive Web Navigation Small-world 1) Bow-tie 2) SCC Comprehensive Web Navigation SCC SCC c 2009 Information Processing Society of Japan

2 ) 2.2 5) STB 6) Web Wikipedia Wikipedia 3. Comprehensive Web Navigation 3.1 Comprehensive Web Navigation Comprehensive Web Navigation Small-world Small-world 1) Small-world L C 4) Small-world Comprehensive Web Navigation Small-world 2 c 2009 Information Processing Society of Japan

3 1 df I 0.6 > 2 10 II 0.35, < 0.6 > 9 < 19 1 III 0.1 > IV I II III 0.01 (a) (b) 1 Broder World Wide Web WWW Bow-tie 2) Bow-tie SCC Strongly Connected Components SCC IN SCC OUT IN OUT Tendrils IN OUT Tubes DCC Disconnected Components Bow-tie IN OUT Tendrils Tubes SCC IN SCC ) 1 2 URL 1 df 2 /df 7) df df 2 4 I II I 1 I II df III IV 300 8) df < 3 1 I II 3 c 2009 Information Processing Society of Japan

4 ,770 20,103 3 C L 20,103 1,783, ( ) ( ) ( ) t i D i T i = {t 1,..., t n } t i t k D ik = {d 1,..., d m } t i t k r(t i, t k ) (1) w k t k r(t i, t k ) = mw k : i k (1) t i 1 r r df 3 4. Bow-tie SCC (a) (b) 2 3 2(a) Small-world 4.2 ( 1 ) ( 2 ) ( 3 ) Bow-tie ( 4 ) Bow-tie 4 c 2009 Information Processing Society of Japan

5 (a) 1 (b) 3 (c) 8 (d) 17 (a) (b) 3 (e) 32 (f) 64 (g) 128 (h) 4,096 5 (a) (C) (b) (L) (c) 4 Pajek (a) 3(b) % Small-world 4(a) 4(b) c 2009 Information Processing Society of Japan

6 Small-world 17 4(c) Small-world 5 k P (k) k ,096 3, Bow-tie Bow-tie SCC SCC IN SCC OUT SCC IN OUT Tubes IN OUT SCC Tendrils DCC 6(a) % DCC % Tendrils IN 5.9% 3 IN 91.4% SCC % SCC Tendrils IN IN 4 SCC IN SCC 18 (a) Bow-tie 6 (b) SCC 4 Bow-tie C L SCC 17, , DCC 2, SCC Bow-tie 4 SCC SCC 6(b) SCC SCC SCC % 5.7% 0.7% Bow-tie Bow-tie SCC 7 Pajek 3 FR 11 SCC SCC 6 c 2009 Information Processing Society of Japan

情報処理学会研究報告 (a) 最大出次数 2 (b) 最大出次数 3 (c) 最大出次数 4 (a) 最大出次数 3 (b) 最大出次数 5 図8 (d)

サブグラフの可視化結果距離感のあるノードが含まれているこれは SCC が巨大になり SCC の内部にもフラクタルに Bow-tie

を除去したグラフを可視化した結果を図 9 に示す最大出次数 3 では OUT Tubes Tendrils のみからなるサブグラフにおいても

不良債権介護保険のクラスタが形成された中心部には製紙業界再編に本節では 3 節で挙げたナビゲーションに適するグラフ構造の要件に対応して考察する

1 Small-world 性短い平均距離で多様なノードへ到達できるためにはグラフ全体が Small-world 性を示すの部分におけるクラスタは消滅し

考ことが大前提となる提案手法において UI 設計の観点から暫定的に設定した最大出次数 8 察の場合に Small-world 性を示すだけでなく

性を示すことが確認できたただし平均距離は到達可能ペアのみを用いて算出する最大い語を精度よく提示することよりも提示項目を次々に選択することで

7 情報処理学会研究報告 (a) 最大出次数 2 (b) 最大出次数 3 (c) 最大出次数 4 (a) 最大出次数 3 (b) 最大出次数 5 図8 (d) 最大出次数 5 (e) 最大出次数 8 図7 (c) 最大出次数 8 SCC および IN を除去したグラフの可視化結果 (f) 最大出次数 11 SCC サブグラフの可視化結果距離感のあるノードが含まれているこれは SCC が巨大になり SCC の内部にもフラクタルに Bow-tie 構造が生じていることを意味する (a) 最大出次数 3 (b) 最大出次数 5 (c) 最大出次数 8 SCC および IN を除去したグラフを可視化した結果を図 9 に示す最大出次数 3 では OUT Tubes Tendrils のみからなるサブグラフにおいても複数のクラスタが形成され図9 IN を除去したグラフの可視化結果ている外周部にはビール石油航空衛星放送に関連する語のクラスタが形成され内周部には不良債権介護保険のクラスタが形成された中心部には製紙業界再編に本節では 3 節で挙げたナビゲーションに適するグラフ構造の要件に対応して考察する関連する語のクラスタが形成された最大出次数が大きくなると OUT Tubes Tendrils 5.1 Small-world 性短い平均距離で多様なノードへ到達できるためにはグラフ全体が Small-world 性を示すの部分におけるクラスタは消滅し SCC に取り込まれていく 5. 考ことが大前提となる提案手法において UI 設計の観点から暫定的に設定した最大出次数 8 察の場合に Small-world 性を示すだけでなく最大出次数を変化させても同様に Small-world 包括的な内容把握を支援するためのキーワード間ナビゲーションにおいては関連性の高性を示すことが確認できたただし平均距離は到達可能ペアのみを用いて算出する最大い語を精度よく提示することよりも提示項目を次々に選択することで文書空間内を広く出次数が小さすぎると到達可能ペアが極めて少なくなるため平均距離が短いとはいえ多様飛び回れることが重要になる提示内容の妥当性も検証する必要があるがそれ以前の課題なノードへ到達できる構造にはならないまた同じ Small-world ネットワークにおいても次数分布によって特性が大きく異なとしてグラフ構造そのものがナビゲーションに適した構造を持つことが要求される 7 c 2009 Information Processing Society of Japan

8 5.2 SCC Small-world SCC SCC SCC 5.3 Bow-tie IN OUT SCC Tendrils SCC SCC SCC 3 SCC IN 24 SCC 10 SCC SCC Comprehensive Web Navigation Small-world Small-world Bow-tie SCC 24 SCC SCC 3 10 Comprehensive Web Navigation CGM 1) Watts,D. and Strogatz,S.: Collective dynamics of small-world networks, Nature, Vol. 393, No. 6684, pp (1998). 2) Broder,A. et al.: Graph structure in the Web, In Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications networking,, pp (2000). 3) White, R., Kales, B., Ducker, S. and Schraefel, M.: Supporting exploratory search, Communications of the ACM, Vol.49, No.4, pp (2006). 4),, Small World,, Vol.43, No.6, pp (2002). 5),,, Web, Web (DBWeb Forum) 2007, 1A-3 (2007). 6),,,,,,,,, 7 (FIT 2008), 2, pp. 1 4 (2008). 7),,., Vol. 2001, No. 112, pp (2001). 8),, 70,, 5S-1 (2008). 9),, Web, Web (WebDB Forum) 2008, 5A-2 (2008). 8 c 2009 Information Processing Society of Japan

DEIM Forum 2010 A Web Abstract Classification Method for Revie

DEIM Forum 2010 A Web Abstract Classification Method for Revie DEIM Forum 2010 A2-2 305 8550 1 2 305 8550 1 2 E-mail: s0813158@u.tsukuba.ac.jp, satoh@slis.tsukuba.ac.jp Web Abstract Classification Method for Reviews using Degree of Mentioning each Viewpoint Tomoya