Complexe netwerken

Uit Wikipedia, de vrije encyclopedie

Complexe netwerken is een vrij recent onderzoeksdomein voortgevloeid uit de grafentheorie dat minder focust op de studie van kleine grafen, en de eigenschappen van individuele knopen en bogen in deze grafen, maar eerder op de statistische eigenschappen van grootschalige netwerken.

[bewerk] Inleiding

Een netwerk is een verzameling items met verbindingen tussen. De items noemen we knopen, de verbindingen ertussen bogen. In de wiskundige literatuur worden netwerken meestal grafen genoemd. Voorbeelden van netwerken zijn het internet, sociale netwerken, neurale netwerken, netwerken van referenties in wetenschappelijke papers enz. Het onderzoek rond netwerken in de vorm van grafentheorie is één van de belangrijkste onderdelen van de discrete wiskunde. De oplossing van Euler voor het "Zeven bruggen van Koningsbergen"-probleem in 1735 wordt meestal gezien als het eerste bewijs in de grafentheorie. De laatste jaren is er een nieuwe stroming in het onderzoek rond grafen ontstaan die minder focust op de studie van kleine grafen, en de eigenschappen van individuele knopen en bogen in deze grafen, maar eerder op de statistische eigenschappen van grootschalige netwerken. Deze stroming is ontstaan doordat de mogelijkheid er is gekomen om met computers data te analyseren op een veel grotere schaal dan dat vroeger ooit mogelijk was. Vroeger deed men studies met grafen van enkele tientallen of soms enkele honderden knopen, terwijl nu netwerken onderzocht worden met miljoenen of zelfs biljoenen knopen. Er is nog een bijkomende reden waarom het onderzoek rond netwerken veranderd is. Voor grafen met enkele tientallen of enkele honderden knopen is het nog mogelijk om een voorstelling van de graf te maken met punten en lijnen, en aan de hand van deze figuur antwoorden op bepaalde vragen af te leiden. Voor grafen met miljoenen of zelfs biljoenen knopen is dit gewoon onmogelijk. Statistische methoden moeten nu deze taak overnemen en een inzicht geven in de structuur van het netwerk.

[bewerk] Eigenschappen van netwerken

[bewerk] Mean geodesic en small-world effect

De mean geodesic l van een netwerk is de gemiddelde kortste afstand tussen twee knopen in het netwerk. In de jaren zestig deed Stanly Milgram een experiment waarbij brieven werden verstuurd tussen twee willekeurige personen in Noord-Amerika via sociale contacten. Uit dit experiment bleek dat er maar een klein aantal stappen (ongeveer zes) nodig is om een brief van persoon a naar persoon b te sturen. In dit geval komt het aantal stappen overeen met de mean geodesic in het sociaal netwerk. Het bestaan van een kort pad tussen twee willekeurige knopen in een complex netwerk wordt in de literatuur het small-world effect genoemd. Dat een kort pad tussen twee willekeurige knopen bestaat is statistisch aan te tonen voor random grafen. Een belangrijkere conclusie die we uit de resultaten van het experiment kunnen trekken is dat mensen blijkbaar in staat zijn om dit pad te vinden met enkel lokale kennis van het netwerk.

De mean geodesic kan als volgt gedefinieerd worden:

$l=\frac{1}{\frac{1}{2}n(n+1)}\sum_{i \ge j}d_{ij}$

waarbij $d i j$ de kortste afstand van knoop i tot knoop j is. Merk op dat in de formule de afstand van elke knoop tot zichzelf (die nul is) is meegerekend. De mean geodesic kan voor een netwerk met n knopen en m bogen berekend worden in $O (m n)$ met een breedte-eerst zoekalgoritme.

Het toepassen van deze formule geeft problemen voor grafen met meer dan één component. In deze gevallen bestaan er namelijk knopen-paren waartussen geen pad bestaat. Normaal wordt de afstand tussen zulke knopen gelijk gesteld aan oneindig, maar dan zou l ook oneindig worden. Daarom wordt l voor deze netwerken meestal gedefinieerd als de gemiddelde kortste afstand tussen alle paren waartussen een pad bestaat. Paren met knopen in verschillende componenten worden dus niet meegerekend in het gemiddelde.

[bewerk] Gradenverdeling

