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

20 Graph Essentials

Edge List

Another simple and common approach to storing large graphs is to save all

edges in the graph. This is known as theedge listrepresentation. For the

graph shown in Figure2.4, we have the following edge list representation:

(v 1 ,v 2 )

(v 2 ,v 3 )

(v 2 ,v 4 )

(v 3 ,v 4 )

(v 4 ,v 5 )

(v 4 ,v 6 )

In this representation, each element is an edge and is represented as

(vi,vj), denoting that nodeviis connected to nodevj. Since social media

networks are sparse, both the adjacency list and edge list representations

save significant space. This is because many zeros need to be stored when

using adjacency matrices, but do not need to be stored in an adjacency or

an edge list.

2.3 Types of Graphs

In general, there are many basic types of graphs. In this section we discuss

several basic types of graphs.

Null Graph.A null graph is a graph where the node set is empty (there

are no nodes). Obviously, since there are no nodes, there are also no edges.

Formally,

G(V,E), V=E=∅. (2.11)

Empty Graph.An empty oredgelessgraph is one where the edge set is

empty:

G(V,E), E=∅. (2.12)

Note that the node set can be non-empty. A null graph is an empty graph

but not vice versa.

Directed/Undirected/Mixed Graphs.Graphs that we have discussed thus

far rarely had directed edges. As mentioned, graphs that only have directed

edges are calleddirectedgraphs and ones that only have undirected ones are