Krapivsky PL, Redner S "Organization of growing random networks" PHYSICAL REVIEW E 63 (6): art. no. 066123 Part 2 JUN 2001

[Eugene Garfield]

P.L. Krapivsky : paulk at buphyk.bu.edu

TITLE Organization of growing random networks
AUTHOR Krapivsky PL, Redner S
JOURNAL PHYSICAL REVIEW E   63 (6): art. no. 066123 Part 2 JUN 2001

 Document type: Article
Language: English
Cited References: 56
Times Cited: 8


Abstract:
The organizational development of growing random networks is investigated.
These growing networks are built by adding nodes successively, and linking
each to an earlier node of degree k with an attachment probability A(k).
When A(k) grows more slowly than linearly with k, the number of nodes with k
links. N-k(t), decays faster than a power law in k, while for A(k) growing
faster than linearly in k, a single node emerges which connects to nearly
all other nodes. When A(k) is symptotically linear, N-k(t) similar to
tk(-nu), With nu dependent on details of the attachment probability, but in
the range 2 < <nu><<infinity>. The combined age and degree distribution of
nodes shows that old nodes typically have a large degree. There is also a
significant correlation in the degrees of neighboring nodes, so that nodes
of similar degree are more likely to be connected. The size distributions of
the in and out components of the network with respect to a given
node-namely, its "descendants" and "ancestors''-are also determined. The in
component exhibits a robust s(-2) power-law tail, where s is the component
size. The out component has a typical size of order In t, and it provides
basic insights into the genealogy of the network.

KeyWords Plus:
WORLD-WIDE-WEB, DEGREE SEQUENCE, INTERNET, GROWTH, AGGREGATION, MODEL,
BEHAVIOR, KINETICS, DYNAMICS, GRAPH

Addresses:
Krapivsky PL, Boston Univ, Ctr BioDynam, Boston, MA 02215 USA
Boston Univ, Ctr BioDynam, Boston, MA 02215 USA
Boston Univ, Ctr Polymer Studies, Boston, MA 02215 USA
Boston Univ, Dept Phys, Boston, MA 02215 USA

Publisher:
AMERICAN PHYSICAL SOC, COLLEGE PK

IDS Number:
442KU

ISSN:
1063-651X
 Cited Author            Cited Work                Volume      Page
Year

 AIELLO W              UNPUB
 ALBERT R              NATURE                       401       130      1999
 BARABASI AL           PHYSICA A                    272       173      1999
 BARABASI AL           SCIENCE                      286       509      1999
 BARTHELEMY M          PHYS REV LETT                 82     3180*      1999
 BECKER R              ANN PHYSIK                    24       719      1935
 BLACKMAN JA           EUROPHYS LETT                 16       115      1991
 BOLLOBAS B            RANDOM GRAPHS                                   1985
 BRILLIANTOV NV        J PHYS A-MATH GEN             24      4787      1991
 BRILLIANTOV NV        SOV PHYS-SOLID STATE          31       271      1989
 BRODER A              COMPUT NETW                   33       309      2000
 CALDARELLI G          EUROPHYS LETT                 52       386      2000
 CALDARELLI G          J THEOR BIOL                 193       345      1998
 CALOGERO F            J PHYS A-MATH GEN             33      5619      2000
 CAMACHO CJ            CONDMAT0103114
 DOMANY E              MODELS NEURAL NETWOR           1                1995
 DOROGOVTSEV SN        CONDMAT0004434
 DOROGOVTSEV SN        PHYS REV E A                  62      1842      2000
 EGGHE L               INTRO INFORMETRICS                              1990
 ERNST MH              FUNDAMENTAL PROBLEMS           6                1985
 FALOUTSOS M           COMP COMM R                   29       251      1999
 GARFIELD E            SCIENCE                      178       471      1972
 GILBERT N             SOCIOL RES                     2         2      1997
 GRAHAM RL             CONCRETE MATH FDN CO                            1989
 HENDRIKS EM           J COLLOID INTERF SCI          97       176      1984
 HUBERMAN BA           NATURE                       401       131      1999
 HUBERMAN BA           SCIENCE                      280        95      1998
 JANSON S              RANDOM GRAPHS                                   2000
 KAUFFMAN SA           ORIGIN ORDER SELF OR                            1993
 KLEINBERG J           LECT NOTES COMPUTER         1627                1999
 KRAPIVSKY PL          CONDMAT0005139
 KRAPIVSKY PL          IN PRESS PHYS REV LE
 KRAPIVSKY PL          PHYS REV B                    59    15950*      1999
 KRAPIVSKY PL          UNPUB
 KUMAR R               VLDB 99 P 25 INT C V                   639      1999
 LAHERRERE J           EUR PHYS J B                   2       525      1998
 LANGER JS             SOLIDS FAR EQUILIBRI                            1992
 LARSON RR             P 1996 ANN ASIS M BA                            1996
 LAURENCOT P           NONLINEARITY                  12       229      1999
 LEYVRAZ F             PHYS REV A                    36     4033*      1987
 LEYVRAZ F             PHYS REV LETT                 57      163*      1986
 LOTKA AJ              J WASHINGTON ACADEMY          16       317      1926
 MATSOUKAS T           J COLLOID INTERF SCI         132        13      1989
 MEDINA A              COMPUT COMMUN REV             30        18      2000
 MILGRAM S             PSYCHOL TODAY                  2        60      1967
 MOLLOY M              COMB PROBAB COMPUT             7       295      1998
 MOLLOY M              RANDOM STRUCT ALGOR            6       161      1995
 NEWMAN MEJ            CONDMAT0007214
 NEWMAN MEJ            CONDMAT007235
 REDNER S              EUR PHYS J B                   4       131      1998
 SHOCKLEY W            P IRE                         45       279      1957
 SIMON HA              BIOMETRIKA                    42       425      1955
 SIMON HA              MODELS MAN                                      1957
 UMAR R                P 8 WORLD WID WEB C                             1999
 WATTS DJ              NATURE                       393       440      1998
 ZANETTE DH            NLINAO009046