We kunnen voor een netwerk de gemiddelde graad van zijn knopen berekenen. Dit getal geeft ons echter niet veel informatie omdat het niets zegt over hoe de graden verdeeld zijn. Daarom is het interessanter om een verdeling op te stellen van de graden in het netwerk. Het percentage knopen in het netwerk met graad k wordt gedefinieerd als $p k$ . Deze waarde komt overeen met de kans dat een random gekozen knoop graad k heeft. De reeks ${p 1, p 2,...}$ , noemen we de gradenverdeling. De gradenverdeling kan visueel worden voorgesteld in een histogram. In plaats van percentages $p k$ kunnen ook het aantal knopen met graad k in het histogram worden weergegeven.

Deze voorstelling geeft problemen voor grafen met enkele knopen met een erg hoge graad, zoals grafen met een power-law gradenverdeling. Bij de hoge graden worden de statistische afwijkingen zo groot dat er duidelijke ruis in de histogrammen te zien is. Een alternatieve voorstelling die dit probleem minimaliseert is de cumulatieve gradenverdeling. Hierin worden in plaats van de kansen $p k$ de kansen $P k$ gegeven met $P_k = \sum_{k'=k}^{\infty} p_{k'}$ , of met andere woorden de kans op een knoop met een graad groter of gelijk aan k.

Bipartitegrafen hebben knopen van twee verschillende soorten. Knopen van dezelfde soort hebben nooit onderlinge bogen, bijgevolg kunnen we voor bipartitegrafen twee gradenverdelingen opstellen.

[bewerk] Power-law, Pareto en Zipf's distributies

Een veelvoorkomende gradenverdeling bij real-world netwerken, waaronder het internet en sociale netwerken, is een power-law gradenverdeling. Een power-law distributie is een verdeling van de vorm:

P [X = x] = C x - α

De cumulatieve distributie hiervan noemt men een Pareto-verdeling:

P [X > x] = C x - λ

De exponent $λ$ van een Pareto verdeling is gelijk aan $α - 1$ , met $α$ de exponent van de overeenkomstige power-law verdeling. Als we de graden van alle knopen van deze grafen plotten volgens grootte krijgen we een Zipf's verdeling:

y = C x - τ

Hierbij is de exponent $α$ van de overeenkomstige power-law verdeling (gradenverdeling) gelijk aan $1 + \frac{1}{\tau}$

Als we van beide leden van $y = a x k$ de logaritme nemen, krijgen we $log(y) = k log(x) + log(a)$ , wat equivalent is met $y = m x + c$ , de vergelijking van een rechte. Power-laws (en Pareto en Zipf) zijn met andere woorden te herkennen als een rechte op een grafiek in logaritmische schaal.

[bewerk] Clustering

In vele real world netwerken werd vastgesteld dat als een knoop A verbonden is met een knoop B, en knoop B met een knoop C, er een grotere kans is dat knoop A ook verbonden is met knoop C. Voor sociale netwerken bijvoorbeeld is de kans dat twee vrienden van een bepaalde persoon ook vrienden van elkaar zijn groter dan dat twee random personen vrienden zijn. Deze eigenschap wordt clustering genoemd. In termen van netwerk topologie betekent clustering dat er een hoog aantal driehoeken in het netwerk voorkomen. Een driehoek is een set van drie knopen die elk met elkaar verbonden zijn. Een maat voor de clustering in een netwerk is de clusteringscoëfficiënt C :

$C=\frac{3 \times \mbox{het aantal driehoeken in het netwerk}}{\mbox{het aantal geconnecteerde tripletten van knopen}}$

waarbij het aantal geconnecteerde tripletten van knopen het aantal subgrafen van 3 knopen en 2 bogen is. De clusteringscoëfficiënt geeft het percentage tripletten met een derde boog die er een driehoek van maakt.

[bewerk] Patronen

De clusteringscoëfficiënt geeft een maat voor het voorkomen van driehoeken in een netwerk. In real world netwerken komen dikwijls ook complexere patronen (ook wel motieven genoemd) terug. Om aan te tonen dat het voorkomen van een bepaald motief niet te wijten is aan toeval moet worden aangetoond dat het motief significant meer voorkomt in het originele netwerk dan in vergelijkbare random netwerken. Vergelijkbare random netwerken kunnen we opstellen met het configuratie model. Het aantal motieven in het echte netwerk ( $N r e a l$ ) kan dan vergeleken worden met het gemiddelde aantal motieven in de random netwerken ( $N_{rand} \pm \sigma$ , met $σ$ de standaardafwijking). Aan de hand van de Z-score kan aangetoond worden of het motief significant meer voorkomt in de originele graf. De Z-score geeft aan hoeveel standaardafwijkingen het verschil groter is voor de originele graf: $Z=\frac{N_{real} - N_{rand}}{\sigma}$

[bewerk] Scale Free netwerken

