Predicting Popularity of Twitter Accounts
through the Discovery of Link-Propagating
Early Adopters

Daichi Imamori

Keishi Tajima

Kyoto University(CyberZ, inc.)

Kyoto University

BACKGROUND
In social media, such as• New useful users frequently appears.
• We want to detect such new useful users.
• Popularity-based methods, e.g. , HITS andPageRank, do not work well for new users thathave not established their reputa>on yet.

We propose a method of es>ma>ng
prospec>ve popularity of new users.
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

2

OUR APPROACH
We ﬁrst detect early adopters※ Early adopters = The users who are good atﬁnding new good informa>on sources earlier
than others.

• The new users followed by early adopters areprobably good informa>on sources even if they
have few followers at this point.
• We can ﬁnd good informa>on sources bydetec>ng early adopters.
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

3

OUR APPROACH
Informa>on SourceSEA

EAEA

Early Adopters16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

4

DETECTION OF EARLY ADOPTERS
How do we detect early adopters?

SAssump>on

SourceEarly adopters
C imitated
EA’s link toS

The users whose follow links
are imitated by many followers.

C
16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

EA
Early Adopter

Copier5

DETECTION OF EARLY ADOPTERS
How do we detect early adopters?

SAssump>on

SourceEarly adopters
EA

The users whose follow links
are imitated by many followers.
We can detect early adopters
based on the frequency of link
imita>on.
16/10/27

C1

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

C2

C3

Copiers

6

ROADMAP
1. Detect links createdthrough imita>on.

SSource

2. Count number of link
imita>on.
3. Calculate early adopter
score from the number oflink imita>on.

EA

C1

C2

C3

Copiers
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

7ROADMAP
1. Detect links createdthrough imita>on.

S

Source2. Count number of link
imita>on.
3. Calculate early adopter
score from the number oflink imita>on.

EA

C1

C2

C3

Copiers
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

8

ROADMAP
1. Detect links createdthrough imita>on.
2. Count number of link
imita>on.
3. Calculate early adopter
score from the number oflink imita>on.

S

1

C1

Source

2

EA

3

C2

C3

Copiers
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

9ROADMAP
1. Detect links createdthrough imita>on.
2. Count number of link
imita>on.
3. Calculate early adopter
score from the number oflink imita>on.

S

Source
Score

1C12

EA

3C2

C3

Copiers
16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

10

ROADMAP
4. Calculate all users’ early
adopter score.

SourceS

5. Calculate future popularity
score from followers’ early
adopter score.
0.2

16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

0.90.1

11

ROADMAP
4. Calculate all users’ early
adopter score.

Source5. Calculate future popularity
score from followers’ early
adopter score.
0.2

16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early AdoptersS

0.2 + 0.9 + 0.1
= 1.2

0.9

0.1

12

ROADMAP
1. Detect links createdthrough imita>on.

S

Source2. Count number of link
imita>on.
3. Calculate early adopter
score from the number oflink imita>on.

EA

C1C2

C3

Copiers
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

13

ROADMAP
1. Detect links createdthrough imita>on.

SSource

2. Count number of link
imita>on.
3. Calculate early adopter
score from the number oflink imita>on.

EA

C1

C2

C3Copiers
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

14

DETECTION OF LINK IMITATION
We cannot immediately know
imita>on of follow links.

16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

15

DETECTION OF LINK IMITATION
We cannot immediately know
imita>on of follow links.
Structures

triangle
Non-reciprocity

16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

16

DETECTION OF LINK IMITATION
We cannot immediately know
imita>on of follow links.

SSource

Structures

triangle

Early Adopter

Non-reciprocity

EAC
16/10/27

This triangle is atrace that C
Copier imitated EA’s linkto S.

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

17

DETECTION OF LINK IMITATION
We cannot immediately know
imita>on of follow links.

SStructures

triangle

reciprocal
follow links

Non-reciprocity

EAC
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

18

DETECTION OF LINK IMITATION
We cannot immediately know
imita>on of follow links.

S

Structures

triangle

reciprocal
follow links

Non-reciprocity

It is important whether this linkof triangle is reciprocal or nonreciprocal.

16/10/27

C

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

EAFriendshiporfollowback

19

DETECTION OF LINK IMITATION
We cannot immediately know
imita>on of follow links.

SStructures

nonreciprocal
follow links

triangle
Non-reciprocity

