A Centrality for Social Media Users
Focusing on Information-Gathering Ability

Mamoru Yamakawa, Keishi Tajima
Kyoto University

1Introduction• Most existing SNS user scoring methods
use the individual's social influence.
• However, users with a high ability tocollect useful information quickly arealso important in SNS.

Can we devise a scoring methodthat uses information-gathering
ability on Twitter?
2

Related work (1)Katz Centrality [Katz 1953]

𝑖Information flow

follow𝑗• 0 < 𝛼 < 1/|𝜆max |• 𝜆max is the eigenvalue of 𝐴 with the largest absolute value

𝐶Katz 𝑖 gives the sum of the information flowing into i3

Related work (1)Katz Centrality [Katz 1953]• 0 < 𝛼 < 1/|𝜆max |• 𝜆max is the eigenvalue of 𝐴 with the largest absolute value

Shortcomings:• Weights of information transmitted by each node are equal.
• Parent node propagates information to all child nodes withprobability 1.

4

Related work (2)HITS algorithm [Kleinberg 1999]

Shortcomings:• Hub score is based only on the authority score of direct neighbors.
→ No consideration is given to information dissemination throughretweets.
5

Proposed Method• Node 𝑖 has a weight 𝑤𝑖 representing the quality of information• Node 𝑖 forwards Information from the parent node in 𝑃𝑅𝑇 𝑖• 𝛼: attenuation rate makes the quality ofinformation smaller for those originatingfrom more distant nodes.

𝑃𝑅𝑇 (1)

𝑤2

𝑤1

𝑃𝑅𝑇 (0)𝑤0

6

Proposed Method
𝑃RT (𝑖): information forwarding probability of 𝑖
𝑃RT (𝑝): information propagating probability through path 𝑝• we calculate the probability that information posted by 𝑢1 reaches
𝑢𝑙 through a (𝑙 − 1)-hop path 𝑝 = 𝑢1 , 𝑢2 , . . . , 𝑢𝑙 , denoted by 𝑃RT (𝑝),by the formula below :

𝑢1
post

𝑢2

𝑢3

𝑢𝑙−1𝑢𝑙reach7

Probability of Multi-hop Propagation
Adjacency matrix weighted by user retweet probability 𝑃𝑅𝑇 :• 𝑃𝑖𝑗 = 𝐴𝑖𝑗 ⋅ 𝑃𝑅𝑇 (𝑖)•(𝑃𝑙 )𝑖𝑗
𝑃RT 𝑖= σ𝑝 𝑃RT (𝑝)• 𝑝 is 𝑙-hop paths from 𝑖 to 𝑗
8

Information-Gathering Ability Including
Self-Originated Information
We first define the metric including self-originated information,
denoted by 𝐼𝐺𝐶+ (𝑖) (Information-Gathering Centrality including
self-originated information), as follows:

𝐼𝐺𝐶+ gives sum of the information flowing into 𝑖 through retweets

9Information-Gathering Ability Including
Self-Originated Information
We first define the metric including self-originated information,
denoted by 𝐼𝐺𝐶+ (𝑖) (Information-Gathering Centrality including
self-originated information), as follows:• There are many ways to define the value of 𝑤𝑖• PageRank• Topic-sensitive PageRank• etc.

10

Information-Gathering Ability Including
Self-Originated Information
If 𝛼 satisfies the condition, We can simplify the computation of
𝐼𝐺𝐶+ = 𝐼𝐺𝐶+ 1 , … , 𝐼𝐺𝐶+ (𝑛) T using the inverse matrix:• 𝑤𝑝 𝑗 = 𝑤𝑗 /𝑃RT (𝑗)• 𝑤𝑝 = 𝑤𝑝 1 , … , 𝑤𝑝 𝑛𝑇

11

Elimination of Self-Originated Information• 𝐼𝐺𝐶+ (𝑖) includes information originating 𝑖 itself.
• 𝐼𝐺𝐶self (𝑖): the amount of information originating 𝑖 and recievedby 𝑖.
• 𝐼𝐺𝐶(𝑖) : our proposed metric

12

Elimination of Self-Originated Information
As in 𝐼𝐺𝐶+ , We can efficiently the compute 𝐼𝐺𝐶 using inverse
matrix and Hadamard product:• ⊗ is Hadamard product• 𝐴 ⊗ 𝐵 = (𝑎𝑖𝑗 𝑏𝑖𝑗 ).

13

Metric for Users Retweeting UsefulInformation
𝐼𝐺𝐶𝑟𝑡 : Another metric based on the amount information that
• 𝑖 collects and• Forward to its followerd

14

Experiment
To compare the proposed metric with several existing metrics, weconducted experiments on two datasets collected from Twitter.
• The node dataset consist of seed user, and their followers andfollowees.
• The edge of dataset is the existing follow-relation between node pairs
in dataset.
followers

seed user
15

Experiment
To compare the proposed metric with several existing metrics, weconducted experiments on two datasets collected from Twitter.
• To estimate 𝑃𝑅𝑇 𝑖 , we collected the total number of tweets so far andthe 100 most recent tweets for each account.
• In addition, collected the number of followers and following
relationships for each account.
followers

seed user16

Experiment
We compared the node ranking by our 𝐼𝐺𝐶 and 𝐼𝐺𝐶𝑟𝑡 with theranking by the following existing metrics:
••
•
•
•
•
•
•

𝑃RT
In-degree (𝑑 − )Out-degree (𝑑 + )𝐼𝐺𝐶 (𝑤𝑖 : PR)
𝐼𝐺𝐶𝑟𝑡 (𝑤𝑖 : PR)
Katz Centrality(Katz)
Hub score(Hub)PageRank(PR)17Experiment 1
𝐼𝐺𝐶 has strong positive correlation with Katz, but their correlation issmaller than the correlation between 𝐼𝐺𝐶 and the hub score.
• Node weight 𝑤𝑗 and retweet probability 𝑃RT certainly makes 𝐼𝐺𝐶
different from Katz.

18

Experiment 2
To compare the ranking by the hub score and the ranking by 𝐼𝐺𝐶 in
more details, we show their top 10 users in Dataset 1.
In addition to the metrics from Experiment 1, we use the f. PR• the average PageRank values of the followees of the user

19

Experiment 2
The users with the highest hub scores have high out-degreevalues (𝑑 + ) , and high values in the column f. PR.

20

Experiment 2
By contrast, the users with the highest IGC scores do notnecessarily have high values for 𝑑 + and f.PR.

21

Conclusion• We proposed a new centrality metric for social media users,
focusing on information-gathering ability of users.
•assigning different importance weight and different forwarding
probability to each node.

• We show that we can compute our metrics efficiently.
• We compared the rankings generated by our metrics and theexisting metrics on two social graphs obtained from Twitter.
• The result shows that the rankings by our metrics do notcoincide with the rankings by existing metrics.
22

Future work
𝐼𝐺𝐶 in reversed edge graph• 𝐼𝐺𝐶 is expected to measure information distributing ability
through multi-hop information propagation• The comparison of 𝐼𝐺𝐶 and PageRank would be an interesting23