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

18 Graph Essentials

Global

U.S.

Fraction

1e–07

1e–05

1e–03

1e–01

550

Degree

1 500 5000

Figure 2.3. Degree Distribution for both the global and U.S. population of Facebook

users (fromUgander et al. [2011]). There exist many users with few friends and a few

users with many friends. This is due to a power-law degree distribution.

Graphs can also have subgraphs. For any graphG(V,E), a graph

G′(V′,E′)isasubgraphofG(V,E), if the following properties hold:

V′⊆V, (2.8)

E′⊆(V′×V′)∩E. (2.9)

2.2 Graph Representation

We have demonstrated the visual representation of graphs. This represen-

tation, although clear to humans, cannot be used effectively by computers

or manipulated using mathematical tools. We therefore seek representa-

tions that can store the node and edge sets in a way that (1) does not lose

information, (2) can be manipulated easily by computers, and (3) can have

mathematical methods applied easily.

Adjacency Matrix

A simple way of representing graphs is to use anadjacency matrix(also

SOCIOMATRIX known as asociomatrix). Figure2.4depicts an example of a graph and

its corresponding adjacency matrix. A value of 1 in the adjacency matrix