LIONbook Chapter 16: Visualizing Graphs and Networks

The LIONbook on machine learning and optimization, written by co-founders of LionSolver software, is provided free for personal and non-profit usage. Chapter 16 looks at Visualizing graphs and networks by nonlinear maps.

Here is the latest chapter from LIONbook, a new book dedicated to "LION" combination of Machine Learning and Intelligent Optimization, written by the developers of LionSolver software, Roberto Battiti and Mauro Brunato.

This book is freely available on the web.

Here are the previous chapters:

You can also download the entire book here.

The latest chapter is LIONbook Chapter 16: Visualizing Graphs and NetworksChapter 16: Visualizing Graphs and Networks.

After considering visualizations based on linear projections in Chapter 15, let's now consider more general ways to feed the human unsupervised learning capabilities and derive insight from data. We assume that the n entities to be displayed are not necessarily characterized by internal coordinates, but only by item-to-item (i.e., external) relationships such as dissimilarities between two items i and j denoted by d_ij. If items do have coordinates, such external relationships can be obtained by simple ways, as explained in Sec. 12.2.

... Given the way in which our eyes work, visualization is only in two or three dimensions. Our aim is therefore to place items on the 2D plane (or in 3D space) so that their mutual distances are as close as possible to their dissimilarities. In general, a perfect placement obeying to all dissimilarities is impossible; therefore, a precise criterion is needed in order to define what placements can be considered as acceptable.

The problem is therefore the following: given a set of (positive) dissimilarities d_ij between items, find the two-dimensional or three-dimensional coordinates p_i for all items that provide a convenient placement of such items on the plane, so that dissimilarities are maintained as much as possible. The simplest approach is stress minimization, stress being the amount by which a visualized dissimilarity is compressed or expanded with respect to the original dissimilarity. It is intuitive, physical, and useful also as a starting point to understand more complex approaches.