Optimeringsmekanism

Inom nätverksvetenskap är optimeringsmekanismen en nätverkstillväxtalgoritm , som slumpmässigt placerar nya noder i systemet och kopplar dem till de befintliga noderna baserat på en kostnads-nyttoanalys . Beroende på parametrarna som används i optimeringsmekanismen kan algoritmen bygga tre typer av nätverk: ett stjärnnätverk, ett slumpmässigt nätverk och ett skalfritt nätverk . Optimeringsmekanismen tros vara den underliggande mekanismen i flera verkliga nätverk, såsom transportnätverk, elnät, routernätverk, nätverk av motorvägar, etc.

Generella egenskaper

Optimeringsmekanismen är en modell med tillväxt, där förmånsfäste är giltigt under vissa antaganden. Till skillnad från kopieringsmodellen använder optimeringsmodellen global information om nätverket för att koppla de nyinkomna noderna till de befintliga, vilket minskar mängden slumpmässighet i processen. Modellens mekanism är baserad på en kostnads-nyttojämförelse, det vill säga för varje ingående nod 'i', beräknar algoritmen nettonyttan (fördelar minus kostnader) av att ansluta 'i' till varje befintlig nod, och kopplar nod 'i' till den nod som ger den högsta nettonyttan.

Beskrivning

Kostnaderna och fördelarna i optimeringsmodellerna kan generellt förenklas till två attribut: avståndet mellan den nya noden och den befintliga; och avståndet för den befintliga noden från den centrala noden. Således kan målfunktionen skrivas i följande form:

$C_{i}=min_{j}[\delta *d_{ij}+h_{j}]$

• där $C_{i}$ står för den minimala kostnaden för att koppla nod 'i' till en befintlig nod
• $d_{ij}$ anger avståndet mellan noden 'i' och 'j'
• $h_{j}$ representerar avståndet mellan noden 'j' från den centrala noden
• $\delta$ är en parameter som bestämmer vikten av det individuella avståndet jämfört med avståndet till den centrala noden, och därför varierar den mellan olika inställningar.

I ett motorvägsnätverk - där städer är noder och länkar är motorvägar - skulle $d_{ij}$ vara det fysiska avståndet mellan städer, och $h_{j}$ skulle vara avståndet från huvudstaden (eller från den centrala staden i regionen). Värdet på $\delta$ bestämmer vilken typ av nätverk som byggs av optimeringsmekanismen.

Star Network

Optimeringsmekanismen resulterar i ett stjärnnätverk närhelst $\delta <(1/2)^{1/2}$ . En unik egenskap hos stjärnnätverket är att de flesta av de nytillkomna noderna kommer att ansluta till den centrala noden oavsett avstånd. Man kan tänka sig ett stjärnnät som ett nätverk där kostnaderna för att etablera en ny länk är försumbara jämfört med fördelen med att vara direkt ansluten till den centrala noden. Stjärnnätverk observeras sällan i verkligheten.

Slumpmässigt nätverk

Ett slumpmässigt nätverk byggs med optimeringsmetoden när ${\displaystyle \delta >N^{1/2$ . Vid en tillräckligt hög $\delta$ är kostnaderna för att etablera en ny länk enormt höga, jämfört med fördelen med att vara nära kopplad till den centrala noden. Som ett resultat kommer de flesta av de nya noderna att ansluta till den närmsta tillgängliga noden. Ett verkligt exempel är elnätet, där kostnaden för att bygga en kraftledning är hög och fördelarna med att vara direktanslutna till strömkällan är försumbara.

Skalfritt nätverk

${\displaystyle 4<\delta <N^{1/2$ } Om $\delta$ varken är för hög eller för låg, resulterar mekanismen i ett skalfritt nätverk, kännetecknat av preferentiell anslutning. De nyligen tillagda noderna tenderar att ansluta till de större noderna, men ibland kan de ansluta till medelstora noder, eller till och med små, beroende på deras avstånd. De flesta av de verkliga nätverken som kännetecknas av en underliggande optimeringsmekanism är skalfria nätverk, såsom routernätverket och motorvägsnätet.