Information Technology Reference
In-Depth Information
Fig. 3.3
Example of directed graph
these graphs, the edges are directed from an initial node to a final node. This
modeling helps to represent asymmetric relationships in sociology (“I appreciate
sb's company”) and to consider the direction of a section of an infrastructure
network (cf. Fig. 3.3 ). In this representation, the two-way sections have to be
modeled by two edges opposite from each other.
Taking the possible impact of edge direction into account affects the meaning
of the relationships between nodes. In this connection, edge directions may be
integrated in several ways depending on the context of the study:
￿
a tie between two nodes x and y may be considered valid if either both edges
x
y and y
x exist or if at least one of these edges exists;
￿
a connection between two nodes x and y may be assessed through both the
shortest paths x
x or through the shortest path computed on the
graph without taking edge direction into account.
In practice, the interpretation of edge direction depends on the type of network
under study and on the meaning of the relationship between two nodes within a
network. For example, within the context of risk, it is relevant to allow for two-way
circulation on one-way sections because it may provide relief. This reasoning cannot
be extended to air transport networks in which directed edges correspond to flights
from one airport to another: for such graphs it is essential to take edge direction into
account for path computation.
Graph theory is also a useful way to improve network modeling by taking the
possible lengths or costs of sections into account ( Berge , 1973 ; Bollobás , 1998 ).
The operation consists of “valuating” edges by a scalar: from then on, the path
lengths are no longer measured by the number of edges but by the total value of
their edges (cf. Fig. 3.4 ).
As for edge orientation, edge values may be integrated in several ways:
y and y
￿
a direct link between two nodes x and y may depend on an additional condition
related to the edge value (for example, the tie is considered valid if there is an
edge linking both nodes and if its value is lower than a given threshold);
￿
in the same way, the path from x to y may be considered valid if its total length
is below a given threshold.
Search WWH ::




Custom Search