IBM RESEARCH

User Community Reconstruction using
Sampled Microblogging Data
Miki ENOKI, Yohei IKAWA, Raymond RUDY
IBM Research - Tokyo© 2012 IBM Corporation

IBM RESEARCHAt the time of disaster, many people can get real-time
information from social media, while classifying is needed People became not only information receivers, but also senders

propagating information

Flood of messages on Twitter:User

Over 300 million users, over 300 million messages/day© 2012 IBM Corporation 2

IBM RESEARCHAt the time of disaster, many people can get real-time
information from social media, while classifying is needed User community recognition in social media services is important to identify

hot topics or users' interests and concerns in a timely way

User communities on Twitter:User:Reply, RT

Users are interacting with each other© 2012 IBM Corporation 3

IBM RESEARCHAt the time of disaster, many people can get real-time
information from social media, while classifying is needed User community recognition in social media services is important to identify

hot topics or users' interests and concerns in a timely way

User communities on Twitter:User:Reply, RT

Topic:
Accidents at nuclear power
plants

Topic:
Supply shortages atemergency shelters

Topic:
Blackout in theirhomes© 2012 IBM Corporation 4

IBM RESEARCH

Application Scenario 1
Finding Information to Deliver Relief Goods
 Extract user communities on Twitter and find communities ofdisaster victims

 Identify requests for missing items and supply them appropriately

in disaster area

Community of disaster victims
We need many water bottles!!
Koriyama emergency shelterin Fukushima

EV

Get Tweets

Ask up-to-date information

AFSuppliers
Analyze data
• Missing items• Quantity• Location

GB@A When will we get them?

Deliver supplies:user:Reply, RT@A I want medicine, too© 2012 IBM Corporation 5

IBM RESEARCH

Application Scenario 2Finding Closer Relationship Community for Marketing Many companies see microblogging social media services as ideal places todirectly obtain timely opinions from customers and potential customers

 Guan et al.[1] found a tendency for users who purchased a product to often bein the same community in a social-media friendship network[1] Z.Guan, J. Wu, Q. Zhang, A. Singh, and X. Yan: “Assessing andRanking Structural Correlations in Graphs”, SIGMOD2011

Social Media

Canon's announced
an all new DSLR!

Analytics

SONY D80 is great

word-of-mouthrumor, opinion

I want DSLR..

DataStore

Launch an advertising campaign for each customer © 2012 IBM Corporation 6

IBM RESEARCH

We extract a user community by identification of Strongly
Connected Components from user network
1.

Construct user network for community extraction
Build a network whose nodes correspond to twitter users and whoseedges correspond to direct interactions (Replies or RTs) among users
user A

2.

ReplyuserBExtract user community ：Strongly Connected Components


Identify sets of strongly connected nodes

Define the corresponding users of the identified node sets as formingcommunities
 Strongly Connected Component ：Contain a directed path from each node to allof the others in the component
userA

userD
userE

userB

userF

userC
© 2012 IBM Corporation 7

IBM RESEARCH

We often face some difficulties to calculate community withall of the Twitter data
:User:Reply, RTTwitter API
limitation

Much storage space

Public Twitter streaming API
can only collect about 1% ofthe dataEXMLAFVPGKMiss some user connections
and thus divide single usercommunities into pieces!

Over 300 million messages/day

Computational
time
Extremely time-consuming to findnetworks based on numeroustweets© 2012 IBM Corporation 8

IBM RESEARCH

We propose a method for user community
reconstruction using the two type of similarities
between separate communities
Lexical Similarity of the Tweets

× Similarities of Follow Relationships

FollowPEV

We need many water bottles!!
Koriyama emergency shelterin FukushimaMLA

FI need medicine..

XGK

3 days has passed since
we’ve been at Koriyama
emergency shelter!

Similarsamefollowing
keywords
relationships© 2012 IBM Corporation 9

IBM RESEARCH

We propose a method for user community
reconstruction using the two type of similarities
between separate communities
Lexical Similarity of the Tweets

× Similarities of Follow Relationships

