A Multilevel Simplification Algorithm for Computing the Average Shortest-Path Length of Scale-Free Complex Network
Computing the average shortest-path length (ASPL) of a large scale-free network needs much memory space and computation time. Based on the feature of scale-free network, we present a simplification algorithm by cutting the suspension points and the connected edges; the ASPL of the original network c...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2014/154172 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832550151636385792 |
|---|---|
| author | Guoyong Mao Ning Zhang |
| author_facet | Guoyong Mao Ning Zhang |
| author_sort | Guoyong Mao |
| collection | DOAJ |
| description | Computing the average shortest-path length (ASPL) of a large scale-free network needs much memory space and computation time. Based on the feature of scale-free network, we present a simplification algorithm by cutting the suspension points and the connected edges; the ASPL of the original network can be computed through that of the simplified network. We also present a multilevel simplification algorithm to get ASPL of the original network directly from that of the multisimplified network. Our experiment shows that these algorithms require less memory space and time in computing the ASPL of scale-free network, which makes it possible to analyze large networks that were previously impossible due to memory limitations. |
| format | Article |
| id | doaj-art-88724acf0a2d426d8ab733fb5a7ab1be |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-88724acf0a2d426d8ab733fb5a7ab1be2025-02-03T06:07:31ZengWileyJournal of Applied Mathematics1110-757X1687-00422014-01-01201410.1155/2014/154172154172A Multilevel Simplification Algorithm for Computing the Average Shortest-Path Length of Scale-Free Complex NetworkGuoyong Mao0Ning Zhang1Department of Electronic Information and Electric Engineering, Changzhou Institute of Technology, Changzhou 213002, ChinaBusiness School, University of Shanghai for Science and Technology, Shanghai 200093, ChinaComputing the average shortest-path length (ASPL) of a large scale-free network needs much memory space and computation time. Based on the feature of scale-free network, we present a simplification algorithm by cutting the suspension points and the connected edges; the ASPL of the original network can be computed through that of the simplified network. We also present a multilevel simplification algorithm to get ASPL of the original network directly from that of the multisimplified network. Our experiment shows that these algorithms require less memory space and time in computing the ASPL of scale-free network, which makes it possible to analyze large networks that were previously impossible due to memory limitations.http://dx.doi.org/10.1155/2014/154172 |
| spellingShingle | Guoyong Mao Ning Zhang A Multilevel Simplification Algorithm for Computing the Average Shortest-Path Length of Scale-Free Complex Network Journal of Applied Mathematics |
| title | A Multilevel Simplification Algorithm for Computing the Average Shortest-Path Length of Scale-Free Complex Network |
| title_full | A Multilevel Simplification Algorithm for Computing the Average Shortest-Path Length of Scale-Free Complex Network |
| title_fullStr | A Multilevel Simplification Algorithm for Computing the Average Shortest-Path Length of Scale-Free Complex Network |
| title_full_unstemmed | A Multilevel Simplification Algorithm for Computing the Average Shortest-Path Length of Scale-Free Complex Network |
| title_short | A Multilevel Simplification Algorithm for Computing the Average Shortest-Path Length of Scale-Free Complex Network |
| title_sort | multilevel simplification algorithm for computing the average shortest path length of scale free complex network |
| url | http://dx.doi.org/10.1155/2014/154172 |
| work_keys_str_mv | AT guoyongmao amultilevelsimplificationalgorithmforcomputingtheaverageshortestpathlengthofscalefreecomplexnetwork AT ningzhang amultilevelsimplificationalgorithmforcomputingtheaverageshortestpathlengthofscalefreecomplexnetwork AT guoyongmao multilevelsimplificationalgorithmforcomputingtheaverageshortestpathlengthofscalefreecomplexnetwork AT ningzhang multilevelsimplificationalgorithmforcomputingtheaverageshortestpathlengthofscalefreecomplexnetwork |