Scale-free netwerken netwerken zijn een specifiek soort netwerken die in praktijk veel voorkomen. De belangrijkste eigenschap van scale-free netwerken is dat het merendeel van de knopen een lage graad hebben, maar enkele knopen een hele hoge graad hebben. Deze knopen met een hoge graad worden hubs genoemd en houden het netwerk samen. Door deze eigenschap zijn scale-free netwerken robuust voor random aanvallen (het wegnemen van een random knoop) maar kwetsbaar voor gerichte aanvallen (het worst-case geval, namelijk het wegnemen van een hub).

Ondanks het feit dat de aandacht voor scale-free netwerken de laatste jaren erg groot is, was er tot voor kort geen exacte definitie voor. Verder waren er ook geen bewijzen voor de aangenomen eigenschappen van deze netwerken. Het kan zelfs aangetoond worden dat in de theorieën contradicties zaten en foutieve aannames werden gemaakt. Pas in 2005 werd voor het eerst een formele definitie voorgesteld waarmee een groot deel van de aangenomen eigenschappen van scale-free netwerken kon bewezen worden.

De meeste grafen die als scale-free worden bestempeld zijn grafen met een power-law gradenverdeling. Door M.E.J. Newman in The structure and function of complex networks wordt een scale-free netwerk gezien als een synoniem voor een netwerk met een power-law distributie. Als argument wordt aangehaald dat scale-free enkel slaat op gradenverdeling. De term scale free verwijst namelijk naar elke functie f(x) die onveranderd blijft, op een schalingsfactor b na, als het argument x met een factor a wordt vermenigvuldigd: $f (a x) = b f (x)$ . Power-laws zijn de enige functie die aan deze voorwaarde voldoen. Een power-law gradenverdeling impliceert het bestaan van enkele knopen met een hoge graad naast vele knopen met een lage graad. De zogenoemde hubs hebben echter niet alleen een hoge graad, maar hebben ook de eigenschap het netwerk samen te houden (robuust maar kwetsbaar).

Buiten de power-law gradenverdeling worden ook andere eigenschappen met scale-free netwerken geassocieerd. Dit zijn de belangrijkste eigenschappen van scale-free (SF) netwerken die in de literatuur worden beschreven:

SF netwerken hebben een power-law gradenverdeling.
SF netwerken kunnen gegenereerd worden door bepaalde random grafmodellen (zoals het model van Barabasi en Albert).
In SF netwerken komen hubs voor die het netwerk samenhouden en er voor zorgen dat het netwerk zowel robuust als kwetsbaar is voor het wegvallen van bepaalde knopen.
SF netwerken zijn generisch
Patronen van een SF netwerk komen terug in subgrafen van het netwerk (self-simularity).
SF netwerken zijn universeel, of maw onafhankelijk van domein specifieke eigenschappen.

Dikwijls wordt één van deze eigenschappen (meestal de power-law gradenverdeling) aangetoond om een netwerk scale-free te noemen. De andere eigenschappen worden dan als gevolg gezien.

In Towards a theory of scale-free graphs: Definition, properties, and implications introduceert men een nieuwe definitie die zoveel mogelijk van deze eigenschappen overkoepelt. Hiervoor werd voor een graf g de s-metric s(g) ingelast:

$s(g)=\sum_{(i,j) \in \epsilon} d_i d_j$

Hierin is $ε$ de verzameling bogen van g en $d i$ de graad van knoop i. Deze s-metric geeft een maat voor de aanwezigheid van hubs omdat ze gemaximaliseerd wordt als knopen met een hoge graad met elkaar verbonden zijn (dit volgt uit de rearrangement inequality). Voor een gegeven graf g kan de maximale s-metric $s m a x$ berekend worden voor alle grafen met dezelfde gradenverdeling als g. Hiermee kan een maat tussen 0 en 1 gedefinieerd worden: $S(g)=\frac{s(g)}{s_{max}}$ Grafen met $S(g) \approx 1$ zijn scale-free, grafen met een lagere $S (g)$ scale-rich. Men kan aantonen dat deze definitie de meeste van de gegeven eigenschappen van scale-free netwerken overkoepelt. Het is echter niet zo dat enkel een power-law verdeling impliceert dat een netwerk scale-free is.

[bewerk] Random netwerken

Om eigenschappen van netwerken te bestuderen wordt dikwijls met random netwerken gewerkt. Random netwerken kunnen op verschillende manieren worden opgesteld. Hieronder volgen besprekingen van enkele veelgebruikte modellen.

[bewerk] Eerste random netwerk modellen

