GaWC Research Bulletin 421

(Z)

Information-rich Visualisation of Dense Geographical Networks

S. Hennemann^*

Abstract

Network information on geographical entities such as cities is frequently analysed numerically, but seldom visualised in an appealing form. Reasons for this include the absence of powerful software that is capable of handling large-scale networks and layouting this information without extensive visual clutter. In addition, classic network drawing algorithms (e.g. Fruchterman-Reingold) are not optimised for the representation of geographically fixed nodes, and the standard repertoire of cartography is not suited to mapping complex network information. To tackle these issues, a method-mediating circular layout is presented that (1) roughly preserves the geographical information, (2) allows for the drawing of less cluttered relations between the geographical entities, and (3) offers the possibility of including more information on the underlying node and edge attributes when compared to conventional two-dimensional layouts.

The data used to show the capacity of the circular layout was devised by the Globalisation and World City (GaWC) research network of 2010, and represents the office networks of globalised advanced producer services firms.

Key words: Global cities, network science, bootstrapping, primary linkage algorithm, directed network model

Supplementary content (full map) available here.

Introduction

Networks are omnipresent in global socio-economic activities, and therefore a relevant object for geographical research and related cartographic mapping and visualisation. Such relational activities are based on connections (=edges) between actors (=nodes) that represent (parts of) underlying complex systems. Interestingly, most of these networks have an inherent geographical dimension, which is a constituent element of the nodes and strongly interferes with both the topology of the network (cf. Barthélemy 2011) and the ability to visualise these systems for analytical purposes.

However, the most typical method of analysing and visualising complex systems is based on the network position (e.g. centrality of a node) through algorithms that optimise the node positioning in order to reduce the visual clutter, irrespective of the geographical location. Examples of such layout algorithms include the force-directed layout Fruchterman-Reingold (Fruchterman and Reingold 1991) and the entropy-minimising Kamada-Kawai algorithm (Kamada and Kawai 1989). This is most appropriate for studying the topology and basic structures of scale-free networks that follow power-law degree distributions, i.e. a few nodes holding many linkages to other nodes and most of the nodes holding only a small number of linkages to other nodes. Scale-free related properties are present in most socio-economic networks (Newman & Park 2003). Additional information such as detailed node attributes is difficult to incorporate into the network-centred layouts (cf. figure 1a).

In contrast, conventional maps are obviously intuitively interpretable with respect to spatial patterns. However, in cases where the nodes are drawn in their geographical position (cf. figure 1b), the strong co-existence of spatial and network clustering (Hennemann et al. 2012) produces heavy cluttering and poorly readable maps (cf. Ellis & Dix 2007) unless filtering, edge-bending or other abstraction methods such as edge sampling (Rafiei & Curial 2005) are used (cf. appendix 1 in Liefner & Hennemann, 2011, or Liu et al., 2012, for examples of fixed node conventional maps). Flow maps of this type have been used frequently since they were introduced in 1869 by Charles Joseph Minard. To compensate for the obstacles in the context of complex and dense relational information, flow maps are also co-presented along with other techniques such as line density raster maps (cf. Rae 2009).

Flow maps that employ edge-bundling, i.e. those that combine and bend the edges to avoid visual clutter, reflect a recent development towards a combination of geographical location and networks attributes in conventional maps. However, most edge-bundled flow maps are still drawn by hand and only a small number of algorithms exist that are capable of reproducing complex systems in geographical spaces (cf. Verbeek et al. 2011; Holten & Van Wijk 2009; Phan et al. 2005). Furthermore, flow maps are also restricted in their ability to reproduce dense complex networks and are mainly used to show an egocentric perspective, i.e. one main place of origin that interacts with many places.

Other approaches use significant abstraction on both the network information and the geographical information to produce cartograms of geographical networks (Derudder et al. 2003). One recent example of this type of reductionist and clear mapping of geographical information onto a network layout is provided by Vinciguerra et al. (2010). The authors use the famous medieval mappa mundi as an analogy to produce a clustered map of relations among global cities according to their intra-regional coherence and the importance of groups of cities for the global city network. However, the presentation is an abstraction of the relations and makes intensive use of reduction in order to maximise the readability. Therefore, the information provided on geographical order and positioning as well as the network information, is limited.

Figure 1a:

Figure 1b:

Figure 1c:

