Core univ. program seminar, Aug. 20-21, 2008.
Busan, Korea.

Speculative information discovery
from social bookmarks
Eisuke ITO and Makoto MOMOTA
Research Institute for Information Technology,
Dept.of Informatics,

Kyushu University

itou@cc.kyushu-u.ac.jp

11. Introduction
1. Introduction
2. What do you want?
3. The alpha-bookmarker
method
4. Experiments and Results
5. Conclusion

21. Introduction• Social Bookmark– Online bookmark & bookmark sharing– Tagging web pages• Elements of Social-bookmark– <URI, User, Tag(s), Date>• Good features– Location/machine free
– Refer Tags by others– Classification using tags
– Tag Cloud

URI

2008/07/XX
Ruby
OOPUserTags

Hatena Bookmark (in Japan)• Popular tags
• Trend analysis

3Feature of Social Bookmark• Folksonomy– Folks + Taxonomy– Folks are tagging tocontents• Web: Social Bookmark• Photo• Movie– Contents filtering byfolks• Merits– Low-cost (No expert)– Cover every category• Demerits– Uncertain (not strict)– No Hierarchy (notclassify, not categorize)• User only tags interestcontents.
4

Related works• Provided function– Tag cloudNot Personalized– Search by tags Not clear because tags are uncertain.

• Previous researches– Apply PageRank to gain precision• Yamaie et.al.(2007), Hotho et.al.(2007)– Reduce uncertainness by tag clustering• Rui et al. (2007), Niwa et al• These researches try to reduce demerit.
5

Objectives• We focus on merits of folksonomy– Use merits, and don’t care demerits• Speculative discovery of information from socialbookmarks– Speculative• Recommend brand-new web pages which may become popular– Personalized service• May fit for one’s interests.

– Serendipity6

2. What you want?
1. Introduction
2. What do you want?
3. The alpha-bookmarker
method
4. Experiments and Results
5. Conclusion

7

2. What do you want?
• Search system in library• Social Bookmark system– Well categorized– Well controlled
vocabulary (metadata)– Up-to-date information• Web search engine– Authorized Web pages• Tagging to News/blogs– Filtering by personal
interest– Not categorized• PageRank by Google• HITS algorithm– Correct/Qualified/Accurate pages• Past information

8

What do you want from SBM?
• Speculative Information
discovery– Recommend brand-new
web pages which may
become popular• Personalized service– May fit for one’sinterests.

9Strategy• In each topic field, there are
few leaders and a lot offollowers– Leaders are good trend
watchers of the topic.

• Definition of alphabookmarker– Good trend watchers of thetopic.
– He/She has a lot of follower.

• Early detector of valuable
news.

– Followers catch up later.
• They mentioned those news
later

Find alpha-bookmarker for given topic,
Recommend alpha-bookmarker’s watching web pages.
10

3. The alpha-bookmarker method
1. Introduction
2. What do you want?
3. The alpha-bookmarker
method
4. Experiments and Results
5. Conclusion

11

3. The Alpha-Bookmarker method
Find alpha-bookmarker for given topic,
Recommend alpha-bookmarker’s watching web pages.
• Problems.
– How to extract topics?
– How to find alpha-bookmarker from SBM?
– How to rank pages for recommendation?

12

Outline of the alpha-bookmarker method
Collect massivebookmarks<URI, date, tags, user>

Tag Hierarchization(Topic extraction)

Find alpha-bookmarker
for each topic (tag level)

Recommended pages

Alpha-bookmarkers(few leaders)
Followers

URI (web page)
recommendation
based on ABM.

13

3.1 Tag Hierarchization (1/2)
U(t) : set of URIs (pages) which are tagged t.

U(t)

U(s)

googlegmaps•••

Intersection ratio‘Google’ is more popular than
‘gmaps’.
‘Google’ tagged pages are rarely
tagged ‘gmaps’.
‘gmaps’ tagged pages arefrequently tagged ‘google’.

‘google’ is higher than ‘gmaps’.

Definition|U(t)| > |U(s)| and| U (t )  U ( s ) | a then| U (s) |ts

(We used a=50%.)14

3.1 Tag Hierarchization (2/2)• Lower tags belongs to the higher tag.
• Def.
– TOPIC(t) = { t, {lower tags of t}}• Ex.
– TOPIC(mysql) = { mysql, phpmyadmin, replication, FULLTEXT,LAMP, ERD, XAMPP, activecollab, … }15

3.2 Find alpha-bookmarker (1/2)• Def. of alpha-bookmarker degree for a TOPIC(t).
– t: a tag , u: a user, i: an URI .
– U(t) = URI(TOPIC(t)): Set of URIs which is tagged one of tagt∈TOPIC(t) .
– alpha(u, t). : alpha-bookmarker degree of user u for a TOPIC(t).

alpha (u )   w(i, u ) w(i, u) is weight of a user u for the URI i ,w(i, u) = (# of bookmarked users } – rank(u) .

iU ( t )i an URI (an web page)w(u, i) =85-1=84

user
rank 1 2 3 4 5 6 7 8 985
time

16

3.3 Find alpha-bookmarker (2/2)
alpha(u)   w(i, u)• Early bookmarking and many
follower, then weight
becomes heavy.

iU ( t )i an URI (an web page)

userrank 1 2 3 4 5 6 7 8 985time• Def. of alpha-bookmarkers for a TOPIC(t).
Top Nth users by alpha(u, t) are alpha-bookmarkers
for the TOPIC(t) .
(We used N=10.)17

3.3 URI recommendation based on ABM• Recommend high rank
• Def. : alpharank(i,t), where i is an URI.
alpharank (i, t )  alpha (u, t )ibookmarkedURI

Alpha-bookmarkers

18

4. Experiments and Results
1. Introduction
2. What do you want?
3. The alpha-bookmarker
method4. Experiments and Results
5. Conclusion

19

Experiments and Results• Apply our method to real data (Hatena Bookmark)– Hatena Bookmark is the most popular SBM in Japan– Over 100,000 users• Crawled data
PeriodFeb. 10 2005 –Jul. 17, 2007

# of SBM# of unique Tags
# of unique URI

6,648,994
108,753
350,279# of unique Users

42,75320

Experiments•Separate SBM data into 2 parts
Base data

2005/2/10•

time
Test data
2007/1/1
2007/7/17

Assumption– If alpha-bookmarker’s bookmarked pages are also bookmarked by follower.

•Definition of success– If recommended URI (from base data, before period) is bookmarked by someone at later
period, then that is success.

•Test data
– Tags: Top 20 TF(term frequency) tags
– Users: Random sampling from users who tagged related tags.

•

Compare 4 methods––––

Alpha-bookmarker
Topic co-occurrence
Cosine similarity
Random21

Results
Random Sampling 1,000 uses , 100 times, and calculate average
45%
16% .. 42%

y: success rate (%)

y: success ratio =Total users# of followers•Alpha-bookmarker

14% .. 36%

Topic-cooccurecos similarity

random4% .. 15%0% .. 2%

x: # of recommendation pages (10 .. 100)

•Results– Alpha-bookmark method is most useful5. Conclusion
1. Introduction
2. What do you want?
3. The alpha-bookmarker
method
4. Experiments and Results
5. Conclusion

Search ‘Alpha Bookmarker’23

6. Conclusion• Summary– Speculative information discovery from social bookmarks.
– We developed Alpha-Bookmarker method.
– Apply the method to Hatena bookmark data.
• Hatena bookmark is the most popular SBM in Japan.

• Future works– Check adaptability for long period SBM data
– Apply to other folksonomy system• del.icio.us (SBM), Flicker(photo), …

24