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

Qian, Liqiang; Bu, Zhan; Lu, Mei; Cao, Jie; Wu, Zhiang

Abstr. Appl. Anal. 2015, Article ID 105385, 11 p. (2015).

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.

MSC:

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

Software:

GraphBase

References:

[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)