Extracting Backbones from Weighted Complex Networks with Incomplete Information
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—th...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2015-01-01
|
| Series: | Abstract and Applied Analysis |
| Online Access: | http://dx.doi.org/10.1155/2015/105385 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832559818557095936 |
|---|---|
| author | Liqiang Qian Zhan Bu Mei Lu Jie Cao Zhiang Wu |
| author_facet | Liqiang Qian Zhan Bu Mei Lu Jie Cao Zhiang Wu |
| author_sort | Liqiang Qian |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-370baa4f140d49b6829c1a776c861a12 |
| institution | Kabale University |
| issn | 1085-3375 1687-0409 |
| language | English |
| publishDate | 2015-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Abstract and Applied Analysis |
| spelling | doaj-art-370baa4f140d49b6829c1a776c861a122025-02-03T01:29:08ZengWileyAbstract and Applied Analysis1085-33751687-04092015-01-01201510.1155/2015/105385105385Extracting Backbones from Weighted Complex Networks with Incomplete InformationLiqiang Qian0Zhan Bu1Mei Lu2Jie Cao3Zhiang Wu4School of Computer Science and Technology, Soochow University, Suzhou 215006, ChinaJiangsu Provincial Key Lab. of E-Business, Nanjing University of Finance and Economics, Nanjing 210046, ChinaSchool of Computer Science and Technology, Soochow University, Suzhou 215006, ChinaJiangsu Provincial Key Lab. of E-Business, Nanjing University of Finance and Economics, Nanjing 210046, ChinaJiangsu Provincial Key Lab. of E-Business, Nanjing University of Finance and Economics, Nanjing 210046, ChinaThe 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.http://dx.doi.org/10.1155/2015/105385 |
| spellingShingle | Liqiang Qian Zhan Bu Mei Lu Jie Cao Zhiang Wu Extracting Backbones from Weighted Complex Networks with Incomplete Information Abstract and Applied Analysis |
| title | Extracting Backbones from Weighted Complex Networks with Incomplete Information |
| title_full | Extracting Backbones from Weighted Complex Networks with Incomplete Information |
| title_fullStr | Extracting Backbones from Weighted Complex Networks with Incomplete Information |
| title_full_unstemmed | Extracting Backbones from Weighted Complex Networks with Incomplete Information |
| title_short | Extracting Backbones from Weighted Complex Networks with Incomplete Information |
| title_sort | extracting backbones from weighted complex networks with incomplete information |
| url | http://dx.doi.org/10.1155/2015/105385 |
| work_keys_str_mv | AT liqiangqian extractingbackbonesfromweightedcomplexnetworkswithincompleteinformation AT zhanbu extractingbackbonesfromweightedcomplexnetworkswithincompleteinformation AT meilu extractingbackbonesfromweightedcomplexnetworkswithincompleteinformation AT jiecao extractingbackbonesfromweightedcomplexnetworkswithincompleteinformation AT zhiangwu extractingbackbonesfromweightedcomplexnetworkswithincompleteinformation |