143 Twitter Twitter Twitter Twitter Twitter Java 8) Weng 16) 1 PageRank 15) Twitter 72.4% 80% 16) 1 1 Twitter Boyd 5) 6),11),12),18) 6),11),18) 17) Tw

Size: px

Start display at page:

Download "143 Twitter Twitter Twitter Twitter Twitter Java 8) Weng 16) 1 PageRank 15) Twitter 72.4% 80% 16) 1 1 Twitter Boyd 5) 6),11),12),18) 6),11),18) 17) Tw"

さなえこいたばし
5 years ago
Views:

1 Vol. 4 No (July 2011) Twitter 1 1, 2 1, 1 1, 2 and so on. Useful information spreads among users widely by Retweet which is a functionality of Twitter to cite other user s message. For this reason, users whose messages are frequently Retweeted are considered to be useful. However, conventional approaches only deal with social graphs consisting of relationships among users, and do not consider Retweet. In this paper, we introduce the User-Tweet Graph which incorporates information spread by Retweet into the social graph. Using such a graph, we also propose a user evaluation method called TURank. TURank analyzes the User-Tweet Graph using the concept of ObjectRank, which is a link analysis method extending PageRank. Experimental results show the effectiveness of the proposed approach. Twitter Twitter Twitter Twitter User-Tweet Graph PageRank ObjectRank TURank Ranking Twitter Users Based on Information Propagation Graph Analysis Yuto Yamaguchi, 1 Toshiyuki Amagasa, 1, 2 Tsubasa Takahashi 1, 1 and Hiroyuki Kitagawa 1, 2 Recently, a micro-blogging service called Twitter has grown popular. It attracts a lot of attentions as a new type of information source, because diverse information is transmitted in real-time. There are a huge variety of Twitter users, and they transmit information based on their interests or preferences. Some users transmit a lot of useful information and have a great influence on other users. Therefore, identifying such users is considered a major research issue, because it is needed to identify useful information, to conduct marketing, 1. SNS Social Networking Service Web SNS SNS Twitter 1) Twitter Twitter Twitter 1 Graduate School of Systems and Information Engineering, University of Tsukuba 2 Center for Computational Sciences, University of Tsukuba 1 Presently with Service Platforms Research Laboratories, NEC Corporation 142 c 2011 Information Processing Society of Japan

2 143 Twitter Twitter Twitter Twitter Twitter Java 8) Weng 16) 1 PageRank 15) Twitter 72.4% 80% 16) 1 1 Twitter Boyd 5) 6),11),12),18) 6),11),18) 17) Twitter TURank Twitter User Rank TURank User-Tweet Graph User-Tweet Graph User-Tweet Graph PageRank ObjectRank 4) 2 Twitter Twitter Twitter Twitter 1)

3 144 Twitter ,500 14) Twitter Twitter Twitter Twitter 140 URL Twitter Twitter 1 SNS Twitter 1 Twitter 2 Twitter Twitter Kwak 11) PageRank PageRank ObjectRank PageRank PageRank 15) Web PageRank Web PageRank Web Web PageRank Web Web G =(V,E) V = {v 1,,v n} Web E v i d 1 d

145 Twitter 1 v i v i r i r =[r 1,,r n] T r = dar + (1 d) u (1) V A n v j v i (v j,v i) a ij = 1/OutDeg(v j) 0 OutDeg(v j) v j u =[1,, 1] T 1 2

Schema Graph Authority Transfer Data Graph 2 Authority Transfer Data Graph Authority Transfer Data Graph V E 1 v i v j e ij E w(e ij) w(e ij) = w(e S) OutDeg(v i,e S) e S e ij OutDeg(v

4 145 Twitter 1 v i v i r i r =[r 1,,r n] T r = dar + (1 d) u (1) V A n v j v i (v j,v i) a ij = 1/OutDeg(v j) 0 OutDeg(v j) v j u =[1,, 1] T ObjectRank ObjectRank 4) PageRank PageRank ObjectRank Authority Transfer Schema Graph 1 Authority Transfer Schema Graph Authority Transfer Schema Graph 2 1 Authority Transfer Schema Graph Authority Transfer Data Graph 2 Authority Transfer Data Graph Authority Transfer Data Graph V E 1 v i v j e ij E w(e ij) w(e ij) = w(e S) OutDeg(v i,e S) e S e ij OutDeg(v i,e S) v i e S Authority Transfer Data Graph PageRank (1) ObjectRank A a ij v j v i (2) 1 Authority Transfer Schema Graph 2 Authority Transfer Data Graph Fig. 1 Authority Transfer Schema Graph. Fig. 2 Authority Transfer Data Graph.

5 146 Twitter e ji w(e ji) 0 3. User-Tweet Graph TURank User-Tweet Graph 4 (1) (2) (3) (4) 4 PageRank User-Tweet Graph PageRank ObjectRank Twitter 1 1 Twitter Twitter TURank (1) User-Tweet Schema Graph ( 2 ) User-Tweet Schema Graph User- Tweet Graph (3) User-Tweet Graph (4) 3.1 User-Tweet Schema Graph 3.2 User-Tweet Graph User-Tweet Schema Graph User-Tweet Graph User-Tweet Schema Graph 1 3 User-Tweet Schema Graph User-Tweet Schema Graph UTG S UTG S =(V S,E S,α) (3) V S = {vuser,v S tweet} S (4) E S = {e S follow,e S followed,e S post,e S posted,e S RT,e S RT ed} (5) α : E S [0, 1] (6) V S user vuser S tweet vtweet S E S follow e S follow followed e S followed post e S post posted e S posted RT e S RT RTed e S RT ed follow u u post u u RT t t followed posted RTed follow post RT 1 User-Tweet Schema Graph ObjectRank Authority Transfer Schema Graph

8 post tweet v S V S 1 α(e S ) 1 (7) e S OutEdges(v S ) OutEdges(v S ) v S 1 3.3 3.2 User-Tweet Graph User-Tweet Schema Graph 4 User-Tweet Graph

6 147 Twitter 3 Fig. 3 User-Tweet Schema Graph User-Tweet Schema Graph. E S V S V S Σ Σ e S follow (vuser,v S user, S follow) α E S [0, 1] user 2 follow 8 post followed 0 followed PageRank user 0.2 follow user 0.8 post tweet v S V S 1 α(e S ) 1 (7) e S OutEdges(v S ) OutEdges(v S ) v S User-Tweet Graph User-Tweet Schema Graph 4 User-Tweet Graph Fig. 4 User-Tweet Graph. User-Tweet Graph 1 4 User-Tweet Graph User-Tweet Graph UTG UTG =(V,E,λ,μ,β) (8) E V V (9) λ : V V S (10) μ : E E S (11) β : E [0, 1] (12) V User-Tweet Graph v V λ v V S user tweet λ(v) E User-Tweet Graph e E μ e E S follow/followed post/posted RT/RTed μ(e) β E [0, 1] β(e ij) = α(μ(e ij)) OutDeg(v i,μ(e ij)) 1 User-Tweet Graph ObjectRank Authority Transfer Data Graph (13)

