Page 324 - Becoming Metric Wise

317
Networks

10.1.3 Types of Networks: Directed or not; Weighted
(Valued) or not

Directed and Undirected Networks
Alink e is an ordered pair (i,j) representing a link from node i to node j.
Node i is called the initial node of link e, while node j is called its terminal
node. If a link has no direction we say that this network is undirected. A
coauthorship network is an example of an undirected graph if author A
coauthored an article with author B, automatically author B coauthored an
article with A. An undirected graph can be represented by a symmetric
matrix M5 (m ij ), where m ij 5 m ji is equal to 1 if there is an edge between
nodes i and j,and m ij is zero otherwise. Two-dimensional representations of
directed networks often have arrows on the links, pointing from the initial
to the terminal node.

Weighted and Unweighted Networks
1
In a weighted or valued network a weight function w: E-R (the posi-
0
tive real numbers, except zero) is given. In a so-called unweighted graph
all edges have weight one. Two types of weights can be distinguished:
those expressing a similarity or proximity, such as the number of times A
addresses B in an observation study in a friendship network, and those
expressing a dissimilarity or distance such as time to travel (by car or train)
from point P to point Q in a route map. In the adjacency matrix of a
weighted network the weight of edge e 5 (i,j) is placed in cell (i,j).
Bringing these considerations together we see that there exist four
types of networks. They result from a double binary classification:
directed or not and weighted (or valued) or not. Table 10.1 provides
some informetric examples.
Each weighted network can be considered an unweighted one by set-
ting all weights equal to 1. Similarly each directed network can be consid-
ered an undirected one by ignoring directions. This network is called the
underlying undirected network.
A path in a network from sAV to tAV is a sequence alternating
between vertices and edges, starting with s, ending with t such that each
edge connects a vertex in the sequence to the succeeding one. The length
of a path is the sum of the weights of its edges. In an unweighted graph
the length is simply the number of edges. The length of a shortest path
(or geodesic) between vertices s and t is called the distance between s and
t, denoted d G (s,t) (Brandes, 2001). In particular, d G (s,s) is set equal to 0
for each sAV and if there is no path from s to t we say that their distance