C
16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

EA

We only counttriangles where thelink is a nonreciprocal.

20

DETECTION OF LINK IMITATION
We cannot immediately know
imita>on of follow links.

SStructures

nonreciprocal
follow links

triangle
Non-reciprocity

We can detect links createdthrough imita>on

16/10/27

EAC

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

21

WHEN THERE ARE MULTIPLE CANDIDATES
However, in the right ﬁgure, it isdiﬃcult to determine which wasimitated by C, EA1 or EA2

S

EA1

EA2

C
16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

22

WHEN THERE ARE MULTIPLE CANDIDATES
However, in the right ﬁgure, it isdiﬃcult to determine which wasimitated by C, EA1 or EA2

SEach candidates
arebetween
given a users
Scoringby similarity
score equally.

Score
0.5

EA1

Score
0.5

EA2C
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

23

ROADMAP
1. Detect links createdthrough imita>on.
2. Count number of link
imita>on.
3. Calculate early adopter
score from the number oflink imita>on.

S

1

C1

Source

2

EA

3

C2

C3

Copiers
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

24

HOW TO COUNT NUMBER OF IMITATION
Our method process all edges inthe graph one by one.

Each follow link f in a graph

SfC
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

25

HOW TO COUNT NUMBER OF IMITATION
Our method process all edges in
the graph one by one.

Each follow link f in a graph

Sf
Intersec>on of S’s followers andC’s followeesC
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

26

HOW TO COUNT NUMBER OF IMITATION
Our method process all edges inthe graph one by one.

Each follow link f in a graph

SEA2

EA1

These intersec>on users are candidates ofusers whose links to S were imitated by C.

16/10/27

fC

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

27

HOW TO COUNT NUMBER OF IMITATION
Our method process all edges in
the graph one by one.
Accumula>ng the scorefor each candidate

Each follow link f in a graph

S+0.5
EA2

EA1fC
16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

28

HOW TO COUNT NUMBER OF IMITATION
Our method process all edges inthe graph one by one.
Accumula>ng the scorefor each candidate

Each follow link f in a graph

S+0.5
EA2

EA1f

EA1’s accumulated score= 0.5

C
16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

29

HOW TO COUNT NUMBER OF IMITATION
Each follow link f in a graph

Our method process all edges inthe graph one by one.
Accumula>ng the scorefor each candidate

S16/10/27+0.25+0.5
EA2

EA1’s accumulated score= 0.5 + 0.25
= 0.75S’EA1ff’

EA2

EA3EA4CPredic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

30

HOW TO COUNT NUMBER OF IMITATION
Our method process all edges inthe graph one by one.
Ader processing all links in +0.5
the graph, the scores
EA2
accumulated to each user isthe expected number of>mes that user has been
imitated.

Each follow link f in a graph

SS’+0.25

EA1ff’EA2

EA3

EA4

C
16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

31

ROADMAP
1. Detect links createdthrough imita>on.
2. Count number of linkimita>on.
3. Calculate early adopter
score from the number oflink imita>on.

SSource
Score

1C1

2

EA

3

C2

C3Copiers
16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

32

EARLY ADOPTER SCORE
EA’s followees...
Early adopter score=EA

Number of link imita>on|followees| x |followers|...
EA’s followers
16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

33

EARLY ADOPTER SCORE
EA’s followees...
Early adopter score=

Number of link imita>on|followees| x |followers|

This denominator corresponds tothe maximum number of >mes thisuser could be imitated.
16/10/27

EA...
EA’s followers

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

34

EARLY ADOPTER SCORE
EA’s followees...
Early adopter score=

Number of link imita>on|followees| x |followers|This frac>on corresponds to theimita>on ra>o of this user.
16/10/27

EA...
EA’s followers

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

35

EARLY ADOPTER SCORE
2 followees

Early adopter score==
16/10/27

EA

Number of link imita>on|followees| x |followers|2x3=

63 followers

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

36

EARLY ADOPTER SCORE
2 followees

Early adopter score==
16/10/27

EA

Number of link imita>on|followees| x |followers|
22x3=

263 followers

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

37

EARLY ADOPTER SCORE
2 followees

Early adopter score==16/10/27

EA

Number of link imita>on|followees| x |followers|
22x3=

26=

133 followers

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

38

ROADMAP
4. Calculate all users’ earlyadopter score.

SourceS

