448:
are generated by the copying mechanism. If the newly introduced node were to always choose the root node as the target, a star graph would be generated. On the other hand, if the target node is always the most recent one in the network, all previous nodes are ancestors of the target and the copying mechanism would give a complete graph. Correspondingly, the total number of links
394:. Similarly, the models can be extended to include death processes, which cause vertices and edges to disappear as time evolves. A number of other extensions are possible, but we seek to determine the properties of this simple model, in order to understand which extensions are necessary to capture the complexity of the web.
430:
Middendorf-Ziv (MZ) proposed a growing directed graph modeling biological network dynamics. A prototype is chosen at random and duplicated. The prototype or progenitor node has edges pruned with probability β and edges added with probability α<<β. Based loosely on the undirected protein network
447:
Krapivsky and Redner proposed a new growing network model, which grows by adding nodes one at a time. A newly introduced node randomly selects a target node and links to it, as well as to all ancestor nodes of the target node (Fig. 2). If the target node is the initial root node, no additional links
416:
Sole proposed a growing graph initialized with a 5-ring substrate. At every time step a new node is added and a prototype is chosen at random. The prototype's edges are copied with a probability δ. Furthermore, random nodes are connected to the newly introduced node with probability α= β/N, where δ
382:
Above is the linear growth copying model. Since the web is currently growing exponentially, there is the exponential growth copying model. At each step a new epoch of vertices arrives whose size is a constant fraction of the current graph. Each of these vertices may link only to vertices from
386:
The evolving models above are by no means complete. They can be extended in several ways. First of all, the tails in the models are either static, chosen uniformly from the new vertices, or chosen from the existing vertices proportional to their out-degrees. This process could be made more
407:
Vazquez proposed a growing graph based on duplication modeling protein interactions. At every time step a prototype is chosen randomly. With probability q edges of the prototype are copied. With probability p an edge to the prototype is created.
52:
Some web page authors will note an interesting but novel commonality between certain pages, and will link to pages exhibiting this commonality; pages created with this motivation are modeled by a random choice among existing
475:
in a network of N nodes can range from N−1 (star graph) to N(N−1)/2 (complete graph). Notice also that the number of outgoing links from each new node (the out-degree) can range between 1 and the current number of nodes.
56:
Most authors, on the other hand, will be interested in certain already-represented topics, and will collect together links to pages about these topics. Pages created in this way can be modeled by node copying.
72:
For the simple case, nodes are never deleted. At each step we create a new node with a single edge emanating from it. Let u be a page chosen uniformly at random from the pages in existence before this step.
32:
of new outgoing edges. As a result of a stochastic selection, the neighbors of the new vertex are either chosen randomly among the existing vertices, or one existing vertex is randomly selected and
24:
is a process by which such a network can form and grow, by means of repeated steps in which nodes are duplicated with mutations from existing nodes. Several variations have been studied. In the
439:
Vazquez proposed a growth model based on a recursive 'copying' mechanism, continuing to 2nd nearest neighbors, 3rd nearest neighbors etc. The authors call it a 'random walk' mechanism.).
272:
128:
The second process increases the probability of high-degree nodes' receiving new incoming edges. In fact, since u is selected randomly, the probability that a webpage with degree
377:
331:
351:
181:
473:
301:
123:
146:
94:
622:
Kleinberg, J. M., R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, 1999, Proceedings of the
International Conference on Combinatorics and Computing.
183:, indicating that the copying mechanism effectively amounts to a linear preferential attachment. Kumar et al. prove that the expectation of the incoming
28:, a growing network starts as a small initial graph and, at each time step, a new vertex is added with a given number
417:
and β are given parameters in (0,1) and N is the number of total nodes at the considered time step. (see fig. 1).
493:
Kogias, A. (2005), "Modelling and simulation of the web graph: Evaluating an exponential growth copying model",
190:
391:
61:
125:, the new edge points to the destination of u's (sole) out-link; the new node attains its edge by copying.
649:
356:
310:
539:
R. V. Sole, R. Pastor-Satorras, E. Smith, T. B. Kepler, A model of large-scale proteome evolution,
184:
583:
557:
540:
520:
17:
601:
519:
A. Vazquez, A. Flammini, A. Maritan, A. Vespignani, Modeling of protein interaction networks,
387:
sophisticated to account for the observed deviations of the out-degree distribution from the
336:
593:
502:
151:
451:
277:
102:
131:
79:
45:
643:
636:, 2000b, Proceedings of the 41st IEEE Symposium on Foundations of Computer Science.
597:
629:, 2000a, Proceedings of the 19th Symposium on Principles of Database Systems.
506:
605:
633:
626:
388:
304:
588:
561:
544:
524:
632:
Kumar, R., P. Raghavan, S. Rajagopalan, D. Sivakumar, A. S. Tomkins and
625:
Kumar, R., P. Raghavan, S. Rajagopalan, D. Sivakumar, A. S. Tomkins and
574:
Krapivsky, P. L.; Redner, S. (2005-03-17). "Network growth by copying".
556:
A. Vazquez, Knowing a network by walking on it: emergence of scaling,
96:, the only parameter of the model, the new edge points to u.
36:
of its neighbors are "copied" as heads of the new edges.
495:
International
Journal of Web Engineering and Technology
454:
359:
339:
313:
280:
193:
154:
134:
105:
82:
467:
371:
345:
325:
295:
266:
175:
148:will receive a new hyperlink is proportional with
140:
117:
88:
582:(3). American Physical Society (APS): 036118.
44:Copying mechanisms for modeling growth of the
307:with an exponent which varies between 2 (for
8:
267:{\displaystyle P(k_{in})=k^{-(2-p)/(1-p)}}
48:are motivated by the following intuition:
587:
459:
453:
358:
338:
312:
279:
242:
223:
204:
192:
153:
133:
104:
81:
485:
535:
533:
7:
443:Growing network with copying (GNC)
435:WWW networks and citation networks
340:
14:
372:{\displaystyle p\rightarrow 1}
363:
326:{\displaystyle p\rightarrow 0}
317:
290:
284:
259:
247:
239:
227:
213:
197:
167:
155:
1:
403:Protein interaction networks
64:properties of the networks.
666:
598:10.1103/physreve.71.036118
507:10.1504/IJWET.2005.007463
60:Those are the growth and
346:{\displaystyle \infty }
62:preferential attachment
469:
373:
347:
327:
297:
268:
177:
176:{\displaystyle (1-p)k}
142:
119:
99:(II) With probability
90:
470:
468:{\displaystyle L_{N}}
431:model of Sole et al.
374:
348:
328:
298:
269:
178:
143:
120:
91:
76:(I) With probability
26:general copying model
452:
357:
337:
311:
296:{\displaystyle P(k)}
278:
191:
152:
132:
103:
80:
426:Biological networks
185:degree distribution
118:{\displaystyle 1-p}
18:scale-free networks
465:
369:
343:
323:
293:
264:
173:
138:
115:
86:
576:Physical Review E
412:Proteome networks
398:Undirected models
383:previous epochs.
141:{\displaystyle k}
89:{\displaystyle p}
22:copying mechanism
657:
610:
609:
591:
589:cond-mat/0410379
571:
565:
562:cond-mat/0006132
554:
548:
545:cond-mat/0207311
537:
528:
525:cond-mat/0108043
517:
511:
509:
490:
474:
472:
471:
466:
464:
463:
378:
376:
375:
370:
352:
350:
349:
344:
332:
330:
329:
324:
302:
300:
299:
294:
273:
271:
270:
265:
263:
262:
246:
212:
211:
182:
180:
179:
174:
147:
145:
144:
139:
124:
122:
121:
116:
95:
93:
92:
87:
16:In the study of
665:
664:
660:
659:
658:
656:
655:
654:
640:
639:
619:
614:
613:
573:
572:
568:
555:
551:
538:
531:
518:
514:
492:
491:
487:
482:
455:
450:
449:
445:
437:
428:
423:
421:Directed models
414:
405:
400:
355:
354:
335:
334:
309:
308:
276:
275:
219:
200:
189:
188:
150:
149:
130:
129:
101:
100:
78:
77:
70:
42:
12:
11:
5:
663:
661:
653:
652:
642:
641:
638:
637:
630:
623:
618:
615:
612:
611:
566:
549:
529:
512:
484:
483:
481:
478:
462:
458:
444:
441:
436:
433:
427:
424:
422:
419:
413:
410:
404:
401:
399:
396:
368:
365:
362:
342:
322:
319:
316:
292:
289:
286:
283:
261:
258:
255:
252:
249:
245:
241:
238:
235:
232:
229:
226:
222:
218:
215:
210:
207:
203:
199:
196:
172:
169:
166:
163:
160:
157:
137:
114:
111:
108:
85:
69:
66:
58:
57:
54:
46:World Wide Web
41:
38:
13:
10:
9:
6:
4:
3:
2:
662:
651:
648:
647:
645:
635:
631:
628:
624:
621:
620:
616:
607:
603:
599:
595:
590:
585:
581:
577:
570:
567:
563:
559:
553:
550:
546:
542:
536:
534:
530:
526:
522:
516:
513:
508:
504:
500:
496:
489:
486:
479:
477:
460:
456:
442:
440:
434:
432:
425:
420:
418:
411:
409:
402:
397:
395:
393:
390:
384:
380:
366:
360:
320:
314:
306:
287:
281:
256:
253:
250:
243:
236:
233:
230:
224:
220:
216:
208:
205:
201:
194:
186:
170:
164:
161:
158:
135:
126:
112:
109:
106:
97:
83:
74:
67:
65:
63:
55:
51:
50:
49:
47:
39:
37:
35:
31:
27:
23:
19:
650:Graph theory
579:
575:
569:
552:
515:
498:
494:
488:
446:
438:
429:
415:
406:
392:distribution
385:
381:
127:
98:
75:
71:
59:
43:
33:
29:
25:
21:
15:
68:Description
617:References
303:follows a
40:Motivation
606:1539-3755
501:(1): 29,
389:power-law
364:→
341:∞
318:→
305:power-law
254:−
234:−
225:−
162:−
110:−
644:Category
634:E. Upfal
627:E. Upfal
274:, thus
604:
333:) and
53:pages.
584:arXiv
558:arXiv
541:arXiv
521:arXiv
480:Notes
353:(for
602:ISSN
20:, a
594:doi
503:doi
379:).
187:is
646::
600:.
592:.
580:71
578:.
532:^
497:,
608:.
596::
586::
564:.
560::
547:.
543::
527:.
523::
510:.
505::
499:2
461:N
457:L
367:1
361:p
321:0
315:p
291:)
288:k
285:(
282:P
260:)
257:p
251:1
248:(
244:/
240:)
237:p
231:2
228:(
221:k
217:=
214:)
209:n
206:i
202:k
198:(
195:P
171:k
168:)
165:p
159:1
156:(
136:k
113:p
107:1
84:p
34:k
30:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.