Analysis of Average Shortest-Path Length of Scale-Free Network
Computing the average shortest-path length of a large scale-free network needs much memory space and computation time. Hence, parallel computing must be applied. In order to solve the load-balancing problem for coarse-grained parallelization, the relationship between the computing time of a single-s...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2013/865643 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832545494657662976 |
|---|---|
| author | Guoyong Mao Ning Zhang |
| author_facet | Guoyong Mao Ning Zhang |
| author_sort | Guoyong Mao |
| collection | DOAJ |
| description | Computing the average shortest-path length of a large scale-free network needs much memory space and computation time. Hence, parallel computing must be applied. In order to solve the load-balancing problem for coarse-grained parallelization, the relationship between the computing time of a single-source shortest-path length of node and the features of node is studied. We present a dynamic programming model using the average outdegree of neighboring nodes of different levels as the variable and the minimum time difference as the target. The coefficients are determined on time measurable networks. A native array and multimap representation of network are presented to reduce the memory consumption of the network such that large networks can still be loaded into the memory of each computing core. The simplified load-balancing model is applied on a network of tens of millions of nodes. Our experiment shows that this model can solve the load-imbalance problem of large scale-free network very well. Also, the characteristic of this model can meet the requirements of networks with ever-increasing complexity and scale. |
| format | Article |
| id | doaj-art-367cc30388de47da809b5e96859f20c5 |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-367cc30388de47da809b5e96859f20c52025-02-03T07:25:30ZengWileyJournal of Applied Mathematics1110-757X1687-00422013-01-01201310.1155/2013/865643865643Analysis of Average Shortest-Path Length of Scale-Free 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 of a large scale-free network needs much memory space and computation time. Hence, parallel computing must be applied. In order to solve the load-balancing problem for coarse-grained parallelization, the relationship between the computing time of a single-source shortest-path length of node and the features of node is studied. We present a dynamic programming model using the average outdegree of neighboring nodes of different levels as the variable and the minimum time difference as the target. The coefficients are determined on time measurable networks. A native array and multimap representation of network are presented to reduce the memory consumption of the network such that large networks can still be loaded into the memory of each computing core. The simplified load-balancing model is applied on a network of tens of millions of nodes. Our experiment shows that this model can solve the load-imbalance problem of large scale-free network very well. Also, the characteristic of this model can meet the requirements of networks with ever-increasing complexity and scale.http://dx.doi.org/10.1155/2013/865643 |
| spellingShingle | Guoyong Mao Ning Zhang Analysis of Average Shortest-Path Length of Scale-Free Network Journal of Applied Mathematics |
| title | Analysis of Average Shortest-Path Length of Scale-Free Network |
| title_full | Analysis of Average Shortest-Path Length of Scale-Free Network |
| title_fullStr | Analysis of Average Shortest-Path Length of Scale-Free Network |
| title_full_unstemmed | Analysis of Average Shortest-Path Length of Scale-Free Network |
| title_short | Analysis of Average Shortest-Path Length of Scale-Free Network |
| title_sort | analysis of average shortest path length of scale free network |
| url | http://dx.doi.org/10.1155/2013/865643 |
| work_keys_str_mv | AT guoyongmao analysisofaverageshortestpathlengthofscalefreenetwork AT ningzhang analysisofaverageshortestpathlengthofscalefreenetwork |