Complexe netwerken vormen een vrij recent onderzoeksdomein voortgevloeid uit de grafentheorie en dat zich minder concentreert op de studie van kleine grafen, en de eigenschappen van individuele knopen en zijden in deze grafen, maar meer op de statistische eigenschappen van grootschalige netwerken.

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 een 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 gericht is op de studie van kleine grafen en de eigenschappen van individuele knopen en bogen in deze grafen, maar meer 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 vroeger 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 miljarden 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 graaf 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 miljarden knopen is dit niet meer mogelijk. Statistische methoden moeten nu deze taak overnemen en een inzicht geven in de structuur van het netwerk.

Eigenschappen van netwerken Mean geodesic en smallworldeffect De mean geodesic l van een netwerk is de gemiddelde kortste afstand tussen twee knopen in het netwerk. In de jaren zestig deed Stanley 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:

waarbij 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 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 gelijkgesteld 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.

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 . Deze waarde komt overeen met de kans dat een random gekozen knoop graad k heeft. De reeks , noemen we de gradenverdeling. De gradenverdeling kan visueel worden voorgesteld in een histogram. In plaats van percentages 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 gradenverdeling die aan een machtsverband voldoet. 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 de kansen gegeven met , 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.

Machtsfunctie, paretoverdeling en Wet van Zipf Een veelvoorkomende gradenverdeling bij realworldnetwerken, waaronder het internet en sociale netwerken, is een machtsfunctiegradenverdeling. Een machtsfunctieverdeling is een verdeling van de vorm:

De cumulatieve distributie hiervan noemt men een paretoverdeling:

De exponent van een paretoverdeling is gelijk aan , met de exponent van de overeenkomstige machtsfunctieverdeling. Als we de graden van alle knopen van deze grafen plotten volgens grootte krijgen we een Wet van Zipf:

Hierbij is de exponent van de overeenkomstige machtsfunctieverdeling (gradenverdeling) gelijk aan

Als we van beide leden van de logaritme nemen, krijgen we , wat equivalent is met , de vergelijking van een rechte. Machtsfunctie (en ook paretoverdelingen en wetten van Zipf) zijn met andere woorden te herkennen als een rechte op een grafiek in logaritmische schaal.

Clustering In vele real-worldnetwerken 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 netwerktopologie betekent clustering dat er een hoog aantal driehoeken in het netwerk voorkomen. Een driehoek is een verzameling van drie knopen die elk met elkaar verbonden zijn. Een maat voor de clustering in een netwerk is de clusteringscoëfficiënt C:

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.

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 configuratiemodel. Het aantal motieven in het echte netwerk () kan dan vergeleken worden met het gemiddelde aantal motieven in de random netwerken (, met de standaardafwijking). Aan de hand van de Z-score kan aangetoond worden of het motief significant meer voorkomt in de originele graaf. De Z-score geeft aan hoeveel standaardafwijkingen het verschil groter is voor de originele graaf:

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

Ondanks het feit dat de aandacht voor scale-freenetwerken 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-freenetwerken kon bewezen worden.

De meeste grafen die als scale-free worden bestempeld zijn grafen met een machtsfunctiegradenverdeling. Door M.E.J. Newman in The structure and function of complex networks wordt een scale-freenetwerk gezien als een synoniem voor een netwerk met een machtsfunctieverdeling. 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: . Machtsfuncties zijn de enige functie die aan deze voorwaarde voldoen. Een machtsfunctiegradenverdeling 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 machtsfunctiegradenverdeling worden ook andere eigenschappen met scale-freenetwerken geassocieerd. Dit zijn de belangrijkste eigenschappen van scale-free (SF) netwerken die in de literatuur worden beschreven: SF netwerken hebben een machtsfunctiegradenverdeling. 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 ervoor 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 domeinspecifieke eigenschappen. Dikwijls wordt een van deze eigenschappen (meestal de machtsfunctiegradenverdeling) 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 zo veel mogelijk van deze eigenschappen overkoepelt. Hiervoor werd voor een graf g de s-metric s(g) ingevoerd:

Hierin is de verzameling bogen van g en 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 berekend worden voor alle grafen met dezelfde gradenverdeling als g. Hiermee kan een maat tussen 0 en 1 gedefinieerd worden:

Grafen met zijn scale-free, grafen met een lagere 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 machtsfunctieverdeling impliceert dat een netwerk scale-free is.

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

Eerste randomnetwerkmodellen