Een eerste model om een random graf op te stellen werd voorgesteld door Paul Erdös en Alfréd Rényi in 1959. Erdös en Rényi definieerden het model $G n, p$ , een graf opgesteld volgens dit model heeft n knopen en een kans op een boog tussen een willekeurig knopenpaar gelijk aan p.

Om de limiet voor hoge n te nemen wordt de gemiddelde graad constant gehouden op $z = p (n - 1)$ . In dit geval heeft het model een Poisson gradenverdeling omdat de aan- of afwezigheid van een boog onafhankelijk is, en bijgevolg de kans dat een boog graad k heeft gelijk is aan:

$p_k = {n \choose k} p^k(1-p)^{n-k} \simeq \frac{z^k e^{-z}}{k!}$

De benaderende gelijkheid wordt exact in de limiet voor hoge n en vaste k. Vandaar worden deze grafen ook Poisson random grafen genoemd.

De structuur van een Poisson random graf wordt vooral bepaald door de waarde van p. Een belangrijke eigenschap van Poissson random grafen is de overgang van een graf met weinig bogen en kleine componenten voor een kleine p, tot een graf met veel bogen en één grote component en enkele kleine. Deze eigenschap wordt in de literatuur de fase-transitie genoemd. De ene component die opvallend groter is dan alle andere noemen we de giant component. De aanwezigheid van een giant component is een eigenschap die ook in veel real world netwerken aanwezig is.

Een Poisson gradenverdeling komt bij real world netwerken zelden voor. Een gesofisticeerder, en meer realistisch, model is het configuratie model. Bij dit model wordt een graf met n knopen opgesteld volgens een opgegeven gradenverdeling. De gradenverdeling geeft voor elke graad k de kans dat een knoop in de graf voorkomt met graad k. We kunnen de gradenverdeling voorstellen als een opeenvolging van graden $k i$ van de knopen i=1, ...,n. We kunnen een graf volgens dit model opstellen door aan elke knoop i eerst $k i$ halve bogen te hangen en vervolgens deze halve bogen random met elkaar te verbinden. Merk op dat het niet voor elke gradenverdeling mogelijk is om een graf op te stellen. Het configuratie model is interessant omdat we voor een gegeven graf een random graf kunnen opstellen met dezelfde gradenverdeling. Hiervoor knippen we gewoon alle bogen in twee en plakken ze vervolgens weer random aan elkaar. Op die manier kunnen we bijvoorbeeld aantonen dat een kenmerk met parameter x specifiek is voor de gegeven graf als x voor de gegeven graf significant afwijkt van x voor random grafen met een gelijke gradenverdeling. Het model kan uitgebreid worden om random bipartitegrafen op te stellen. In dit geval zijn twee gradenverdelingen nodig om de random graf op te stellen.

[bewerk] Het Small-World model

De topologie van netwerken kan gestructureerd zijn of kan volledig random zijn. Voorbeelden van netwerken uit de praktijk (zoals sociale netwerken) liggen echter meestal ergens tussen beide. Ze worden gekenmerkt door korte gemiddelde padlengtes en een hoge clusteringscoëfficiënt. Deze netwerken worden naar analogie met het small world effect small-world netwerken genoemd.

Een volledig gestructureerd netwerk kunnen we opstellen door een ring met n knopen en k bogen per knoop op te stellen. Van zo'n gestructureerd netwerk kunnen we een random netwerk maken door voor elke boog met kans p een knoop te verwisselen. Hoe lager p hoe gestructureerder het netwerk, hoe hoger p hoe meer random. Een small-world netwerk ligt ergens tussen beide. Dit model werd voorgesteld door Watts en Strogatz in 1998.

Volledig gestructureerde netwerken hebben een hoge clusteringscoëfficiënt maar een lange gemiddelde padlengte. Random netwerken hebben wel een korte padlengte, maar hebben dan weer een lage clusteringscoëfficiënt. Als we de gemiddelde padlengte en de clusteringscoëfficiënt bekijken voor netwerken volgens het voorgestelde model met een toenemende p dan zien we inderdaad dat er een overgangsfase is waarbij het netwerk zowel een korte gemiddelde padlengte als een hoge clusteringscoëfficiënt heeft.

Dit model kan vereenvoudigd worden door in plaats van één knoop beide knopen van een boog te verwisselen en door dubbele bogen en lussen toe te staan. Monasson stelde een alternatief model voor waarbij geen bogen worden herlegd maar bogen aan de cirkel-structuur worden toegevoegd. Dit model heeft het voordeel dat het netwerk altijd geconnecteerd blijft en de afstand tussen twee willekeurige knopen dus altijd gedefinieerd is.