Merge two communities to form a larger community
PEVM
LA

FX

GK© 2012 IBM Corporation 10

IBM RESEARCH

Lexical Similarity of the Tweets
 We identify the members of a community from the similarities ofthe keywords and phrases that appear in their tweets

1. Parse the tweets of users within each community andcreate the feature vector (use TF*IDF)
userCommunity 2

Community 1 =(DSLR,Camera, photograph,Lens)

Community 2 =(Sony, DSLR, Travel, Lens)

Community 1

Reconstruction
2. Compute the similarity between their feature vectors andmerge the two communities if the similarity score is above a given threshold(use Cosine
Cosine similarity )© 2012 IBM Corporation 11

IBM RESEARCH

Similarities of Follow Relationships
 We identify the members of a community from the similarities of“Follow” relationships

Compare the lists of followers of the users of a community andmerge communities that share more than a threshold number of users
Follow relationshipCommunity 1

userCommunity 2

2 step distance = high possibility of same community© 2012 IBM Corporation 12

IBM RESEARCH

Lexical Similarity of the Tweets

× Similarities of Follow Relationships

Procedure
1. Compute the lexical similarity of the tweets ofeach community

2. Compute the similarity between the Follow

users of each community

3. Multiply the result of 1. by that of 2.
4. Merge the two communities if the similarity

score (the result of 3.) is above a given
threshold© 2012 IBM Corporation 13

IBM RESEARCH

Experiment© 2012 IBM Corporation 14

IBM RESEARCH

Evaluation Methodology
We merge the divided communities and evaluate the accuracy
Accuracy =# of correctly reconstructed communities# of divided communities

Correct set : The complete
set of all of the communities inour experimental data

# of correctly reconstructedcommunities = 2# of divided communities = 3

MergedApply our method

Randomly delete

50 % of theexperimental data

Merged© 2012 IBM Corporation 15IBM RESEARCH

 Experimental Data We collected twitter data using disaster related keywords (inJapanese) “disaster”, “disaster-affected”, “earthquake”, “nuclearpower”, “buyout”, “brownout”, etc. by using theTwitter API

 Collection period ：2011/03/16 – 2011/04/03(After the Great East Japan Earthquake) # of users ：About 300,000 users

Comparison(1) Using only the lexical similarity of the Tweets(2) Using only the similarities from the Twitter follow relationships(3) Our proposed method© 2012 IBM Corporation 16

IBM RESEARCH

Experimental Result - Community Reconstruction
Result Our proposed method (3) had the highest accuracy while using only

the textual similarities (1) had the lowest

 The rate of false-positives of Follow similarities(2) was quite highAccuracy (%)

Better

100%
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%

False-positiveCorrect

(1)

(2)

(3)
False-positive :Ratio of incorrectly
reconstructed communities(1) Only textualsimilarity(2) Only Follow
similarity(3) Our proposed
methodAccuracy of Community Reconstruction
using 50% Reduced Twitter Data.
© 2012 IBM Corporation 17

IBM RESEARCH

Experimental Result - Community Reconstruction
 We found that using the lexical similarity metrics after selecting

candidate communities for reconstruction by using thesimilarities of the Twitter follow relationships is effective in
avoiding spurious communities

Accuracy (%)

Better

100%
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%

False-positive
Correct

(1)

(2)

(3)
False-positive :Ratio of incorrectly
reconstructed communities(1) Only textual
similarity(2) Only Follow
similarity(3) Our proposed
methodAccuracy of Community Reconstruction
using 50% Reduced Twitter Data.
© 2012 IBM Corporation 18

IBM RESEARCHConclusions
 Proposed a method for user community reconstruction using

the two type of similarities between separate communities

Lexical Similarity of the Tweets

× Similarities of Follow Relationships

 Found that using our method produced the highest accuracy

compared with using only textual similarities or using only thesimilarities of the Twitter follow relationships© 2012 IBM Corporation 19

IBM RESEARCH

Thank you for your attention! !

© 2012 IBM Corporation 20