A backbone extraction method with Local Search for complex weighted networks
- Publication Type:
- Conference Proceeding
- 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2014, August 17-20, 2014, 2014, pp. 85 - 88
- Issue Date:
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.
Please use this identifier to cite or link to this item: