Suppose first you have one measure. A greedy method would reduce the graph by one node or link at a time according to criteria that, for example, ensure that the graph still is connected. If you repeat this any number of steps you will get a heuristic for your problem. If you have several measures you perhaps have to weigh the objectives in some manner, and then utilize the above-described algorithm. Whatever you do, though, it sounds like it will be difficult to get results that are "stable" in the sense that the result does not depend much on the labeling/order of the nodes or links. Perhaps you need to reorder them several times and re-run the code to see if it produces weird graphs often or seldom. I would assume that your original graph has some structure that you wish to be preserved so you may want to take that measure or those measure into account in the construction of the algorithm.

Cluster analysis, machine learning, data mining, and classification analysis are names of related problem areas where there may have been done something of interest.

This immediately reminds me dimensionality reduction on the adjacency matrix of the graph. A simple experiment may show if important properties are preserved or not.

@Michael: I can imagine a greedy reduction of the graph that preserves connected components, but I find it difficult to imagine for more complex properties like centrality. Can you point to an example?

@Volkan: Dimensionality reduction of the adjacency matrix is graph coarsening, in which also the number of nodes is reduced, right? That's a related technique, but for simplicity, let's restrict ourselves to edge sparsification/reduction/filtering.

Christian: I suppose I cannot. :-) But it appears to be possible to embed a rule in the greedy algorithm by which a greedily (or arbitrarily) removed network component is put back in if it leads to a bad result, instead picking another one to remove. The complexity should not increase very much, I should think.

See papers by David Karger on how to sample edges or arcs in such a way that properties concerning maximum flows and minimum cuts are preserved.  His web page is:

http://people.csail.mit.edu/karger/

Also look for papers about "spanners", which are sparse subgraphs that approximately preserve distances. See the Wikipedia entries:

http://en.wikipedia.org/wiki/Geometric_spanner

http://en.wikipedia.org/wiki/Tree_spanner

Finally, there is a huge literature about "metric embeddings" of graphs, which are embeddings of the nodes in low-dimensional spaces that approximately preserve distances.

Let's assume you have a large human network such as cell-phones or Facebook users and your network is > 1M nodes.  This network gives the FALSE impression that anyone  is connected to anyone else, by some path, in the network.  But most FB and cell-phone activity happens in local clusters (those 1 and 2 steps away from you).  So rather than look at 1 large component of 1M nodes it makes more sense to look at the natural clusters of dozens/hundreds of people who really know each other (or at least of each other).  So how do you reduce the large component to hundreds/thousands of real life social circles? A human network of > 1000 nodes usually makes no sense from a sociological perspective -- because most people are strangers in large networks.

1) Often the reason we end up with one very large component is that we have set the bar TOO LOW for what an edge is.  If you have edge strength/frequency to work with, move it up to get rid of the noisey connections while retaining at least "weak ties".

2) Many networks have many satellites/hangers on with a degree of 1... hide all of those (you get one or more 2-cores).  This will start to show the natural emergent clusters in the data.  If you still have one large component you may try a 3-core or 4-core... but no more.

3) Betweenness is normally calculated using all geodesics in a component.  Yet, it can also be calculated using just the shorter geodesics (maxing out at 3 steps).  This efficiently find the spanners between clusters.  There iterative removal will leave you with hundreds of natural social circles.  Keep the high betweenness nodes you removed as a separate network -- as the backbone.

4) Investigate the smaller clusters and the backbone to understand both local behavior and global structure.

Herewith a possible solution or a new way of thinking in general:

Complex networks are like a human brain which is hard to decompose, while simple networks like a mechanical watch, which is decomposable.

Jiang B. and Ma D. (2015), Defining least community as a homogeneous group in complex networks, Physica A: Statistical Mechanics and its Applications, 428, 154-160, Preprint: http://arxiv.org/abs/1502.00284

Jiang B., Duan Y., Lu F., Yang T. and Zhao J. (2014), Topological structure of urban street networks from the perspective of degree correlations, Environment and Planning B: Planning and Design, 41(5), 813-828.

Another direction is to mine network motifs (k-node motif you are interested in), then you combine them into a sub-network. NetMatch (http://www.ncbi.nlm.nih.gov/pubmed/17277332) and CyClus3D (http://www.ncbi.nlm.nih.gov/pubmed/21478195). 

This recent paper of ours is an attempt at an answer to above question.

Article Structure-Preserving Sparsification of Social Networks

 I might be wrong here, but I'm still rather sceptical about how these algorithms are often used. Structurally they surely make sense, meaning that the networks preserve their integrity and most of their characteristics, but in the end there's still low reproducibility when applying certain models on longitudinal data.

What I mean is that there's almost no qualitative analysis on the network being analysed, and those algorithms and/or models end up proving to be of low applicability to the real world.

Take the example of an air transport network. You can use most filters and get the backbone of a certain sample network, but when applying it to a different time period, the initial characteristics won't be preserved.