Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: Socially-based networks are of particular interest amongst the variety of communication
networks arising in reality. They are distinguished by having small
average path length and high clustering coefficient, and so are examples of
small-world networks. This thesis studies both real examples and theoretical
models of small-world networks, with particular attention to average path
length.
Existing models of small-world networks, due to Watts and Strogatz (1998)
and Newman and Watts (1999a), impose boundary conditions on a one dimensional
lattice, and rewire links locally and probabilistically in the former
or probabilistically adding extra links in the latter. These models are investigated
and compared with real-world networks. We consider a model in
which randomness is provided by the Erdos-Rényi random network models superposed
on a deterministic one dimensional structured network. We reason
about this model using tools and results from random graph theory.
Given a disordered network C(n, p) formed by adding links randomly with
probability p to a one dimensional network C(n). We improve the analytical
result regarding the average path length by showing that the onset of smallworld
behaviour occurs if pn is bounded away from zero. Furthermore, we
show that when pn tends to zero, C(n, p) is no longer small-world. We display
that the average path length in this case approaches infinity with the network
order. We deduce that at least εn (where ε is a constant bigger than zero)
random links should be added to a one dimensional lattice to ensure average
path length of order log n. / AFRIKAANSE OPSOMMING: Sosiaal-baseerde netwerke is van besondere belang onder die verskeidenheid
kommunikasie netwerke. Hulle word onderskei deur ’n klein gemiddelde skeidingsafstand
en hoë samedrommingskoëffisiënt, en is voorbeelde van kleinwêreld
netwerke. Hierdie verhandeling bestudeer beide werklike voorbeelde en
teoretiese modelle van klein-wêreld netwerke, met besondere aandag op die
gemiddelde padlengte.
Bestaande modelle van klein-wêreld netwerke, te danke aan Watts en Strogatz
(1998) en Newman en Watts (1999a), voeg randvoorwaardes by tot eendimensionele
roosters, en herbedraad nedwerkskakels gebaseer op lokale kennis
in die eerste geval en voeg willekeurig ekstra netwerkskakels in die tweede.
Hierdie modelle word ondersoek en vergelyk met werklike-wêreld netwerke.
Ons oorweeg ’n prosedure waarin willekeurigheid verskaf word deur die Erdös-
Renyi toevalsnetwerk modelle wat op ’n een-dimensionele deterministiese gestruktureerde
netwerk geimposeer word. Ons redeneer oor hierdie modelle deur
gebruik te maak van gereedskap en resultate toevalsgrafieke teorie.
Gegewe ’n wanordelike netwerk wat gevorm word deur skakels willekeurig
met waarskynlikheid p tot ‘n een-dimensionele netwerk C(n) toe te voeg, verbeter
ons die analitiese resultaat ten opsigte van die gemiddelde padlengte deur
te wys dat die aanvang van klein-wêreld gedrag voorkom wanneer pn weg van
nul begrens is. Verder toon ons dat, wanneer pn neig na nul, C(n, p) nie meer
klein-wêreld is nie. Ons toon dat die gemiddelde padlengte in hierdie geval na
oneindigheid streef saam met die netwerk groote. Ons lei af dat ten minste εn
(waar εn n konstante groter as nul is) ewekansige skakels bygevoeg moet word by ’n een-dimensionele rooster om ‘n gemiddelde padlengte van orde log n te verseker.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/95834 |
| Date | 12 1900 |
| Creators | Taha, Samah M. Osman |
| Contributors | Sanders, J. W., Ralaivaosaona, D., Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. |
| Publisher | Stellenbosch : Stellenbosch University |
| Source Sets | South African National ETD Portal |
| Language | en_ZA |
| Detected Language | Unknown |
| Type | Thesis |
| Format | xviii, 65 p. : ill. |
| Rights | Stellenbosch University |
Page generated in 0.002 seconds