Network Backbone Discovery Using Edge Clustering
arXiv:1202.1842
Abstract
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.
References in corpus (5)
- Community structure in social and biological networks
- Finding community structure in networks using the eigenvectors of matrices
- Maps of random walks on complex networks reveal community structure
- Extracting the multiscale backbone of complex weighted networks
- Global organization of metabolic fluxes in the bacterium, Escherichia coli