| | |
| | |
Stat |
Members: 3645 Articles: 2'506'133 Articles rated: 2609
26 April 2024 |
|
| | | |
|
Article overview
| |
|
Parallel Dynamics and Computational Complexity of Network Growth Models | Benjamin Machta
; Jonthan Machta
; | Date: |
16 Aug 2004 | Subject: | Statistical Mechanics | cond-mat.stat-mech | Affiliation: | 1,2) and Jonthan Machta ( University of Massachusetts Amherst, Brown University | Abstract: | The parallel computational complexity or depth of growing network models is investigated. The networks considered are generated by preferential attachment rules where the probability of attaching a new node to an existing node is given by a power, $alpha$ of the connectivity of the existing node. Algorithms for generating growing networks very quickly in parallel are described and studied. The sublinear and superlinear cases require distinct algorithms. As a result, there is a discontinuous transition in the parallel complexity of sampling these networks corresponding to the discontinuous structural transition at $alpha=1$, where the networks become scale free. For $alpha>1$ networks can be generated in constant time while for $0 leq alpha < 1$ logarithmic parallel time is required. The results show that these networks have little depth and embody very little history dependence despite being defined by sequential growth rules. | Source: | arXiv, cond-mat/0408372 | Other source: | [GID 170572] pmid15783453 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |