The paper deals with two topics: the quantification of the complexity of networks (graphs and digraphs) and the simplification of networks by identifying their most important parts (nodes and arcs / edges) and leaving out the less important parts. This is the second version of a paper first published in 2019.
Quantification of complexity is a preparation for the simplification/reduction of networks. It provides measures to quantify the most important nodes and arcs in a network. Complexity for graphs is first considered, by the average degree. Then the complexity of digraphs is studied on the basis of reachability. The main goal of this paper is to simplify complex networks by focusing on their essential parts. This is in fact complexity reduction. In this way one obtains an overview by removing distracting details. Edges or arcs may need to be added in order to preserve the topology of the original network. Network reduction can be compared to (and was in fact inspired by) zooming in or out at cartographic maps: for an overview of an entire country information on hamlets and villages is not needed. Only, cities, towns and other more significant geographic features that are of interest at that level are shown. Zooming in to a small part of the country yields information on less prominent features. So there is a trade‐off between scale and detail: global scale and limited detail go together as well as local scale with an abundance of detail. For networks the same kind of trade‐off can be envisioned: for an overview of the entire network the hubs are important and the way they are interconnected. For a small part of the network, however, detailed information on less important nodes should also be provided. This begs the question what are in fact the important parts of a network? How do we define them? Various measures (node ranks) are discussed to quantify the relative importance of nodes. With such measure one can in turn define arc ranks, which can be used to select important arcs.