7 148 Twitter e ij E v i v j OutDeg(v i,μ(e ij)) v i μ(e ij) 4 0 Ω={user, tweet} Ψ={follow, followed, post, posted, RT, RT ed} V E λ μ V = V ω (14) E = ω Ω E ψ (15) ψ Ψ ω Ω, V ω = {v V λ(v) =vω} S (16) ψ Ψ, E ψ = {e E μ(e) =e S ψ} (17) V V ω E E ψ V ω E ψ (16) (17) User-Tweet Graph Twitter user follow PageRank 1 tweet RT User-Tweet Graph user tweet user tweet tweet user User-Tweet Graph RT tweet posted follow user post User-Tweet Graph User-Tweet Graph 4 t 1 t 2 t 2 t 3 t 1 t 2 t 3 t 2 t 3 User-Tweet Graph 1 Web 3.3 User-Tweet Graph ψ Ψ A ψ A follow A followed V user V user A post V user V tweet A posted V tweet V user A RT A RT ed V tweet V tweet A ψ A ψ ij { A ψ ij = β(e ji) e ji E ψ (18) 0 e ji / E ψ e ji E ψ A ψ ij β(eji) 0 A ψ k 0 OutDeg(v k,e S ψ)=0 k α(e S ψ)/n N A ψ 1 A ψ α(e S ψ) A ψ A [ ] [ ] A follow O A followed A posted A = + (19) A post A RT RT ed O A O 0 A ψ A V vuser v S tweet S 1 A 1 A vuser S α(e S follow) =0.4 α(e S followed) =0 α(e S post) =0.5 A 1 V user 0.9 A L L =(E D) (20) D ii = A ij (21) i

8 149 Twitter E D (21) L 1 A L L V user L Vuser V tweet L Vtweet (22) 1 A A N (23) [ ] L Vuser O L = O L Vtweet A N = [ A + L ] A follow + A followed + L Vuser A posted = A posted A RT + A RT ed + L Vtweet 3.4 PageRank (1) TURank (1) r V user r u V tweet r w [r u,r w ] T A 3.3 A N [ ] [ ][ ] [ ] r u A f L A posted r u (1 d) u u = d + (24) V r w A post A R L A f L = Afollow + A followed + L Vuser A R L = A RT + A RT ed + L Vtweet r w u u 1 V user u w 1 V tweet (24) TURank (25) r u = d(a f L ru + A posted r w )+ r w = d(a post r u + A R Lr w )+ (1 d) u u V u w (22) (23) (25) (1 d) u w V TURank r0 u [1/ V user,, 1/ V user ] r w 0 [1/ V tweet,, 1/ V tweet ] p 0 Repeat p p +1 foreach rp,i u rp u rp,i u dβ(e e ji E follow E followed ji)rp 1,j+ u dβ(e e ji E posted ji)rp 1,j w +dl iirp 1,i u +(1 d) / V end foreach rp,i w rp w rp,i w dβ(e e ji E RT E RT ed ji)rp 1,j w + e ji E post dβ(e ji)rp 1,j u +dl iirp 1,i w +(1 d) / V end until rp u rp 1 u 1 <ɛ rp w rp 1 w 1 <ɛ return rp u end 5 TURank Fig. 5 TURank algorithm. TURank r u 2 TURank r u 5 p user i rp,i u 1 i follow followed user j p 1 dβ(e ji)rp 1,j u 2 i posted tweet j p 1 dβ(e ji)rp 1,j w 3 p 1 dl iirp 1,i u 4 (1 d)/ V 1 3 d tweet user 1 L 2 TURank r w

150 Twitter ɛ TURank r u 4. 4.1 4.2 4.3 4.4 4.

9 150 Twitter ɛ TURank r u Twitter API 2) D =(T,U,F,P,R) T U T 1 F follow U follow P post u U u t T R RT t 1 T t 1 t 2 T ( 1 ) Twitter Search API 3) RT T U post P 1 (2) t T T U post P RT R ( 3 ) Twitter API followers/ids u U U follow F Twitter API (2) RT t T 1 Twitter Search API 6 Fig. 6 Cost matrix of Levenshtein distance. 100 Twitter API statuses/user timeline t 13) t t 2 6 apple play

10 151 Twitter 1 Table 1 Dataset details. size # of tweet nodes T 605,968 #ofusernodes U 112,035 #ofpostedges P 605,968 #ofrtedges R 369,383 # of follow edges F 14,631,014 2 TURank weights Table 2 TURank weights. follow followed post posted RT RTed TURank TURank TURank TURank ( 1 ) pple a (2) ple p (3) pla e a (4) play y apple play 5 RT 1 Twitter D 1 PageRank Google 2 PageRank MapReduce 11) Web 4.2 Twitter User-Tweet Schema Graph 2 4 User-Tweet Schema Graph TURank1 TURank3 RT follow TURank4 RTed 0 followed 0 RT/RTed follow/followed post/posted RT/RTed follow/followed 1 post/posted PageRank HITS 9) FollowNum RTNum FollowRT PageRank HITS FollowNum RTNum FollowRT 0.5

11 152 Twitter k NDCG NDCG (u 1,u 2,,u 25) (26) NDCG = DCG (26) IDCG 25 score(u i) DCG = score(u 1)+ (27) log 2 i i=2 score(u i) u i IDCG DCG IDCG score(u) DCG NDCG score(u) Fig. 7 Fig. 8 7 Precision of proposed methods using varied weights. 8 TURank Precision of the proposed method and existing methods. 3 Table 3 NDCG NDCG of all methods. NDCG TURank TURank TURank TURank PageRank HITS FollowNum RTNum FollowRT 0.820

