DEIM Forum 2009 C8-4 QA NTT 239 0847 1 1 E-mail: {kabutoya.yutaka,kawashima.harumi,fujimura.ko}@lab.ntt.co.jp QA QA QA 2 QA Abstract Questions Recommendation Based on Evolution Patterns of a QA Community Yutaka KABUTOYA, Harumi KAWASHIMA, and Ko FUJIMURA NTT Cyber Solutions Laboratories, NTT Corporation Hikarinooka 1 1, Yokosuka-shi, Kanagawa, 239 0847 Japan E-mail: {kabutoya.yutaka,kawashima.harumi,fujimura.ko}@lab.ntt.co.jp In an existing QA site, it is necessary for repliers to retrieve attractive questions for themselves. In this paper, we propose a method to retrieve questions for which each replier is likely to give an answer. In our method, based on the possibility of a new answer in local structure of the QA network, we discover two users between whom a new answer is likely to be derived. The QA Network is such a graph that each node mean a user and each edge mean an answer. In this paper, we describe our method and report experimental evaluation of our method. Key words question answering, network motifs, time series analysis, link prediction 1. QA Web u QA v 2 QA QA goo 1 Yahoo! u v goo 400 QA QA QA u QA v v ( ) u QA 1 http://oshiete.goo.ne.jp/ u v QA 3 t 0 t 1 t 0
1 3 2. 2 QA 3 t 1 3 1 t 1 t 2 Newman [4] 2 2 2 2. 2 2. 1 2 Jaccard Milo [1] [5], [6] 2 Adamic [7] ( ) ( ) 2 2 [8] [4] ( ) 3 1 (a) WWW 1 (b) [4], [9] 1 2. 3 QA n k QA O(n k ) goo QA [10] Adamic [11] Yahoo Answers Wernicke [2] 3 [12] Yahoo! Apache [3] 3 [13] Yahoo! QA 30 Wikipedia
2 QA 4 3 QA 3 3 3 3 13 3. QA 3 30 30 QA 1 [3] ID 30 ID 1 (1) 2 1 1 2 1 2 2 1 2 2 3 3 a 53 t u v 53 QA v n v u n u e vu 2 1 3 4 t 2 2 4 5 t QA QA 4. 2 4 4. t 0 QA Q 0 t 1 QA Q 1 t 1 t 2 v {a t 1 < t < t 2, n u, n v Q 1 } Q 2 Q 1 U given V 1 1 v U 1: Q 0 t 0 QA Q 0 3 4. 1 3 30 2: t 0 t 1 2 1 3 53
1 5 t 0 t 1 t 2 1434 4746 2756 9200 3900 12807 2265 7103 3073 9281 3685 10688 EXPLICIT 1720 5079 2874 8586 3145 9382 1393 4506 2383 7665 2986 9269 3116 7128 4259 9450 4910 10681 PHP 2425 5112 4208 8864 5540 11499 3 2 ( ) 2236 7495 3356 10974 4044 12955 2481 7761 3396 10443 3914 11880 1786 5747 2971 9106 3756 11175 Java 4449 9840 5872 13030 6838 15084 2 1 t 0 3 2 EXPLICIT 5 2 p i p j answerfreq(p i, p j ) ( 4 answerfreq(1, 2) = 4 answerfreq(2, 1) = 0 answerfreq(2, 2) = 2...) 3: 2 2 2 answerfreq(p i, p j ) 3 σ(p i, p j) QA structurescore(p i, p j ) answerfreq(p i, p j ) 3 answerfreq(p i, p j ) σ(p i, p j ) Z (13) structurescore(p answerfreq(30, 30) i, p j) = answerfreq(p i, p j ) answerfreq(p i, p j ) (1) σ(p i, p j) (1) 3 4: Q 1 (1) 1 2 2 1 t 1 QA answerfreq(1, 2) Q 1 3 5: 2 3 3 4 Q 1 3 2 t 1 3 t 2 n u n v t 0 t 1 4 Q 1 3 2 n u n v ( K 3 ) 2 n u n v (1 30 ) t 0 t 1 (p k u, p k v) (k = 1, 2,..., K) n u n v score(n u, n v) score(n u, n v ) = structscore(p k u, p k v) (2) 5. QA 5. 1 goo Wernicke [2] 309 k
10 2 QA (A) (R) (A R) 38777 3063 245 3 t 0 t 1 t 2 2006 1497 1308 10 1 2007 1 2007 8 1 7398 710 43 13076 1394 111 7774 1114 48 t 0(= 2006 1 ) PHP 41161 1996 156 QA Q 0 3 ( ) 9662 1769 54 ( 1) A 1 10 3683 1346 10 11168 Q 0 3 Java 15023 (1) (4) 1778 1541 37 71 (12) (13) t 0 u (12) (13) 5. 2 Q 1 t 1(= 2007 1 ) (12) (13) 3 t 2 (= 2007 8 ) (1) (3) ( 2 2) (1) (3) 2 ( 3) A 1 (A) t 1 (= 2007 1 ) t 2 (= 2007 8 ) 2 (R) t 1 (= 2007 1 ) QA Q 1 (A R) 2 3 ( 4) t 1(= 2007 1 ) t 2(= A 2 10 Q 1 3 2007 8 ) 2 (1) (3) t 1 Q 1 3 2 2 ( 5) 2 (v u 5. 3 u v) 4 V 1 1 1 u v t 0 (= 2006 1 ) t 1 (= v U 2007 1 ) v u 2 2 u v Q 1 3 (u, v) U V t 1 t 2 2 3 u t 1 (= 2007 1 ) t 1 (= 2007 8 ) 250 500 1000 2 (1) t 0 t 0 t 1 (= 2007 1 ) 2 ( / ) (2) t 1 (= 2007 1 ) 5. 4 Q 1 3 3 (3) 2 given 2 χ 2 2 v v 2 2 ( 4 ) 1% v given
3 v u @250 @500 @1000 : 39 1.58 46 3.16 70 6.32 4 1.67 6 3.34 9 6.68 2 12 1.45 18 2.91 22 5.81 23 2.12 37 4.24 54 8.49 17 1.54 22 3.09 27 6.17 PHP 42 0.95 55 1.90 71 3.79 ( ) 10 1.40 15 2.80 22 5.59 8 0.68 9 1.36 9 2.72 10 0.83 16 1.66 22 3.31 Java 16 1.18 21 2.36 25 4.73 4 χ 2 QA @250 @500 @1000 5.73 10 196 3.99 10 129 1.91 10 142 7.04 10 2 1.44 10 1 3.68 10 1 1.54 10 18 5.95 10 19 1.62 10 11 5.05 10 47 1.83 10 57 1.89 10 55 7.79 10 36 2.95 10 27 4.04 10 17 QA PHP 0.00 0.00 3.69 10 262 [1] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network Motifs: Simple Building Blocks of Complex Networks. Science, Vol. 298, No. ( ) 2.93 10 13 2.46 10 13 3.40 10 12 6.17 10 19 5.37 10 11 1.37 10 4 5594, pp. 824 827, 2002. 5.52 10 24 5.77 10 29 7.82 10 25 [2] S. Wernicke. Efficient Detection of Network Motifs. Java 1.80 10 42 6.00 10 34 9.43 10 21 IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, pp. 347 359, 2006. [3],,.. 2008, pp. 120 124, 2 2 2008. [4] MEJ Newman. Clustering and preferential attachment in 5. 5 growing networks. Physical Review E, Vol. 64, No. 2, p. 25102, 2001. 2 [5] R. Baeza-Yates, B. Ribeiro-Neto, et al. Modern information 2 (u, v) retrieval. Addison-Wesley Harlow, England, 1999. v u [6] D. Liben-Nowell and J. Kleinberg. The Link-Prediction Problem for Social Networks. JOURNAL-AMERICAN SO- CIETY FOR INFORMATION SCIENCE AND TECH- 2 (u, v) v NOLOGY, Vol. 58, No. 7, p. 1019, 2007. u v [7] L.A. Adamic and E. Adar. Friends and neighbors on the Web. Social Networks, Vol. 25, No. 3, pp. 211 230, 2003. [8] L. Katz. A new status index derived from sociometric analysis. Psychometrika, Vol. 18, No. 1, pp. 39 43, 1953. [9] AL Barabási, H. Jeong, Z. Néda, E. Ravasz, A. Schubert, 6. and T. Vicsek. Evolution of the social network of scientific collaborations. Physica A: Statistical Mechanics and its Applications, Vol. 311, No. 3-4, pp. 590 614, 2002. [10],,. QA.., Vol. 2008, No. 88, pp. 247 252, 2008. 3 30 [11] L.A. Adamic, J. Zhang, E. Bakshy, and M.S. Ackerman. Knowledge sharing and Yahoo Answers: Everyone knows something. Proceedings of the 17th international conference on World Wide Web, 2008. 53 53 2 [12],,,.., pp. 1 10, 2008. goo 10 [13],,. Yahoo!., pp. 11 18, 2007 1 8 2008. 2
A 1 Q 0 3 A 2 Q 1 3
A 1 PHP (1) (2) (3) (4) (5) (6) (7) (8) ( ) Java 1 2 0.220-0.250 4.431-0.395 0.006-0.392-0.411-0.099-0.264-0.098 2 1 4.927-0.303 2.525 3.085 4.652 2.768 1.032 0.846 3.912 0.992 2 2 1.391-0.608-0.433-0.468-0.649-0.200-1.289-0.807-0.031 1.771 3 4 0.948 2.175 0.820 1.830 2.734 0.585 0.114-0.637 5.403 0.874 3 5 1.239-0.243 3.134 1.048 1.251-0.216-0.421-0.054-0.275-0.657 4 3 1.231-0.241 0.324-0.478-0.501-0.864-0.206-0.404-0.295-0.686 4 5-0.433-0.246 4.899-0.081-0.366 0.992 0.727-0.240-0.325-0.407 5 3 5 4 6 7 7.230-0.737-0.123 6 8 5.932-0.045 7 6 6.273-0.737-0.133 7 8-0.886-0.095-0.303 8 6 8 7 9 9 2.936 1.905 2.010 0.344 3.329 2.301-0.396-0.480 4.352 0.563 9 10 1.047 0.518 4.988 0.904 4.584 3.464 0.115-0.136 1.370 1.554 10 9 11 12 6.084 1.279 4.493-0.873 4.676 2.534-0.406-0.331 5.852-0.035 11 13 0.480-0.048 3.865 2.083-0.149-0.077-0.546 0.990-0.639-0.427 12 11 1.134 3.077 3.557 2.028-0.156 3.043 1.809-0.273 4.150 0.317 12 13 0.252-0.048 3.214-0.896-0.262 1.091-0.504 1.197 0.398 13 11 13 12 14 14 7.256-0.128 14 15 5.590-0.045-0.289 15 14 16 17 5.856-0.128 16 18 6.816 2.005 2.116 17 16 5.607-0.737 17 18-0.795-0.115 0.818-0.101 18 16 18 17 19 20 20 19 20 20-0.071 (9) 21 21-0.055-0.207 (10) (11) (12) 22 23-0.988 22 24 4.776 23 22 0.587 23 24-0.427 24 22 24 23 25 25 4.776 25 26 0.806-0.220-0.160 26 25-0.763 27 28 27 29 28 27 28 29 29 27 29 28 (13) 30 30