Loading...
Please wait, while we are loading the content...
Similar Documents
Width of a Scale-free Tree
| Content Provider | Semantic Scholar |
|---|---|
| Author | Katona, Zsolt |
| Copyright Year | 2005 |
| Abstract | Consider the random graph model of Barabási and Albert, where we add a new vertex in every step and connect it to some old vertices with probabilities proportional to their degrees. If we connect it to only one of the old vertices then this will be a tree. These graphs have been shown to have a power-law degree distribution, the same as that observed in some large real-world networks. We are interested in the width of the tree and we show that it is Wn ∼ n/√π log n at the nth step; this also holds for a slight generalization of the model with another constant. We then see how this theoretical result can be applied to directory trees. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://faculty.haas.berkeley.edu/zskatona/pdf/width.pdf |
| Alternate Webpage(s) | https://www.cambridge.org/core/services/aop-cambridge-core/content/view/DC24339CFCE235D8A8C920A20C814CEA/S0021900200000814a.pdf/width_of_a_scalefree_tree.pdf |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Barabási–Albert model Degree distribution Generalization (Psychology) Graph - visual representation Probability Published Directory Rado graph Random graph Trees (plant) Vertex (geometry) width |
| Content Type | Text |
| Resource Type | Article |