12 153 Twitter u NDCG TURank1 1 RT follow TURank2 TURank3 follow RT TURank2 TURank3 TURank2 TURank3 TURank1 RTed 0 TURank4 NDCG RTed yumemitter 1 soysoucebot TURank4 Twitter 2 Twitter 1 RT follow Twitter RT RT follow Twitter RTed 0 RTed 0 TURank1 TURank1 follow RT 1:1 FollowRT TURank PageRank HITS yahoo shopping shuumai RTNum nelson koenji

13 154 Twitter 4 TURank1 Table 4 Ranking by TURank1. 5 PageRank Table 5 Ranking by PageRank. 6 HITS Table 6 Ranking by HITS. 7 FollowNum Table 7 Ranking by FollowNum. 8 RTNum Table 8 Ranking by RTNum. 9 FollowRT Table 9 Ranking by FollowRT. 1 masason 2 555hamako 3 takapon jp 4 kazuyo k 5 astro soichi 6 hikaruijuin 7 mainichijpedit 8 shuzo matsuoka 9 asahi 10 kohmi 11 meigenbot 12 shakase 13 tsuda 14 kharaguchi 15 jaxa jp 16 hmikitani 17 nhk pr 18 shiro tsubuyaki 19 47news 20 renho sha 21 seikoito 22 hazuma 23 skmt09 24 taguchi 25 samfurukawa 1 masason 2 555hamako 3 takapon jp 4 kazuyo k 5 jaxa jp 6 comic natalie 7 astro soichi 8 owarai natalie 9 hikaruijuin 10 mainichijpedit 11 hmikitani 12 kohmi 13 47news 14 kharaguchi 15 asahi 16 toriaezu 17 tsuda pr 18 47newsflush 19 seikoito 20 shakase 21 skmt09 22 shiro tsubuyaki 23 renho sha 24 shuzo matsuoka 25 room66plus 1 masason 2 takapon jp 3 kazuyo k 4 555hamako 5 tsuda 6 kohmi 7 inadatomoyuki 8 note man 9 bonbokorin 10 mainichijpedit 11 q2e2d2 12 hmikitani 13 hikaruijuin 14 astro soichi 15 asahi 16 renho sha 17 sentan 18 ohanika 19 kharaguchi 20 taguchi 21 sasakitoshinao 22 shuzo matsuoka 23 omowaku 24 makeplex 25 nobi 1 mooris 2 gachapinblog 3 tenkijp 4 takapon jp 5 asahi 6 mainichijpedit 7 twj 8 kazuyo k 9 yahoo shopping 10 taguchi 11 kotoripiyopiyo 12 kohmi 13 suadd 14 kengo 15 kogure 16 nobi 17 abfly 18 msugaya 19 fshin tokuriki 21 matsuyou 22 taromatsumura 23 ryotheskywalker 24 natalie mu 25 rkmt 1 hazuma 2 meigenbot 3 shuzo matsuoka 4 meinichijpedit 5 iwakamiyasumi 6 47news 7 itmedia news 8 shuumai 9 nelson koenji 10 hikaruijuin 11 nhk pr 12 hokayan 13 kotoba bot 14 kazuyo k 15 idanbo 16 samfutukawa 17 masason 18 shakase 19 eguchinn 20 kenjieno 21 akhk 22 astro soichi 23 knnkanda 24 gotch akg 25 katokichicoltd 1 mainichijpedit 2 hazuma 3 meigenbot 4 kazuyo k 5 shuzo matsuoka 6 asahi 7 mooris 8 natalie mu 9 takapon jp 10 iwakamiyasumi 11 hikaruijuin 12 47news 13 itmedia news 14 kogure 15 nobi 16 shuumai 17 gachapinblog 18 nelson koenji 19 taguchi 20 abfly 21 nhk pr 22 hokayan 23 kotoba bot 24 kohmi 25 masason matsuyou suadd 2 RTNum hazuma kenjieno RTNum ryotheskywalker eguchinn

