Extracting backbones from weighted complex networks with incomplete information. (English) Zbl 1367.68268

Summary: The backbone is the natural abstraction of a complex network, which can help people understand a networked system in a more simplified form. Traditional backbone extraction methods tend to include many outliers into the backbone. What is more, they often suffer from the computational inefficiency – the exhaustive search of all nodes or edges is often prohibitively expensive. In this paper, we propose a backbone extraction heuristic with incomplete information (BEHwII) to find the backbone in a complex weighted network. First, a strict filtering rule is carefully designed to determine edges to be preserved or discarded. Second, we present a local search model to examine part of edges in an iterative way, which only relies on the local/incomplete knowledge rather than the global view of the network. Experimental results on four real-life networks demonstrate the advantage of BEHwII over the classic disparity filter method by either effectiveness or efficiency validity.


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
05C82 Small world graphs, complex networks (graph-theoretic aspects)


Full Text: DOI


[1] Ahn, Y.-Y.; Bagrow, J. P.; Lehmann, S., Link communities reveal multiscale complexity in networks, Nature, 466, 7307, 761-764, (2010)
[2] Girvan, M.; Newman, M. E., Community structure in social and biological networks, Proceedings of the National Academy of Sciences of the United States of America, 99, 12, 7821-7826, (2002) · Zbl 1032.91716
[3] Dong, H.; Wang, Z.; Gao, H., Robust \(H_\infty\) filtering for a class of nonlinear networked systems with multiple stochastic communication delays and packet dropouts, IEEE Transactions on Signal Processing, 58, 4, 1957-1966, (2010) · Zbl 1392.94183
[4] Song, C.; Havlin, S.; Makse, H. A., Self-similarity of complex networks, Nature, 433, 7024, 392-395, (2005)
[5] Hutchins, C. E.; Benham-Hutchins, M., Hiding in plain sight: criminal network analysis, Computational and Mathematical Organization Theory, 16, 1, 89-111, (2010)
[6] Choi, J. H.; Barnett, G. A.; Chon, B.-S., Comparing world city networks: a network analysis of Internet backbone and air transport intercity linkages, Global Networks, 6, 1, 81-99, (2006)
[7] Goh, K. I.; Salvi, G.; Kahng, B.; Kim, D., Skeleton and fractal scaling in complex networks, Physical Review Letters, 96, 1, (2006)
[8] Serrano, M. Á.; Boguñá, M.; Vespignani, A., Extracting the multiscale backbone of complex weighted networks, Proceedings of the National Academy of Sciences of the United States of America, 106, 16, 6483-6488, (2009)
[9] Wu, Z.; Braunstein, L. A.; Havlin, S.; Stanley, H. E., Transport in weighted networks: partition into superhighways and roads, Physical Review Letters, 96, 14, (2006)
[10] Dodds, P. S.; Watts, D. J.; Sabel, C. F., Information exchange and the robustness of organizational networks, Proceedings of the National Academy of Sciences of the United States of America, 100, 21, 12516-12521, (2003)
[11] Weihong, Y.; Yuehui, Y.; Guozhen, T., Recursive Kernighan-Lin algorithm (RKL) scheme for cooperative road-side units in vehicular networks, Parallel Computational Fluid Dynamics. Parallel Computational Fluid Dynamics, Communications in Computer and Information Science, 405, 321-331, (2014), Berlin, Germany: Springer, Berlin, Germany
[12] Stoev, S. A.; Michailidis, G.; Vaughan, J., On global modeling of backbone network traffic, Proceedings of the 29th Conference on Computer Communications (INFOCOM ’10)
[13] Kim, A.; Krim, H., Hierarchical stochastic modeling of SAR imagery for segmentation/compression, IEEE Transactions on Signal Processing, 47, 2, 458-468, (1999)
[14] Bu, Z.; Zhang, C.; Xia, Z.; Wang, J., A fast parallel modularity optimization algorithm (FPMQA) for community detection in online social network, Knowledge-Based Systems, 50, 246-259, (2013)
[15] Gfeller, D.; de Los Rios, P., Spectral coarse graining of complex networks, Physical Review Letters, 99, 3, (2007)
[16] Chalupa, J.; Leath, P. L.; Reich, G. R., Bootstrap percolation on a Bethe lattice, Journal of Physics C: Solid State Physics, 12, 1, L31-L35, (1979)
[17] Macdonald, P. J.; Almaas, E.; Barabási, A.-L., Minimum spanning trees of weighted scale-free networks, Europhysics Letters, 72, 2, 308-314, (2005)
[18] Eguíluz, V. M.; Chialvo, D. R.; Cecchi, G. A.; Baliki, M.; Apkarian, A. V., Scale-free brain functional networks, Physical Review Letters, 94, 1, (2005)
[19] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512, (1999) · Zbl 1226.05223
[20] Papadopoulos, S.; Kompatsiaris, Y.; Vakali, A.; Spyridonos, P., Community detection in social media, Data Mining and Knowledge Discovery, 24, 3, 515-554, (2012)
[21] Knuth, D. E., The Stanford GraphBase: A Platform for Combinatorial Computing, 37, (1993), Reading, Pa, USA: Addison-Wesley, Reading, Pa, USA · Zbl 0806.68121
[22] Barrat, A.; Barthélemy, M.; Pastor-Satorras, R.; Vespignani, A., The architecture of complex weighted networks, Proceedings of the National Academy of Sciences of the United States of America, 101, 11, 3747-3752, (2004)
[23] Opsahl, T.; Panzarasa, P., Clustering in weighted networks, Social Networks, 31, 2, 155-163, (2009)
[24] Corman, S. R.; Kuhn, T.; Mcphee, R. D.; Dooley, K. J., Studying complex discursive systems centering resonance analysis of communication, Human Communication Research, 28, 2, 157-206, (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.