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.1 Graph Basics 15

v 1 v 2 v 3

v 7

v 4 v 5 v 6

v 1 v 2 v 3

v 7

v 4 v 5 v 6

(a)Directed Graph (b)Undirected Graph

Figure 2.2. A Directed Graph and an Undirected Graph. Circles represent nodes, and

lines or arrows connecting nodes are edges.

people, edges indicate inter-node relationships and are therefore known as

relationshipsor(social) ties. The edge set is usually represented usingE, RELATIONSHIPS

AND TIES

E={e 1 ,e 2 ,...,em}, (2.2)

whereei,1≤i≤m, is an edge and the size of the set is commonly shown

asm=|E|. In Figure2.1, lines connecting nodes represent the edges, so

in this case,m=8. Edges are also represented by their endpoints (nodes),

soe(v 1 ,v 2 )(or(v 1 ,v 2 )) defines an edgeebetween nodesv 1 andv 2. Edges

can have directions, meaning one node is connected to another, but not vice

versa. When edges are undirected, nodes are connected both ways. Note that

in Figure2.2(b), edgese(v 1 ,v 2 ) ande(v 2 ,v 1 ) are the same edges, because

there is no direction in how nodes get connected. We call edges in this

graphundirectededges and this kind of graph anundirected graph. Con-

versely, when edges have directions,e(v 1 ,v 2 ) is not the same ase(v 2 ,v 1 ).

Graph2.2(a) is a graph withdirectededges; it is an example of adirected

graph. Directed edges are represented using arrows. In a directed graph,

an edgee(vi,vj) is represented using an arrow that starts atviand ends

atvj. Edges can start and end at the same node; these edges are called

loopsorself-linksand are represented ase(vi,vi). For any nodevi,inan

undirected graph the set of nodes it is connected to via an edge is called its

neighborhoodand is represented asN(vi). In Figure2.1,N(Jade)={Jeff, NEIGHBORHOOD

Juan}. In directed graphs, nodevihas incoming neighborsNin(vi) (nodes

that connect tovi) and outgoing neighborsNout(vi) (nodes thatviconnects

to). In Figure 2.2(a),Nin(v 2 )={v 3 }andNout(v 2 )={v 1 ,v 3 }.

2.1.3 Degree and Degree Distribution

The number of edges connected to one node is thedegreeof that node.

Degree of a nodeviis often denoted usingdi. In the case of directed edges,