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.3 Types of Graphs 21calledundirectedgraphs.Mixedgraphs have both directed and undirected
edges. In directed graphs, we can have two edges betweeniand j(one
fromitojand one from jtoi), whereas in undirected graphs only one
edge can exist. As a result, the adjacency matrix for directed graphs is not
in general symmetric (iconnected to jdoes not mean jis connected to
i, i.e.,Ai,j =Aj,i), whereas the adjacency matrix for undirected graphs is
symmetric (A=AT).
In social media, there are many directed and undirected networks. For
instance, Facebook is an undirected network in which ifJonis a friend
ofMary, thenMaryis also a friend ofJon. Twitter is a directed network,
where follower relationships are not bidirectional. One direction is called
followers, and the other is denoted as following.
Simple Graphs and Multigraphs.In the example graphs that we have
provided thus far, only one edge could exist between any pair of nodes.
These graphs are denoted assimplegraphs.Multigraphsare graphs where
multiple edges between two nodes can exist. The adjacency matrix for
multigraphs can include numbers larger than one, indicating multiple edges
between nodes. Multigraphs are frequently observed in social media where
two individuals can have different interactions with one another. They can be
friends and, at the same time, colleagues, group members, or other relation.
For each one of these relationships, a new edge can be added between the
individuals, creating a multigraph.
Weighted Graphs.A weighted graph is one in which edges are associated
with weights. For example, a graph could represent a map, where nodes
are cities and edges are routes between them. The weight associated with
each edge represents the distance between these cities. Formally, a weighted
graph can be represented asG(V,E,W), whereWrepresents the weights
associated with each edge,|W|=|E|. For an adjacency matrix represen-
tation, instead of 1/0 values, we can use the weight associated with the
edge. This saves space by combiningEandWinto one adjacency matrix
A, assuming that an edge exists betweenviandvjif and only ifWij =0.
Depending on the context, this weight can also be represented bywijor
w(i,j).
An example of a weighted graph is the web graph. A web graph is a
way of representing how internet sites are connected on the web. In general,
a web graph is a directed graph. Nodes represent sites and edge weights
represent number of links between sites. Two sites can have multiple links
pointing to each other, and individual sites can have loops (links pointing
to themselves).