  In this paper, we investigate the problem of network backbone discovery. In
complex systems, a "backbone" takes a central role in carrying out the system
functionality and carries the bulk of system traffic. It also both simplifies
and highlight underlying networking structure. Here, we propose an integrated
graph theoretical and information theoretical network backbone model. We
develop an efficient mining algorithm based on Kullback-Leibler divergence
optimization procedure and maximal weight connected subgraph discovery
procedure. A detailed experimental evaluation demonstrates both the
effectiveness and efficiency of our approach. The case studies in the real
world domain further illustrates the usefulness of the discovered network
backbones.
