A backbone extraction method with local search for complex weighted networks

Zhan BU, Zhiang WU, Liqiang QIAN, Jie CAO, Guandong XU

Research output: Chapter in Book/Report/Conference proceedingChapters

6 Citations (Scopus)

Abstract

The backbone is the natural abstraction of a complex network, which can help people to understand it in a more simplified form. Backbone extraction becomes more challenging as many networks are evolving into large scale and the weight distributions are spanning several orders of magnitude. Traditional filter-based 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 work, we propose a Local Search based Backbone Extraction Heuristic (LS-BEH) 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. Experimental results on two real-life networks demonstrate the advantage of LS-BEH over the classic disparity filter method by either effectiveness or efficiency validity. Copyright © 2014 by the Institute of Electrical and Electronics Engineers, Inc. All Rights Reserved.

Original languageEnglish
Title of host publicationProceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2014
EditorsXindong WU, Martin ESTER, Guandong XU
Place of PublicationDanvers, MA
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages85-88
ISBN (Electronic)9781479958771
ISBN (Print)9781479958764
DOIs
Publication statusPublished - Oct 2014

Citation

Bu, Z., Wu, Z., Qian, L., Cao, J., & Xu, G. (2014). A backbone extraction method with local search for complex weighted networks. In X. Wu, M. Ester, & G. Xu (Eds.), Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2014 (pp. 81-85). Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/ASONAM.2014.6921564

Fingerprint

Dive into the research topics of 'A backbone extraction method with local search for complex weighted networks'. Together they form a unique fingerprint.