One alternative way to combine a coarse-grained geographical positioning and an information-rich layout is presented with the circular alignment of nodes according to their regional location (firstly, grouped by continent, and secondly sub-ordered according to the longitude from west to east, cf. figure 1c). Usually, radial tree or circular layouts are not applied to reproduce geographical relations. They receive wider attention in social network analysis (e.g. U.S. Congress voting patterns in Porter et al. 2005). Radial tree layouts are most frequently used to show ego networks (e.g. Social relations in Facebook, Chen & Yang 2010). A recent example, very impressive due to its high information density, is the chord diagram that was introduced by Krzywinski et al. (2009) to map genomes.

The relative simplicity of the layout and the similarity to cartographic polar projections can be used to combine location and network information in one visualisation in geographical mapping.

Methods

The method presented is based on data from the Globalisation and World Cities (GaWC) research network, which seeks to quantify city positions based on their position in the office networks of advanced producer services (APS) firms such as banks, insurance companies and consultancy firms (cf. Taylor 2001 and the subsequent literature drawing on this method). The GaWC data is optimised for calculation as an interlocking network model (INM), which is essentially a bipartite/two-mode graph (Liu and Derudder, 2012). However, because one-mode graphs are much easier to handle numerically, two-mode graphs are often collapsed into one-mode graphs (cf. figure 2), albeit at the expense of heavy density in terms of clustering and cross-connectivity (Newman and Park 2003). Hennemann and Derudder (2012) propose a primary linkage algorithm (PLA) that almost completely preserves the idea of firm networks making up the world city network along the lines of the INM. Instead of projecting the two-mode network, they use the metaphor of control and directive power in such firm networks in order to reduce the total number of (less meaningful) connections through a system in which two offices of a firm are connected only if they represent different hierarchical level functions (e.g. local country offices and global head-quarters). The connection is directed towards the higher hierarchical level in order to indicate a ‘reporting’ relation (i.e. lower-level offices report to higher-level offices). If, for example, the office of firm F1 in city C3 were the headquarters office location of the firm network, the PLA would only create connections from C1, C2 and C4 to C3 and would not fully cross-connect all city nodes (connections C1-C2, C1-C4 and C2-C4 would be skipped). The PLA would, therefore, not project all present links in figure 2 for conceptual reasons, allowing for the different hierarchical levels of the firm nodes. This has numerical calculation advantages, but also reduces the visual clutter from the very beginning on the basis of a conceptual consideration rather than a visual reduction at arbitrary thresholds.

Figure 2:

For the purpose of the circular mapping of the global city connectivity and network centrality, there were four main steps of data preparation following data gathering:

1. The main information in the original data is the categorisation of the hierarchical levels of the offices in the 308 cities captured (see Taylor et al., 2012, for a detailed description of the dataset). To this end, the primary linkage algorithm of Hennemann and Derudder (2012) was used to create a graph of global city office networks of 58 advanced producer service firms.
2. This network was used to calculate all necessary parameters, such as the number of incoming/outgoing connections, as well as the degree and betweenness centrality of cities (using the algorithms suggested in Brandes, 2008).
   
3. All 308 cities were aligned in a circular form according to their longitude coordinates, grouped according to their continental location and connected using the network information. The continental grouping acknowledges the spatial organisation principle of most multinational firms (cf. Hennemann & Derudder 2012). The size/width, colour and opacity/transparency of nodes and edges were varied in order to reduce visual cluttering. Other node alignments (e.g. alphabetical order of cities, leaving out the continental grouping) did not produce more intuitive results, because  the geographical information was either completely lost or distorted to a large extent (e.g. Minsk and Johannesburg are mapped next to each other).
   
4. Additional information, such as the ratio of incoming and outgoing reports of each city and the level of the hierarchical connections, is displayed around the inner circle.

This leads to three distinct parts, as shown in figure 3. Firstly, there is the inner circle that contains the connections and uses a Bézier curve style. Secondly, there are the basic node attributes, such as connectivity (degree centrality) or influence (betweenness centrality). Thirdly, additional attributes of the nodes are displayed for deeper analytical purposes (e.g. the detailed fraction of incoming and outgoing connections based on the hierarchical level of the sender/receiver).

All this information was drawn through to the scalable vector graphics (SVG) standard that easily allows for transforming (e.g. rotating) elements such as texts, lines, boxes, or circles. Generally, SVG offers a broad variety of graphical elements for producing visualisations which can be further processed in many open-source and commercial programmes. SVG can handle static as well as dynamic images, and it is highly modular and suited to interactive procession on websites, which is becoming increasingly important (cf. Peng & Zhang 2004).

Figure 3:

Conclusions

