Social Media Mining: An Introduction

P1: qVa Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-03 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 16:45

3.1 Centrality 53

v 9

v 8

v 7

v 6

v 5

v 4

v 3

v 2

v 1

Figure 3.1. Degree Centrality Example.

wherenis the number of nodes. We can also normalize by the maximum

degree,

Cdmax(vi)=

di

maxjdj

. (3.6)

Finally, we can normalize by the degree sum,

Cdsum(vi)=

di

∑

jdj

=

di

2 |E|

=

di

2 m

. (3.7)

Example 3.1.Figure3.1shows a sample graph. In this graph, degree

centrality for nodev 1 is Cd(v 1 )=d 1 = 8 , and for all others, it is Cd(vj)=

dj= 1 ,j = 1.

3.1.2 Eigenvector Centrality

In degree centrality, we consider nodes with more connections to be more

important. However, in real-world scenarios, having more friends does

not by itself guarantee that someone is important:having more important

friendsprovides a stronger signal.

Eigenvector centralitytries to generalize degree centrality by incorpo-

rating the importance of the neighbors (or incoming neighbors in directed

graphs). It is defined for both directed and undirected graphs. To keep track

of neighbors, we can use the adjacency matrixAof a graph. Letce(vi)

denote the eigenvector centrality of nodevi. We want the centrality ofvito

be a function of its neighbors’ centralities. We posit that it is proportional