Graph Visulalization

The post summarizes chapter 3 "GRAPH VISUALIZATION AND DATA MINING" from Diane J. Cook and Lawrence B. Holder "MINING GRAPH DATA".
A graph drawing algorithm receives as input a combinatorial description of a graph and returns as output a drawing of the graph. In particular, the edges are represented as polygonal chains in a polyline drawing, as chains of alternating horizontal and vertical segments in an orthogonal drawing, and as segments in a straight-line drawing. one of the fundamental properties of a drawing is its readability, that is, the capability of conveying the information associated with the graph in a clear way. The benefits of graph drawing techniques for data mining purposes
include analysis through visual exploration, discovery of patterns and correlations, and abstraction and summarization. Social network analysts use graph-theoretic methodologies to
identify important actors, crucial links, subgroups, roles, and network characteristics
in such graphs. In this context, graph visualization is essential to make complicated
types of analysis and data handling, such as identification of recurrent patterns and
of relationships, more transparent, intuitive, and readily accessible
For example, the centrality role of an element in a collaboration network can be more easily detected by visual inspection of a radial drawing of the network itself that is, a drawing where vertices lie on concentric circles. Web Searching is a developing effective technologies for mining data from the World Wide Web is a very fertile research field. The effectiveness and the efficiency of most common search engines rely on the structural properties of the Web graph
(Web resources and their hyperlinks). Valuable insight into the link structure and
the page rank of the Web graph can be provided by automatic visualization systems. Also, a new
generation of Web search engines is being designed, where the data collected from the World Wide Web are clustered into meaningful semantic categories. The user interacts with the Web data by means of a graphical user interface that displays these categories organized as a tree structure or organized as a graph.

Three of the most popular graph drawing approaches, namely, the force-directed, the hierarchical, and the topology-shape-metrics approach:

Force-directed methods are quite popular for network analysis since they are easy to
implement and often produce aesthetically pleasing results. The basic idea is idea is to model a graph G as a mechanical system where the vertices of G are steel rings and the edges of G are springs that connect pairs of rings. To compute a drawing of G, the rings are placed in some initial layout and let go until the spring forces move the system to a local minimum of energy.

In the hierarchical approach hierarchies arise in a variety of applications, for example, Project Evaluation Review Technique (PERT) diagrams in project planning, class hierarchies in software engineering, and is-a relationships in knowledge representation systems. It is customary to represent hierarchical graphs so that all the edges flow in the same direction, for
example, from top to bottom or from left to right. Algorithms that compute drawings
of hierarchies generally follow a methodology first introduced by Sugiyama et al that accepts, as input, a directed graph G without any particular restriction (G can be planar or not, acyclic or cyclic) and that produces as output a layered drawing of G, that is, a representation where the vertices are on horizontal layers and the edges are monotone polygonal chains connecting their end vertices.

The topology-shape-metrics approach is one of the most effective techniques for
computing highly readable drawings of graphs. It represents graphs in the so-called orthogonal drawing standard, that is, each vertex of the graph is drawn as a point or a box and each edge is drawn as a polygonal chain of horizontal and vertical segments. Orthogonal drawings are widely used in many application fields, like very large scale integration (VLSI), software engineering, information systems, internet, andWeb computing. An example showing the topology-shape visualization approach.