The problematic presentation of network data that include geographical properties requires new methods that are able to circumvent visual clutter and unappealing layouts. Pure network layouts cannot represent networks that go beyond simple node/edge information representation, while geographical maps are a not a suitable vehicle either. Here, a mediating approach of reduced geographical accuracy was presented in a way that involves a grouped order of cities in global regions using the longitude value for the positioning of the cities on a full circle. The cities’ network attributes (such as centrality measurements) are varied with the size of the city representations. The relational information of the city-to-city connections can then easily be drawn, avoiding too much clutter. This was supported by the use of semi-transparent Bézier curves. The most interesting feature of the circular layout is its capacity to put additional information in one or more outer rings of the core. In the case of any multivariate visualization exercise, however, it is necessary to challenge the information density of the presentation. This addresses the clarity of the layout as well as the number of variables displayed. But compared to a pure structural data presentation, relational and attributed data inherently have multiple dimensions that need to be accounted for to comprehend even the basic idea of the information.

Another challenging aspect is the overall appeal in a gestalt sense. The circular layout needs to be evaluated in order to prove its readability to a wider audience. This includes alternative arrangements of the nodes, such as alphabetically or purely according to longitude coordinate, as well as real cartography polar projections or 3-dimensional layouts. Therefore, any application of similar design approaches to spatial networks is welcomed.

Taken together, a circular layout enables the analyst/researcher to put much more information on the geographical network into the static figure that is otherwise only possible with dynamic or 3-dimensional layouts. However, this comes at the expense of largely hand-crafted production processes, since there is currently no out-of-the-box tool that has automatic production layouts. Moreover, the circular layout restricts the number of nodes which can be displayed to several hundred. The visualisation of several thousand nodes would require considerably higher abstraction or completely different approaches to the visualisation of geographical networks.

In this regard, Holten (2006) provides an interesting solution for a non-geographical flow map that could be combined with the approach presented here.

Software

The data organisation and preparation (i.e. primary linkage algorithm), data analysis, network calculation (NetworkX) and SVG code generation were realised using Python.

The circular layout was inspired by works compiled in Manuel Lima’s book on visual complexity mapping (Lima, 2011). Further file transformation was conducted using Inkscape. The final map was produced with Adobe Illustrator CS3.

ACKNOWLEDGEMENTS

The author would like to thank Ben Derudder for sharing the dataset and for providing valuable comments on an earlier version of this article. The encouraging comments and suggestions of three reviewers are also very much appreciated.

REFERENCES

Barthélemy, M. (2011) Spatial Networks, Physics Reports, 499(1), 1-101. URL http://dx.doi.org/10.1016/j.physrep.2010.11.002

Brandes, U. (2008) On Variants of Shortest-Path Betweenness Centrality and their Generic Computation, Social Networks, 30(2),136-145. URL http://dx.doi.org/10.1016/j.socnet.2007.11.001

Chen, I.-X. and Yang, C.-Z. (2010) Visualisation of Social Networks, Furht, B. (Ed.): Handbook of Scial Network Technologies and Applications, 585-610. URL http://dx.doi.org/10.1007/978-1-4419-7142-5_27

Derudder, B., Taylor, P.J., Witlox, F. and Catalano, G. (2003) Hierarchical Tendencies and Regional Patterns in the World City Network: A Global Urban Analysis of 234 Cities, Regional Studies, 37(9), 875-886. URL http://dx.doi.org/10.1080/0034340032000143887

Ellis, G. and Dix, A. (2007) A taxonomy of clutter reduction for information visualisation, IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 13(6), 1216-1223. URL http://dx.doi.org/10.1109/TVCG.2007.70535

Fruchterman, T.M.J. and Reingold, E.M. (1991) Graph Drawing by Force-directed Placement, Software Practice and Experience, 21(11), 1129-1164. URL http://dx.doi.org/10.1002/spe.4380211102

Hennemann, S. and Derudder, B. (2012): An Alternative Approach to the Calculation and Analysis of Connectivity in the World City Network, arXiv:1206.6214v1 [physics.soc-ph]. URL http://arxiv.org/abs/1206.6214v1

Hennemann, S., Rybski, D. and Liefner, I. (2012) The myth of global science collaboration - Collaboration patterns in epistemic communities, Journal of Informetrics, 6(2), 217-225. URL http://dx.doi.org/10.1016/j.joi.2011.12.002

Holten, D. (2006) Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data, IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 12(5), 741–748. URL http://dx.doi.org/10.1109/TVCG.2006.147

