Social Media Mining: An Introduction

P1: Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-08 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 17:22

8.1 Measuring Assortativity 219

Figure 8.2. A U.S. High School Friendship Network in 1994 between Races. Eighty

percent of the links exist between members of the same race (from [Currarini et al.,

2009 ]).

Consider a network where individuals are friends with people of different

ages. Unlike races, individuals are more likely to be friends with others

close in age, but not necessarily with ones of the exact same age. Hence,

we discuss two techniques: one for nominal attributes and one for ordinal

attributes.

8.1.1 Measuring Assortativity for Nominal Attributes

Consider a scenario where we have nominal attributes assigned to nodes.

As in our example, this attribute could be race or nationality, gender, or

the like. One simple technique to measure assortativity is to consider the

number of edges that are between nodes of the same type. Lett(vi) denote

the type of nodevi. In an undirected graph^2 ,G(V,E), with adjacency

matrixA, this measure can be computed as follows,

1

m

∑

(vi,vj)∈E

δ(t(vi),t(vj))=

1

2 m

∑

ij

Aijδ(t(vi),t(vj)), (8.1)

wheremis the number of edges in the graph,m^1 is applied for normalization,

and the factor^12 is added becauseGis undirected.δ(., .) is the Kronecker

delta function:

δ(x,y)=

{

0 , ifx =y;

1 , ifx=y.

(8.2)