Social Media Mining: An Introduction

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

2.2 Graph Representation 19

v 1

v 1

v 1

01 0 0 0 0

10 1 1 0 0

01 0 1 0 0

01 1 0 1 1

00 0 1 0 0

00 0 1 0 0

v 2 v 3 v 4 v 5 v 6

v 2

v 3

v 4

v 5

v 6

v 2 v 3

v 6 v 5

v 4

(a)Graph (b)AdjacencyMatrix

Figure 2.4. A Graph and Its Corresponding Adjacency Matrix.

indicates a connection between nodesviandvj, and a 0 denotes no con-

nection between the two nodes. When generalized, any real number can be

used to show the strength of connections between two nodes. The adjacency

matrix gives a natural mathematical representation for graphs. Note that in

social networks, because of the relatively small number of interactions,

many cells remain zero. This creates a largesparsematrix. In numerical

analysis, a sparse matrix is one that is populated primarily with zeros.

In the adjacency matrix, diagonal entries representself-linksorloops.

Adjacency matrices can be commonly formalized as

Ai,j=

{

1ifviis connected tovj,

0 otherwise. (2.10)

Adjacency List

In anadjacency list, every node is linked with a list of all the nodes that are

connected to it. The list is often sorted based on node order or some other

preference. For the graph shown in Figure2.4, the corresponding adjacency

list is shown in Table2.1.

Table 2.1. Adjacency List

Node Connected To

v 1 v 2

v 2 v 1 ,v 3 ,v 4

v 3 v 2 ,v 4

v 4 v 2 ,v 3 ,v 5 ,v 6

v 5 v 4

v 6 v 4