You can have a look at the slides I'll be using for this part of the course. Some talk about trees and hierarchical graphs, the others discuss planarity and spring embedders (force-directed layouts).
Networks are everywhere. Networks either exist because they are explicitly built: think of power network where nodes may be power sites, or dispatch point and edges are cables hanging between poles or hidden underground; think of computer networks (the internet) where nodes correspond to routers and edges correspond to actual physical connections between routers (classical cables, fiber cables, radio frequency connections, etc.). Networks also appear as abstract constructions, they are useful to model situations: most of the time, links correspond to interactions between entities modeled as nodes. Think of social networks; you are not physically linked to your friends, links correspond to email exchanges, chat session or instant messaging. You could also run a (written) survey in an organization and define a network based on who people exchange with at work.
Browse the web to find animations and/or applets, showing graph layouts in action. See the JUNG package for example.
Graph drawing is covered in excellent books. Have a look at some of them:
Go have a look at the 'zoo', as Jeffrey Heer calls it (Heer is the creator of prefuse and Vizster). The zoo contains lots of images of networks and discusses some of the layout algorithms.
Trees are familiar objects in computer science (data structures, decision trees, etc.), but also in numerous other areas. Think of trees used to depict organigrams of organizations or companies, animal species, etc. They are also among the simplest objects to draw.
Their time complexity is the lowest possible O(N), where N is the number of nodes (note that N also corresponds the number of edges in this case).
Walker's algorithm is a classical example. For convenience, the algorithm requires each node to point to its parent node. it also requires every node to point to its right ad left sibling
Being able to deal with node size requires additional improvments on te algorithm. See the paper by Stein and Benteler for more details.
Exercices / Projects
Other classes of graphs have received special attention from the Graph Drawing community.
Hierarchical graphs, also known as directed acyclic graphs (DAG) do not contain cycles which allows to rank them from top to bottom. The absence of cycles indeed makes it possible to define the rank of any node, where nodes with no predecessors have rank equal to 0 (why are there necessarily nodes with no predecessors ?). Nodes are usually placed on layers according to their rank. The problem then boils down to sorting nodes as to have a minimum number of edge crossings. Note however that the underlying optimization problem is NP-complete, even when there are only two layers.
These optimization problems can become quite tricky and involve complexity theory. An excellent introduction to the crossing minimization problem is Chapter 5 of the Handbook of Graph Drawing.
Planar graphs are graphs that can be drawn by avoiding edges to cross. Testing whether a graph is planar can be computed in linear time. Planarity algorithms are however quite complex and often rely on the use of sophisticated data structure. Indeed planarity relates with deep topological properties of a graph.
More information on these two classes of graphs may be found in the Graph Drawing book.
What are the options when a graph has none of the above properties? How can we draw such a graph? There are several options.
One popular solution to display a graph is to rely on the extraction of a skeleton structure. A spanning tree is such a skeleton, which moreover may be laid out using any tree layout algorithm.
Exercices / Assignments
Using a spanning tree however may introduce a bias in the graphical represtation, letting a user think that the tree structure dominates the overall structure of the graph.
Another popular approach popularized by Peter Eades in his 1984 paper:
later to be followed by others, improving different aspects of Eades' original idea. (Fruchterman & Reingold 1991) variation is still much used and implemented, just sa GEM (Frick et al. 1994). See also Stephen Kobourov's chapter (part of the Graph Drawing Handbook)
The general idea is the following. Think of a graph as made of charged metal marbles; because marbles are charged, they tend to repulse each other. Now, whenever two nodes are linked by an edge, we think of the edge as a metal spring holding marbles together. hence, whatever forces will act on the marbles, the spring will make sure they don't get too far away from each other.
All force-directed algorithms rely on a similar metaphor. The core algorithm of any of these layout bils down to simulating the system, letting forces act on nodes and edges. In many cases, because the induced (physical) system approaches a stable state, the algorithm will produce a “pleasing” layout of the graph.
The fact that the algorithm more or less runs a simulation of the underlying forces allows one to animate it. The algorithm can also react to user interaction (moving nodes around). Have a look at the Visual Thesaurus that uses force-directed layout to display links between dictionary entries.
The simulation roughly follows the following lines:
Let p_u denote the position (in 2D or 3D space) of node u Let f_u denote a vector acting on p_u (which can be seen as a vector just as well) randomly initialize positions p_u repeat several times (often taken as O(|V|)) for all u in V set f_u = 0 for v in V f_u += f_r(u,v) where f_r(u,v) is a force repulsing u from v for v in N(u) f_u += f_a(u,v) where f_a(u,v) is a force attracting u to v for all u in V move u by a fraction of f_u
Now, because the internal loop goes over all pairs of nodes u, v, it runs in time O(N^2). Since the loop is repeated O(N) times, the overall time complexity of the algorithm is in O(N^3) which is rather high.
Exercices / Assignments
Network data differs from high-dimensional data as it is equipped with a topology – a structure built from the set of links between nodes. Being able to infer properties based on topology is a wonderful game. Graph theory is a bit about it. Network metrics offer a useful angle to identify key nodes in the network. Typically, you'll want to identify nodes that gather a maximum of links, those that hold a central positions (we'll what central may mean), etc.
|Local metrics||Distance Based Metrics||Iterative metrics|
|Closeness centralities||Betweenness centralities||Random centralities||Feedback centralities|
|Node degree ,||Harary Status||Beauchamp Closeness Centrality||Stress centrality||Random walk centrality||Katz Status Score|
|Clustering coefficient||Graph eccentricity||Dangalchev closeness centrality||Betweenness centrality||Random walk betweenness centrality||Eigenvector centrality|
|Burt's node constraint||Integration||Graph centrality||Bridging centrality||Random walk closeness centrality||Bonicich's bargaining centrality|
|Shannon entropy||Radiability||Current-flow closeness centrality||Differencial Betweenness||Hubell Status Score|
|Burt's hierarchy index||Centroid value||Reach centrality||Page Rank|
|Guimera's participation coefficient||Information centrality||Current-flow betweeness centrality||HITS|
The above table lists different graph (node) metrics organized into a taxonomy. Roughly speaking, metrics are distinguished according to their time complexity.
This is an archetypal metric – maybe one the oldest metric. Its role is vital, not only because it captures a basic and fundamental mesure on a graph, but alos because it is often easily interpretable by users. Standard node degree (number of neighbors) may be generalized to the case where edges carry weights (positive real numbers) . Edge weights may also be defined as a fucntion where when . We then consider the weighted degree of nodes, defined as:
Clustering coefficient. This measure was introduced by Watts and Strogatz in a seminal paper.
The clustering coefficient measures just how much a node sits in a tightly connected neighborhood. Looking at all neighbors v \in N(u) of a node u, it computes a ratio comparing the number of links between neighbors node to the clique (complete graph over the set of neighbors). That is, c(u)= |E(N(u))| / k(k-1)/2, where E(X) denotes the set of edges between nodes in X and k(k-1)/2 is the number of edges in a complete graph with k nodes.
Shannon entropy. This is a metric Shannon introduced in a seminal, and now historical, paper.
Shannon's entropy measure just how much a node depends on a single other node – roughly speaking, a node that must go through a single other node to reach all other nodes in the graph has low entropy. On the contrary, a node having a high number of alternative routes to the different parts of the graph has high entropy. Shannon's entropy may be defined using edge weight w(u,v) associated with egdes (u,v) incident to a node v and is computed as S(u) = - \sum_v \in N(u) log(w(u,v)) (requiring that weights add up to 1).
Shannon's entropy is maximal when all weights are equal, and decreases as weights concentrate on a single node.
Exercices / Assignments
Harary Status. This metric due to Harary was also introduced by Shimbel in an earlier paper.
The metric depends on nodes distances d(u,v) in the graph and is defined as h(u) = \sum_v \in G d(u,v). As a consequence a node with a lower status value is globally closer to all nodes in the graph.
Graph eccentricity. This metric due to Harary was also introduced by Shimbel in an earlier paper.
Exercices / Assignments
Arbesman, S. and N. A. Christakis (2010). “Leadership Insularity: A New Measure of Connectivity Between Central Nodes Networks.” Connections: bulletin of the International Network for Social Network Analysis 30(1): 4-10.
This section looks at a strategy one can implement when a metric needs to be computed on a large graph. One such strategy is to sample nodes on the graph, that is compute the exact metric but for fewer nodes.
Another approach is to compute an approximation of the target metric using a faster algorithm. Since metrics are often used to induce a colormap on nodes or edges, an approximation often does the job.
The trick is the following:
Perform a random walk on the graph Select a node Iterate long enough Go to a neighbor node and "do something" (local computation, store a value, etc.) Once you're finished hopping through nodes, run an iteration on nodes to collect, compute a final value
Let us first look at a simple example, that of computing the degree of nodes. This computation is linear in the number of edges of the graph (and we obviously do not need a faster algorithm here, but we do it for the sake of illustrating our approach).
Equip each node with a counter initially set to zero Run a random walk on the graph When on a node, hop to a neighbor by selecting one at random Each time you visit a node, increment the counter by one When finished, assign nodes the value counter/number of steps in walk
If the walk is iterated long enough, the value assigned to a node turns out to be (almost) proportionally equal to .
To see this, observe that a random walk can be implemented using matrix algebra. Indeed, define a matrix indexed with nodes where equals the probability of reaching node from node , that is .
Indeed, consider the vector (we need it to be a column vector) with a single 1 at position . The matrix multiplication then equals where exactly when is a neighbor of . This precisely says that the walk can reach any of 's neighbor in a single steps, all with equal probability. Now starting from this vector storing all possibilities, we may iterate to simultaneously compute all possibilities of reaching nodes through two steps starting at . And so on and so forth.
Iterating this again and again, defining vectors , we obtain a limit vector giving the probabilities if ending on any node (starting from ) when randomly walking on .
Now, we can precisely compute this limit vector. It is equal to . To see that it is indeed the limit vector, we may show that it is stable (it is a fixed point) since we have .
All in all, we have shown how one may obtain a relatively good approximation of node degree using a random walk.
The trick we have shown actually is quite useful when dealing with metric having high time complexity, and where one is ready to accept an approximation of a metric instead of it s genuine value.
We will now look at how a random walk can help estimate node centrality, instead of using the betweenness centrality for nodes which is known to have high time complexity.
This idea is based on a work by:
using a random walk. The authors observe that when randomly walking on a graph, assuming nodes have equal probability of being visited, central nodes are revisited on a more stable basis. That is the time you need to revisit a central node is quite stable, as opposed to non central nodes which you turn out to visit in an unstable manner – so they claim.
The idea then is to design a random walk and collect the ticks at which the walk goes through each node, and then compute the standard deviation of the time differences. Lower values for this metric then help to identify central nodes.
There is one thing though that must be looked at. For the metric to be correct, every node must be visited about the same number of times. Now, we know that the usual random walk goes through a node a number of times that is proportional to its degree. We would however like the walk to go through nodes (approximately) the same number of times, so the routing process must be slightly modified.
The trick here is to use the Metropolis-Gibbs algorithm. There is an important observation to make about the previous random walk process computing the degree of nodes. The values the walk converge to can actually be viewed as a probability distribution on nodes. What the Metropolis-Gibbs algorithm does is modify the routing procedure to force the walk towards any probability distribution we wish. In our case, we wish to force the walk to go towards the uniform distribution (all nodes with the same probability ).
The algorithm proceeds as follows to define the new walking procedure based on the previous walking procedure :
When arriving on a node v, select the next node v' towards which the walk W sends v Consider the ratio pi(v')/pi(v), using the target probablity distribution pi Draw a random number p in [0, 1] If p < pi(v')/pi(v) then go to v' Else stay on v and try again
Exercices / Assignments