Representing connections and relationships between things:

Graphs - a mathematical mechanism for representing connectivity

Networks - interconnected items and the relationships between them


333px-6n-graf.gif

A graph describes entities and how they are connected. The entities are called nodes and the connections are called edges. They are a very general form of representation, that can be used to describe a wide variety of everyday things (and abstract things). Here are some examples:

tube_map.gif

By one definition, a complex network is a graph with non-trivial relationships and features

LIFE SCIENCES - METABOLIC PATHWAYS (See http://www.iubmb-nicholson.org/chart.html)

metabolism.jpg
see also MAPK pathway .

Here is a visualization of the Internet.

Note that to fully represent graphs, we need methods of labeling and weighting both nodes and edges.

Question: How would you represent a social network as a graph?
a) What would be the nodes and what would be the edges?
b) What might you label and weight the edges with?
c) What questions might you want to use the graph to answer?

Check out Social Graphs and the Facebook Open Graph

You can see several beautiful visualizations of a social network at this flickr page.

Scholarometer, a project here at IU, has a visualization of a "discipline network". Nodes represent disciplined, and edges represent related disciplined (if there are enough publications co-authored by researchers in those disciplines, for example)

Representing and processing graphs on computer


To understand graphs and how they can be represented, we will use the wikipedia page . Important concepts are the Adjacency Matrix and Distance Matrix.

Pajek is a popular package for visualizing graphs, and the pajek file format is a popular format for storing graphs.

Check also the SCI2 tool from Indiana University

On the (Semantic) Web we can use RDF with OWL ontologies to describe valid relationships and nodes

Once we represent graphs, we can use them to solve problems using graph theory algorithms. Generic kinds of problem include:

As an example of Dijkstra's Algorithm we'll look at a rail example .

Some of these problems are generally intractable or NP-Complete (or NP-Hard), meaning we usually have to use heuristics to solve them. For example, the traveling salesman problem: "Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once".

For a solution to this, see TSP

Here is an applet that computes an approximate solution for TSP.

Finding a path means we need a representation of a path too. This can be a linked list, or a graph representation of the path.

A fully connected graph has n*(n-1) / 2 edges

Check out Touch Graph and Association Search and GLEaMviz

Special representations for trees


Sometimes when dealing specifically with simple hierarchical tree structures, we represent them in a different way based on the application. Technically, a tree is an acyclic graph, i.e. any one node will have a parent and/or children, but no other connections. For example, we may use a heap or a binary heap. These can speed up operations such as Dijkstra's algorithm and sorting.

A novel way of visualizing hierarchical tree structures called Tree Maps was developed by Schneiderman et al.

See the world as a tree map on this page (image copied below).
external image 04-18-World_TreeMap.jpg