Pondering Preferential Attachment Models

Preparing to load PDF file. please wait...

0 of 0
100%
Pondering Preferential Attachment Models

Transcript Of Pondering Preferential Attachment Models

A JOURNEY DOWN THE RABBIT HOLE: PONDERING PREFERENTIAL
ATTACHMENT MODELS WITH LOCATION
By: Mark Alexander Yarrow
A thesis submitted in partial fulllment of the requirements for the degree of Doctor of Philosophy
University of Sheeld Faculty of Science
School of Mathematics and Statistics Applied Probability

Copyright
All rights reserved. No part of this document may be reproduced, distributed, or transmitted in any form or by any means, including photocopying, recording, or other electronic or mechanical methods, without the prior written permission of the author or host institution, except in the cases where correct citation is provided.

Student: Dr Mark A Yarrow
Signature: Date:

Supervisor: Dr Jonathan H Jordan
Signature: Date:

Abstract
We investigate the use of stochastic approximation as a method of identifying conditions necessary to facilitate condensation and coexistence. We did this for a variety of preferential attachment models which are growing by way of some predetermined selection criteria.
The main results presented in this thesis concern the choice of r model. This growth method uses preferential attachment to select r vertices from a graph at time n. These r vertices are subsequently ranked according to xed location assigned at
each of their creations and used as an extra level of comparison between vertices.
A new vertex is then attached to one of these r selected vertices according to a
predetermined vector of probabilities corresponding to this ranking. We have shown that condensation can occur for any of these vectors, if we can nd at least two stable xed points to the corresponding set of stochastic approximation equations. Following this we investigate the degree distribution and complexity associated to the introduction of a higher dimensional location coecient.
Our concluding chapter investigates the coexistence between vertices in preferential attachment networks where vertices posses dierent types and locations. Using sim-
ilar methods as in the choice of r model we have shown that coexistence can occur
in location type models with phase transitions helping to classify dierent cases.

Acknowledgements
I would like to express my deepest gratitude to both my supervisor Dr Jonathan Jordan and my adviser Dr Nic Freeman for both their guidance academically and personal support throughout my studies. I can say with condence that if I had not had Jonathan's enthusiasm and kind personality spurring me on, I would not have completed my studies. I would like to thank all of the members of the University of Sheeld's School of Mathematics and Statistics for their continued support during my degree.
I would like to thank my boyfriend Daniel Stevens, mother Suzanne Garrett and grandfather Donald Garrett for their continued motivation of which I am extremely grateful.
Lastly, but by no means least; I would like to thank The Absolut Company who contributed more than they will ever know.

CONTENTS
Page
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2. Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 Preferential attachment . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Fitness, choice and condensation . . . . . . . . . . . . . . . . . . . . . 11 2.3 Stochastic approximation . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.1 Example of stochastic approximation: Pólya's Urn . . . . . . . 17 2.4 Vertex types and coexistence . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.1 Coexistence tri-colour example . . . . . . . . . . . . . . . . . . 21 2.4.2 Coexistence results . . . . . . . . . . . . . . . . . . . . . . . . 23
3. Location Based Choice Model: Condensation . . . . . . . . . . . . . . . . . 25
3.1 Model description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1 Largest of r . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Choice of two . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.3.3 Middle of three . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3.4 Second or sixth of seven . . . . . . . . . . . . . . . . . . . . . 56
4. Location Based Choice Model: Degree Distribution . . . . . . . . . . . . . 63
4.1 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2 Comparison to Barabási-Albert . . . . . . . . . . . . . . . . . . . . . 72

Contents

5. Location Based Choice Model: Dimension Extension . . . . . . . . . . . . 74
5.1 Model description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.1.1 2 × 2 lattice simplication . . . . . . . . . . . . . . . . . . . . 77 5.1.2 3 × 3 lattice simplication . . . . . . . . . . . . . . . . . . . . 86

6. Competing Types With Location Model: Coexistence . . . . . . . . . . . . 89

6.1 Model description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

6.1.1 General model . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

6.1.2 Reduced model . . . . . . . . . . . . . . . . . . . . . . . . . . 92

6.2 Approximation equation structure . . . . . . . . . . . . . . . . . . . . 94

µ = 6.3 Specic attachment criteria for

12 . . . . . . . . . . . . . . . . . . 96

6.3.1 Linear model . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

6.3.2 6.3.3

Coin ip model . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.2.1 Coin ip model with m = 3, x = 12 . . . . . . . . . .
Majority wins model . . . . . . . . . . . . . . . . . . . . . . .
6.3.3.1 Majority wins model with m = 3 . . . . . . . . . . . 6.3.3.2 Majority wins model with m = 4 . . . . . . . . . . .

100 102 105 106 114

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

LIST OF FIGURES

2.1 A graph depicting the rankings of the current ve most followed mem-
bers of Twitter over the past seven years. . . . . . . . . . . . . . . . . 6
2.2 The proportion of vertices of degree k plotted both using the BarabásiAlbert models degree distribution given by (2.3) for m = 1 and as
approximated by the power law distribution given by (2.1). . . . . . . 7
2.3 Three simulations of preferential attachment on 100 vertices with different values of α. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 (Left) two pendulums in equilibrium labeled L and R prior to a perturbation. (Right) two pendulums in equilibrium labeled L and R
after a small perturbation. . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5 US presidential election timeline depicting how states voted by colour.
Red represents Republican and blue Democrat. . . . . . . . . . . . . 20
2.6 Three sets of data where points are denoted by Zi,j where j ∈ {R, B, P } and i ∈ {1, 2, . . . }. Points distributed according to Zi,j ∼ N2 (µj , Σj ). 22

3.1 A depiction of how an increase in r varies the stochastic approximation

equation for a xed value of α = − 21 evaluated at each of x ∈ {0, 21 , 1}. 42 3.2 Graphs to show how a decrease in α eects the stochastic approxima-

tion equation for a xed value of r = 5. . . . . . . . . . . . . . . . . . 43

3.3 The function F1 y; 12 , α, Ξ evaluated at four dierent values of α. . . 45

3.4 The function F1(y; x, α, e2,3) evaluated at dierent values of α and x. 50



3.5

F1

y

;

x,



3 4

,

e2,

3

evaluated at both x = 21 ± 186 .

............

50

3.6 Frequency plot of the roots of F1(y; x, 3/4, e2,3) = 0 against x. . . . . 51

3.7 Results from simulations for α = − 43 . . . . . . . . . . . . . . . . . . . 53
ModelCoexistenceCondensationVerticesAttachment Models