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

68 Network Measures

v 1

v 2

v 3

Figure 3.11. A Graph with Reciprocal Edges.

3.2.2 Reciprocity

Reciprocity is a simplified version of transitivity, because it considers closed

loops of length 2, which can only happen in directed graphs. Formally, if

nodevis connected to nodeu,uby connecting tovexhibits reciprocity. On

microblogging site Tumblr, for example, these nodes are known as “mutual

followers.” Informally, reciprocity is

If you become my friend, I’ll be yours.

Figure3.11shows an example where two nodes (v 1 andv 2 ) in the graph

demonstrate reciprocal behavior.

Reciprocity counts the number of reciprocal pairs in the graph. Any

directed graph can have a maximum of|E|/2 pairs. This happens when all

edges are reciprocal. Thus, this value can be used as a normalization factor.

Reciprocity can be computed using the adjacency matrixA:

R=

∑

i,j,i<jAi,jAj,i

|E|/ 2

,

=

2

|E|

∑

i,j,i<j

Ai,jAj,i,

=

2

|E|

×

1

2

Tr(A^2 ),

=

1

|E|

Tr(A^2 ),

=

1

m

Tr(A^2 ), (3.53)