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 2 3 4 5 6 1 c 2009 Information Processing Society of Japan
2. 2.1 3) 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
1 df I 0.6 > 2 10 II 0.35, < 0.6 > 9 < 19 1 III 0.1 > 3 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 3.2 1 9) 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
2 1996 7,770 20,103 3 C L 20,103 1,783,732 0.0044138 0.6636081 2.49359 7 ( ) ( ) ( ) 0.0044116 2.66863 3 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 4.1 1996 2 1996 1 2 3 1 (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
(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 1 4.3 4.3.1 1 http://pajek.imfm.si/doku.php 2 3(a) 3(b) 1 64 20% Small-world 4(a) 4(b) 2 1 24 32 48 64 96 128 192 256 512 768 1024 1536 2048 3072 4096 38 5 c 2009 Information Processing Society of Japan
1 2 3 3 Small-world 17 4(c) 4.3.2 Small-world 5 k P (k) k 1 8 9 8 4,096 3,879 4.3.3 Bow-tie Bow-tie SCC SCC IN SCC OUT SCC IN OUT Tubes IN OUT SCC Tendrils DCC 6(a) 1 96.8% DCC 2 94.0% Tendrils IN 5.9% 3 IN 91.4% SCC 8 378 1.9% SCC Tendrils IN IN 4 SCC IN SCC 18 (a) Bow-tie 6 (b) SCC 4 Bow-tie C L SCC 17,166 891,855 0.0060532 0.7771475 2.49359 7 DCC 2,937 11 0.0000026 0.0000000 1.00000 1 128 SCC Bow-tie 4 SCC SCC 6(b) SCC SCC 1 24 10 32 SCC 6 100.2% 5.7% 0.7% 4.3.4 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) 最大出次数 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
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 3 10 6. 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. 440 442 (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. 309 320 (2000). 3) White, R., Kales, B., Ducker, S. and Schraefel, M.: Supporting exploratory search, Communications of the ACM, Vol.49, No.4, pp.36 39 (2006). 4),, Small World,, Vol.43, No.6, pp. 1825 1833 (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. 27 32 (2001). 8),, 70,, 5S-1 (2008). 9),, Web, Web (WebDB Forum) 2008, 5A-2 (2008). 8 c 2009 Information Processing Society of Japan