14 155 Twitter FollowRT FollowNum RTNum FollowRT 3 nhk pr meigenbot mainichijpedit asahi astro soichi PageRank HITS HITS PageRank HITS Twitter HITS takapon jp kazuyo k masason meigenbot kotoba bot samfurukawa akhk Kwak 11) 2 5. Twitter Java 8) 3 Huberman 7) Krishnamurthy 10) Boyd 5) Ye 18) Kwak 11) 1 Twitter Weng 16) PageRank TwitterRank TURank TwitterRank 1 User-Tweet Graph 1 TwitterRank Leavitt 12) Cha 6) 6. Twitter User-Tweet Graph

156 Twitter User-Tweet Graph tweet user #21013004 1) Twitter. http://twitter.com 2) Twitter API. http://apiwiki.twitter.com/twitter-api-documentation 3) Twitter Search API. http://apiwiki.twitter.com/w/page/22554756/ Twitter-Search-API-Method:-search 4) Balmin, A.

15 156 Twitter User-Tweet Graph tweet user # ) Twitter. 2) Twitter API. 3) Twitter Search API. Twitter-Search-API-Method:-search 4) Balmin, A., Hristidis, V. and Papakonstantinou, Y.: ObjectRank: Authority-Based Keyword Search in Databases, VLDB (2004). 5) Boyd, D., Golder, S. and Lotan, G.: Tweet, Tweet, Retweet: Conversational Aspects of Retweeting on Twitter, Hawaii International Conference on System Sciences, Vol.0, pp.1 10 (2010). 6) Cha, M., Haddadi, H., Benevenuto, F. and Gummadi, K.P.: Measuring user influence in Twitter: The million follower fallacy, ICWSM 2010: Proc. International AAAI Conference on Weblogs and Social Media (2010). 7) Huberman, B.A., Romero, D.M. and Wu, F.: Social networks that matter: Twitter under the microscope, 1st Monday, Vol.14, No.1 (Jan. 2009). 8) Java, A., Song, X., Finn, T. and Tseng, B.: Why We Twitter: Understanding microblogging usage and communities, Joint 9th WEBKDD and 1st SNA-KDD Workshop, San Jose, CA (2007). 9) Kleinberg, J.: Authoritative Sources in a Hyperlinked Environment, Proc. 9th ACM SIAM Symposium on Discrete Algorithms (SODA 98 ), pp (1998). 10) Krishnamurthy, B., Gill, P. and Arlitt, M.: A few chirps about twitter, Proc. 1st Workshop on Online Social Networks, ACM (2008). 11) Kwak, H., Lee, C., Park, H. and Moon, S.: What is Twitter, a social network or a news media?, World Wide Web Conference (2010). 12) Leavitt, A., Burchard, E., Fisher, D. and Gilbert, S.: The influentials: New approaches for analyzing influence on twitter, A publication of the Web Ecology Project (2009). 13) Levenshtein, I.V.: Binary Codes capable of correcting deletions, insertions, and reversals, Cybernetics and Control Theory, Vol.10, No.8, pp (1966). 14) Moore, R.J.: New data on Twitter s users and engagement (2010). new-data-on-twitters-users-and-engagement/ 15) Page, L., Brin, S., Motwani, R. and Winograd, T.: The PageRank Citation Ranking: Bringing Order to the Web, Technical Report , Stanford InfoLab. (1999). 16) Weng, J., Lim, E., Jiang, J. and He, Q.: TwitterRank: Finding Topic-sensitive Influential Twitterers, WSDM (2010). 17) Yamaguchi, Y., Takahashi, T., Amagasa, T. and Kitagawa, H.: TURank: Twitter User Ranking Based on User-Tweet Graph Analysis, WISE, pp (2010). 18) Ye, S. and Wu, S.F.: Measuring Message Propagation and Social Influence on Twitter.com, SocInfo 2010 (2010). ( ) ( ) 2010

16 157 Twitter XML e ACM IEEE Computer Society XML WWW The Unnormalized Relational Data Model Springer-Verlag ACM IEEE-CS

DEIM Forum 2015 F8-4 Twitter Twitter 1. SNS

DEIM Forum 2015 F8-4 Twitter Twitter 1. SNS DEIM Forum 2015 F8-4 Twitter 432 8011 3-5-1 432 8011 3-5-1 E-mail: cs11032@s.inf.shizuoka.ac.jp, {yokoyama,fyamada}@inf.shizuoka.ac.jp Twitter 1. SNS SNS SNS Twitter 1 Twitter SNS facebook 2 mixi 3 Twitter