[bewerk] Netwerk groei modellen

De modellen uit de vorige secties laten ons toe random netwerken op te stellen met eigenschappen die terugkomen in real world netwerken. Een belangrijke vraag is echter ook hoe deze eigenschappen tot stand komen. Typische real world netwerken zijn onderhevig aan veranderingen. Zo groeien de meeste netwerken over tijd. Zo komen er op het internet bijvoorbeeld dagelijks nieuwe webpagina's bij. Uitgaande van dit feit werden enkele nieuwe modellen voorgesteld. De belangrijkste zijn het model van Price en het model van Barabasi en Albert.

In 1965 bestudeerde Derek de Solla Price het netwerk van referenties in wetenschappelijke papers. Dit netwerk is gericht en acyclisch (een paper kan niet refereren naar een paper die later verschenen is). Hij stelde vast dat de knopen in het netwerk een inkomende en uitgaande Power-Law gradenverdeling hadden en zocht naar een model om deze eigenschap te verklaren. Power-Law's ontstaan typisch wanneer de rijkste rijker wordt. Het was Price's bijdrage om dit toe te passen op de groei van een netwerk. Voor wetenschappelijke referenties is het ook aanneembaar dat de kans dat veel gerefereerde papers opnieuw gerefereerd worden groter is dan dat weinig gerefereerde papers gerefereerd worden.

Het model gaat als volgt. Beschouw een graf met n knopen en $p k$ het percentage knopen in het netwerk met inkomende graad k. Er worden voortdurend nieuwe knopen aan het netwerk toegevoegd. Deze knopen hebben een zekere uitgaande graad die achteraf niet meer kan veranderen, deze graad kan variëren, maar de gemiddelde uitgaande graad wordt constant gehouden op m. De waarde m is ook de gemiddelde inkomende graad van het netwerk. De kans dat een nieuwe boog wordt gekoppeld aan een bepaalde knoop is proportioneel met zijn inkomende graad k op dat moment. Aangezien de initiële inkomende graad van een nieuwe knoop steeds nul is zou de kans dat een boog toekomt in deze knoop altijd nul blijven. Daarom stelde Price voor om de kans dat een boog gekoppeld wordt aan een bepaalde knoop proportioneel te maken met $k + k 0$ , met $k 0$ een constante. In de meeste gevallen wordt $k 0$ gelijk gesteld aan één.

Een ander model is het model van Barabasi en Albert. Dit model is heel gelijkaardig aan het model van Price, maar maakt geen onderscheid tussen inkomende en uitgaande graden. Het is dus een model voor ongerichte grafen. Net als bij Price wordt gestart met n knopen en worden nieuwe knopen toegevoegd met een bepaalde graad. Ook hier wordt de gemiddelde graad constant gehouden op m. Aangezien er geen onderscheid wordt gemaakt tussen inkomende en uitgaande bogen is de initiële kans dat een nieuwe boog toekomt in een knoop niet nul maar proportioneel met zijn graad.

Het idee (de rijke wordt rijker) achter de modellen van Price en van Barabasi en Albert wordt tegenwoordig dikwijls gezien als de oorzaak van Power-law distributies die terugkomen in real world netwerken. Toch volstaat een mogelijke modellering niet als verklaring voor het voorkomen in praktijk.

[bewerk] Software

NetworkX is een in Python geschreven open source package voor het maken, manipuleren en bestuderen van de structuur, eigenschappen en functie van complexe netwerken

[bewerk] Referenties

Frederik Temmermans, Semiotic Dynamics in Music File Sharing, Master Thesis, 2006.
M. E. J. Newman The structure and function of complex networks (Review article), 2003.
Lun Li, David Alderson, Reiko Tanaka, John C. Doyle, and Walter Willinger. Towards a theory of scale-free graphs: Definition, properties, and implications, 2005.
Albert-Laszlo Barabasi and Reka Albert. Emergence of scaling in random networks. Science, 286:509–512, 1999.
Lada A. Adamic. Zipf, power-laws, and pareto - a ranking tutorial, 2002.
Stanley Milgram. The small world problem. Psychology Today, May 67:60–67, 05 1967.
M. E. J. Newman. Power laws, pareto distributions and zipf ’s law. Contemporary Physics, 46:323, 2005.
Duncan J. Watts and Steven H. Strogatz. Collective dynamics of small-world networks. Nature, 393:440–442, 06 1998.

See also ebooksgratis.com: no banners, no cookies, totally FREE.