5. Calculate future popularity
score from followers’ early
adopter score.
0.2

16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

0.9

0.1

39

ROADMAP
4. Calculate all users’ early
adopter score.
5. Calculate future popularity
score from followers’ early
adopter score.

16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

SourceS40

FUTURE POPULARITY SCORE
We call the es>mated new user’s
prospec>ve popularity
future popularity score.

EA
16/10/27

SEA

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

EA41

FUTURE POPULARITY SCORE
We call the es>mated new user’s
prospec>ve popularity
future popularity score

SFuture popularity score iscomputed as sum of early adopter
scores of the new user’s followers.

EA
16/10/27

EA

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

EA42

FUTURE POPULARITY SCORE
We call the es>mated new user’s
prospec>ve popularity
future popularity score

S’s future popularity score= 0.3 + 0.2 + 0.4

S = 0.9Future popularity score iscomputed as sum of early adopter
scores of the new user’s followers.

EA
16/10/27

0.3

EA

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

0.2

EA

0.4

43

OUR EXPERIMENT• Dataset [Li et al., KDD 2012]– A sub-graph of TwiGer crawled in 2011
– About 20,000,000 users– About 300,000,000 follow links• Target users– Tnw : we select then-new users that are• within w weeks ader the crea>on, and• have more than n followers

16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

44

OUR EXPERIMENT• Evalua>on– We rank users in Tnw by our methods andbaselines.
– Ground truth: we rank users by their number ofnon-reciprocal followers as of 2015.
– Compute Spearman’s ρ

16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

45

OUR EXPERIMENT• Baseline methods– FW: Number of followers in May 2011
– PRnr: PageRank scores on the graph consis>ng
only of non-reciprocal links– HITSnr: HITS scores on the graph consis>ng only ofnon-reciprocal links– AD: Adamic-Adar index• Our methods– FPS: Feature popularity score– LR: The linear regression of FPS and somebaselines
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

46

OUR EXPERIMENT
Methoddata size
FWHITSnr
PRnr
AD
FPS
LR

16/10/27

T410
6921

T210
1515

T420
2259

T220
431

T430
979

T230
165

0.18

0.23

0.15

0.07

0.19

0.00

0.26

0.31

0.30

0.35

0.38

0.46

0.16

0.09

0.21

0.20

0.300.32

-0.21

-0.13

-0.30

-0.46

-0.27

-0.50

0.39

0.41

0.39

0.45

0.40

0.47

0.43

0.46

0.43

0.50

0.45

0.58

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

47

OUR EXPERIMENT
MethodT410
T210
data size
6921
1515
0.18
0.23
FW
0.26
0.31
HITSnr
0.16
0.09
PRnr
-0.21
-0.13
AD
0.39
0.41
FPS
0.43
0.46
LR
green: best within baselines

T420
2259

T220
431

T430
979

T230
165

0.15

0.07

0.19

0.00

0.30

0.35

0.38

0.46

0.21

0.20

0.30

0.32

-0.30

-0.46

-0.27

-0.50

0.39

0.45

0.40

0.47

0.43

0.50

0.45

0.58

• HITS works best in most cases.
• AD is the best in some cases.
16/10/27

Predic>ng Popularity of TwiGer Accounts through theDiscovery of Link-Propaga>ng Early Adopters

48

OUR EXPERIMENT
Method
T410
T210
T420
T220
T430
T230
data size
6921
1515
2259
431
979
165
0.18
0.23
0.15
0.07
0.19
0.00
FW
0.26
0.31
0.30
0.35
0.38
0.46
HITSnr
0.16
0.09
0.21
0.20
0.30
0.32
PRnr
-0.21
-0.13
-0.30
-0.46-0.27
-0.50
AD
0.39
0.41
0.39
0.45
0.40
0.47
FPS
0.43
0.46
0.43
0.50
0.45
0.58
LR
• FPS is the best in most cases among all themethods excluding LR• LR is the best for all cases. It means that FPS
red: best
captures some aspects that are notblue: best excluding LR
captured by other methods.

CONCLUSION• We proposed a method of es>ma>ng
prospec>ve popularity of new users.
• Our method es>mate it through the discoveryof early adopters.
• Experiment by using sub-graph of TwiGer.
• Our method outperforms baselines.

16/10/27

Predic>ng Popularity of TwiGer Accounts through the
Discovery of Link-Propaga>ng Early Adopters

50