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

52 Network Measures

3.1 Centrality

Centralitydefines how important a node is within a network.

3.1.1 Degree Centrality

In real-world interactions, we often consider people with many connections

to be important. Degree centrality transfers the same idea into a measure.

The degree centrality measure ranks nodes with more connections higher

in terms of centrality. The degree centralityCdfor nodeviin an undirected

graph is

Cd(vi)=di, (3.1)

wherediis the degree (number of adjacent edges) of nodevi. In directed

graphs, we can either use the in-degree, the out-degree, or the combination

as the degree centrality value:

Cd(vi)=diin (prestige), (3.2)

Cd(vi)=diout (gregariousness), (3.3)

Cd(vi)=diin+diout. (3.4)

When using in-degrees, degree centrality measures how popular a node

PROMINENCE is and its value showsprominenceorprestige. When using out-degrees, it

OR

PRESTIGE

measures thegregariousnessof a node. When we combine in-degrees and

out-degrees, we are basically ignoring edge directions. In fact, when edge

directions are removed, Equation3.4is equivalent to Equation3.1, which

measures degree centrality for undirected graphs.

The degree centrality measure does not allow for centrality values to be

compared across networks (e.g., Facebook and Twitter). To overcome this

problem, we can normalize the degree centrality values.

Normalizing Degree Centrality

Simple normalization methods include normalizing by the maximum

possible degree,

Cnormd (vi)=

di

n− 1

, (3.5)