Holten, D. And Van Wijk, J. J. (2009) Force-Directed Edge Bundling for Graph Visualization, Computer Graphics Forum, 28(3), 983-990. URL http://dx.doi.org/10.1111/j.1467-8659.2009.01450.x

Kamada, T. and Kawai, S. (1989) An algorithm for drawing general undirected graphs, INFORMATION PROCESSING LETTERS, 31(1), 7-15. URL http://dx.doi.org/10.1016/0020-0190(89)90102-6

Krzywinski, M., Schein, J., Birol, I., Connors, J., Gascoyne, R., Horsman, D., Jones, S.J. and Marra, M.A. (2009) Circos: An information aesthetic for comparative genomics, Genome Research, 19(9), 1639-1645. URL http://dx.doi.org/10.1101/gr.092759.109

Liefner, I. and Hennemann, S. (2011) Structural holes and new dimensions of distance: The Spatial Configuration of the Scientific Knowledge Network of China’s Optical Technology Sector, Environment and Planning A, 43(4), 810-829. URL http://dx.doi.org/10.1068/a43100

Lima M. (2011) Visual Complexity: Mapping Patterns of Information. Princeton Architectural Press, New York.

Liu, X. and Derudder, B. (2012) Two-Mode Networks and the Interlocking World City Network Model: A Reply to Neal, Geographical Analysis, 44(2), 171-173. URL http://dx.doi.org/10.1111/j.1538-4632.2012.00844.x

Liu, X., Neal, Z. and Derudder, B. (2012) Featured graphic. City networks in the United States: a comparison of four models, Environment and Planning A, 44(2), 255-256. URL http://dx.doi.org/10.1068/a44496

Newman, M.E.J. and Park, J. (2003) Why social networks are different from other types of networks, Physical Review E, 68(3), 036122. URL http://dx.doi.org/10.1103/PhysRevE.68.036122

Peng, Z.-R. and Zhang, C. (2004) The roles of geography markup language (GML), scalable vector graphics (SVG), and Web feature service (WFS) specifications in the development of Internet geographic information systems (GIS), Journal of Geographical Systems, 6(2), 95-116. URL http://dx.doi.org/10.1007/s10109-004-0129-0

Phan, D., Xiao, L., Yeh, R. and Hanrahan, P. (2005) Flow map layout, Proc. IEEE Symposium on Information Visualization (INFOVIS ’05), 219-224.

Porter, M.A.,, Mucha, P.J., Newman, M.E.J. and Warmbrand, C.M. (2005) A network analysis of committees in the U.S. House of Representatives, Proceedings of the National Academy of Sciences of the United States of America PNAS, 102(20), 7057-7062. URL http://dx.doi.org/10.1073/pnas.0500191102

Rae, A. (2009) From spatial interaction data to spatial interaction information? Geovisualisation and spatial structures of migration from the 2001 UK census, Computers, Environment and Urban Systems 33(3), 161-178. URL http://dx.doi.org/10.1016/j.compenvurbsys.2009.01.007

Rafiei, D. and Curial, S. (2005) Effectively Visualizing Large Networks Through Sampling, 16th IEEE Visualization 2005, 48-55. URL http://dx.doi.org/10.1109/VISUAL.2005.1532819

Taylor, P.J. (2001) Specification of the World City Network, Geographical Analysis, 33(2), 181-194. URL http://dx.doi.org/10.1111/j.1538-4632.2001.tb00443.x

Taylor, P.J., Derudder, B., Hoyler, M. and Ni, P. (2012) New Regional Geographies of the World as Practised by Leading Advanced Producer Service Firms in 2010, Transactions of the Institute of British Geographers, early view. URL http://dx.doi.org/10.1111/j.1475-5661.2012.00545.x

Verbeek, K., Buchin, K. and Speckmann, B. (2011) Flow Map Layout via Spiral Trees, IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 17(12), 2536-2544. URL http://dx.doi.org/10.1109/TVCG.2011.202

Vinciguerra, S., Taylor, P.J., Hoyler, M. and Pain, K. (2010) Featured graphic. Contemporary Mappa Mundi: American exceptionalism in the world city network, Environment and Planning A, 42(6),1271-1272. URL http://dx.doi.org/10.1068/a4352

NOTES

^* Stefan Hennemann, Justus-Liebig-Universität Gießen, Institut für Geographie, Bereich Wirtschaftsgeographie, E-mail: stefan.hennemann@geogr.uni-giessen.de