Networks are increasingly applied in a variety of scientific and technological domains, such as for representing the channels of a communication network, providing a graphical representation of the structure and internal interconnections in a complex biological system, and so on. As the rate of data collection is accelerated, databases storing huge networks become available. Maintaining full information on the structure of such networks, and using this information for analysis and decision making, might be prohibitively expensive and slow. On the other hand, it turns out that for many practical purposes, maintaining an approximate image of the network is sufficient to enable effective usage. This raises the question of how one can construct an approximate compact representation of a large network while still preserving accuracy in the important measures to the extent possible.
Computer scientists from the Weizmann Institute developed methods for compactly representing large networks while preserving properties such as distances among pairs of vertices, quality of routing between vertices, and more. An example for such a compact representation is based on constructing a sparse subgraph (known as a "spanner") that approximates the distances in the original network. Another example is based on partitioning the network into local regions, sometimes in a hierarchical fashion (where large regions are partitioned again into sub-regions) and maintaining a suitable representation inside each region and suitable interconnections between adjacent regions. The Institute's Computer Scientists found ways to determine the extent to which the representation of a given network can be sparsified without deteriorating the quality and accuracy of the resulting compact representation.