In the first part of the paper several measures for the complexity of networks (graphs and digraphs) are proposed and some of their properties are investigated. The second part of the paper is devoted to methods to simplify networks. This is done by identifying the important nodes (using node ranks). From these arc ranks are computed. Both types of ranks are used to identify the important parts of a network.
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. The first topic is a preparation for the second one. 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.
