About Networks

images\scrn_abtnet.gif

 

A network consists of nodes that may or may not be connected together by links. Networks are often illustrated with dots or circles representing the nodes and straight or curved lines between nodes representing the links. Nodes may be joined by more than one link. There may even be nodes that are not connected by any link. A network drawn in a GIS or CAD system will be drawn using points for the nodes and lines for the links.

 

The most important thing about a network for new users to understand is that it is defined by its nodes, and not by the links. People new to network analysis will often look at a drawing of lines and think "Aha! That's a network." However, if there are no points in that drawing there is no network in the drawing. Since GIS users will often wish to use a system of lines as a network even if it contains no nodes, Manifold takes a less strict view: default operators in Manifold will treat as a network any system of lines where the endpoints of the lines exactly coincide even if no points exist at the ends of the lines.

 

We could continue calling these objects "points" and "lines"; however, the terminology normally shifts into the use of the words "nodes" and "links" when a GIS map of points and lines is being treated as a network. That’s because (as we will see below) there are certain implications when one says a line is a link in a network. For example, a link always runs between two nodes. There is no such thing in a network as a "line" all by itself without a point at either end.

 

Although networks are used to represent real systems which actually look like networks, for example, a road system, networks may also be used to analyze physical systems which don’t look at all in real life like dots connected by lines. For example, networks may be used to represent the relationships between elements in complex systems such as the assembly of complex machines, scheduling tasks, or the operation of compilers.

 

Network theory has handy names to describe key qualities of networks, links, and nodes. Most of the time these names are quite clear and intuitively obvious. For example, a link which joins a node to itself is called a self-loop.

 

Links may be directed or undirected. A directed link is like a one-way street: it comes out of one node and goes into another node. Directed links are also called arcs. Networks which include directed links are called directed networks or oriented networks. Networks that have only undirected links are called undirected networks or unoriented networks. Directionality is implied in links drawing in GIS data by the sequence of coordinates that define a line.

 

Transportation networks involving a mix of one-way and two-way streets are often modeled as directed networks consisting of nodes joined by one or two directed links. Two-way streets are modeled as two directed links, one going each way, between nodes. However, directed links are only useful to the extent that network functions take such directionality into account. Most default Manifold network operators will ignore directionality.

 

Links and nodes in networks may also have weights associated with them. Weights are simply values in some data field associated with the link or node that represent some parameter that is important to the task at hand. For example, a network that represents a communications network might have a weight assigned to each link where the weight is a number giving the flow capacity of that communications link.

 

To take another example, consider a network that represents an interstate road system with a node for each city or major highway intersection with links between each node representing the interstate highway links between each city or intersection. Such a network might have several weights on each link representing values such as the measured physical length of that link, the maximum speed limit, the number of lanes, the average travel time over the link and so on. Nodes might have weights representing the total population in the city, average income, how many dealers we have in that city, what the average sales per dealer are, and so forth.

 

For the mathematically inclined…

 

When we talk about "networks" and "network theory" we are really discussing a branch of mathematics called graph theory. Although most people use the word "graph" in business to mean a diagram such as a bar chart, in mathematics the word "graph" refers to a mathematical object that consists of nodes that may or may not be joined by links.

 

In casual use, graphs are also called networks, for example as in "a road network," even though that’s not always strictly true. Since Manifold is sold mostly to non-mathematicians we use a more relaxed commercial terminology and use the term network throughout.

 

Historical Note

 

images\ill_euler.gif

 

Leonhard Euler

 

Graph theory as we known it in modern times was founded by Leonhard Euler, born 15 April 1701 in Basel, Switzerland, and died 18 September 1783 in St. Petersburg, Russia. Perhaps the most prolific mathematician of all time, Euler founded graph theory while writing a discourse on the Bridges of Konigsberg problem.

 

images\ill_bridges.gif

 

The citizens of this Russian city enjoyed strolling the city while crossing the seven bridges. A popular entertainment was trying to figure out if one could walk over all seven bridges without repeating a bridge. Euler proved this was not possible.

 

Euler joined the St Petersburg Academy of Science in 1727 and served there until 1741 as a both a professor of physics and mathematics. He lived in Berlin for 25 years from 1741 until returning to Russia in 1766. Although almost entirely blind in the years after 1766, from then until his death in 1783 he produced almost half of his prodigious life’s product of over 880 books and papers. He was able to continue work by relying on his extraordinary memory.

 

Pronunciation

 

In English, "Euler" is pronounced as "oil - er" with the stress on the first syllable.