Teorie sítě je studium grafů jako reprezentace jednoho symetrického vztahu nebo asymetrickými mezi diskrétních objektů. Je to součást teorie grafů : síť lze potom definovat jako graf, kde uzly (vrcholy) nebo hrany (nebo „oblouky“, pokud je graf orientován ) mají atributy, například štítek (tag) .
Teorie sítí nachází uplatnění v různých oborech včetně statistické fyziky , částicové fyziky , informatiky , elektrotechniky , biologie , ekonomiky , financí , operačního výzkumu , klimatologie nebo společenských věd .
Existuje mnoho typů sítí: logistické sítě , World Wide Web , Internet , genetická regulační sítě , metabolické sítě , sociální sítě , sémantické sítě , neuronové sítě , atd.
Studie sítí se objevily v různých oborech, aby umožnily analýzu komplexních relačních dat. Nejstarším známým dokumentem v oblasti studia grafů je problém týkající se sedmi Königsbergových mostů, které napsal Leonhard Euler v roce 1736. Eulerův matematický popis vrcholů a hran byl základem teorie grafů , oboru matematiky, který studuje vlastnosti dyadických vztahů síťové struktury. Pole teorie grafů se nadále rozvíjelo a našlo uplatnění v chemii (Sylvester, 1878).
Dénes Kőnig , maďarský matematik a profesor, napsal v roce 1936 první knihu o teorii grafů s názvem (v anglické verzi): Teorie konečného a nekonečného grafu .
Ve třicátých letech emigroval Jacob Moreno , psycholog z Gestaltské školy do Spojených států . Tam vytvořil sociogram, který představil veřejnosti v dubnu 1933 na konvenci lékařů . Sociogramu tehdejší reprezentace sociální struktury části skupiny o žáky základních škol . Mezi chlapci byli přátelé s ostatními chlapci a děvčata byli přátelé s ostatními dívkami, s výjimkou jednoho chlapce, který řekl, že měl rád dívku. Tento pocit však nebyl vzájemný, což je vidět na sociogramu. Zobrazení ze sítě společenských vztahů byla považována za tak zajímavé, že byl vytištěn v New York Times (3. dubna 1933, strana 17). Od té doby našla sociometrie mnoho aplikací a vyvinula se v oblasti analýzy sociálních sítí .
Pravděpodobnostní teorie v síťové analýze jsou potomky teorie grafů, zejména díky 8 článkům Paula Erdőse a Alfréda Rényiho o náhodných grafech . Pro analýzu sociálních sítí je navrženým pravděpodobnostním modelem exponenciální náhodný graf (ERGM), kde p * je skórovací rámec používaný k reprezentaci prostoru pravděpodobnosti výskytu odkazu v síti. Dalším příkladem použití pravděpodobnostních nástrojů ve struktuře sítě je matice pravděpodobnosti sítě, která modeluje pravděpodobnost výskytu odkazů v síti, v závislosti na historické přítomnosti nebo nepřítomnosti odkazu v síti. Vzorek sítí.
V 80. letech 20. století mnoho sociologů pracovalo na síťové analýze. Zejména v roce 1992 se objevila kniha Harrisona Whitea Identita a kontrola , která zavádí mnoho klíčových konceptů ( vkládání, oddělení, přepínání, netdom , abychom jmenovali alespoň některé). V roce 1994 se pak objevila slavná Social Network Analysis: Methods and Applications, autorů Wassermana a Fausta, referenční práce na opatřeních a metodách v analýze sociálních sítí .
V poslední době se další práce v teorii sítí zaměřují na matematický popis různých topologií prezentovaných sítěmi. Duncan Watts sjednotil stará empirická data na sociálních médiích do matematické reprezentace popisující malý svět .
Albert-László Barabási a Réka Albert vyvinuli škálovou invariantní síť , definovanou jako topologie sítě obsahující vrcholy hub s mnoha připojeními, což umožňuje udržovat konstantní poměr mezi počtem připojení všech ostatních uzlů. I když se zdá, že si tento vzhled zachovává mnoho sítí, například internet , jiné sítě již dlouho mají distribuce uzlů, které se pouze přibližují neškálovaným poměrům.
Dnes jsou síťové studie zajímavé pro mnoho soukromých i veřejných sektorů, včetně amerického ministerstva obrany .
Analýza sociální sítě zkoumá strukturu vztahů mezi sociálními entitami. Těmito entitami jsou často lidé , ale mohou to být také skupiny , organizace , národní státy , webové stránky nebo vědecké publikace . Studium sítí hraje ústřední roli v sociálních vědách a ve většině matematických a statistických nástrojů používaných pro studium sítí byly nejprve vyvinuty v sociologii , podle sociologů .
Mezi mnoha dalšími aplikacemi se analýza sociálních médií používá k pochopení šíření inovací , zpráv a pověstí . Podobně se používá ke zkoumání šíření nemocí a zdraví chování . Rovněž byla použita při průzkumu trhu, aby se prozkoumala role důvěry v obchod a v cenovém procesu .
Podobně se používá ke studiu náboru do sociálních hnutí a sociálních institucí . Používá se také k pojímání vědeckých neshod a sociální prestiže v akademické sféře . V poslední době se analýza sociálních médií ve vojenském zpravodajství ve velké míře používá k odhalení povstaleckých sítí , hierarchických i bez vůdců.
Dynamická analýza sociálních sítíDynamická síťová analýza zkoumá měnící se strukturu vztahů mezi různými třídami entit ovlivňující složité sociálně - technické systémy a odráží sociální stabilitu i změny, jako je vznik nových skupin , subjektů a vedoucích . Dynamická síťová analýza se zaměřuje na metasítě složené z několika typů uzlů (entit) a několika typů odkazů ( multiplexita ). Tyto entity se mohou velmi lišit. Mezi příklady patří lidé , organizace , témata , zdroje , úkoly, události , místa a přesvědčení .
Analytické metody dynamické sítě jsou obzvláště užitečné pro hodnocení trendů a změn v sítích v průběhu času, identifikace vznikajících vůdce , a zkoumá co - vývoj z lidí a myšlenek .
S rozvojem veřejně dostupných biologických databází vzbudila analýza molekulárních sítí značný zájem. Analýza biologických sítí úzce souvisí s analýzou sociálních sítí a často se zaměřuje na místní vlastnosti sítě. Například mřížkové vzory jsou malé podgrafy, které jsou v mřížce nadměrně zastoupeny. Podobně vzory aktivit jsou vzory v atributech síťových uzlů a hran, které jsou nadměrně zastoupeny vzhledem ke struktuře sítě. Analýza biologických sítí s ohledem na nemoci vedla k rozvoji síťového přístupu k nemocem a léčbě ( síťová medicína ). Nedávné příklady aplikace teorie sítí v biologii zahrnují aplikace pro pochopení buněčného cyklu . Interakce mezi fyziologickými systémy, jako je mozek , srdce , oči atd. lze prozkoumat jako fyziologickou síť .
Tyto modely kompartmentové epidemiologie jsou ty známé algoritmy předpovědět šíření pandemie ve světě v rámci infekčního obyvatelstva, zejména modelu SIR.
Kromě pandemií tento model umožňuje zachytit mnoho společenských jevů šíření / přenosu (informace, propaganda, móda atd.).
Automatické zpracování z korpusu umožnila extrakci herců a jejich vztahových sítí ve velkém měřítku. Relační data jsou poté analyzována pomocí nástrojů teorie sítě za účelem identifikace klíčových aktérů , komunit nebo klíčových komponent , jakož i obecných vlastností, jako je robustnost, strukturální stabilita celé sítě nebo centralita určitých uzlů v síti.
To automatizuje přístup zavedený kvantitativní analýzou textových dat, ve kterém jsou triády subjektu-sloveso-objekt (nebo trojice) identifikovány s dvojicemi (dyády) aktérů spojených akcí nebo dvojicemi sestávajícími z aktéra-objektu. Může to být sémantické .
Analýza elektrických systémů může být provedena pomocí teorie sítí ze dvou hlavních hledisek:
Odkazy ( analýza odkazů) je odvětví analýzy sociálních sítí , které zkoumá asociace mezi objekty analýzy. Například je možné vyšetřovat interakce podezřelého a jeho obětí ( telefonní čísla, která byla vytočena, adresy, provedené finanční transakce v daném čase), jakož i jejich rodinné vztahy během vyšetřování. Policie a forenzní vyšetřování .
Analýza odkazů poskytuje zásadní informace týkající se vztahů a asociací mezi několika objekty různých typů, které nejsou zjevné jako jediná informace.
Banky a pojišťovny stále častěji používají plně nebo částečně automatizované analýzy odkazů , zejména k odhalování podvodů ; od telekomunikačních operátorů v analýze telekomunikačních sítí ; ve zdravotnictví v epidemiologii a farmakologii ; při údržbě objednávky , vyhledávači , aby si všimli relevance (a najednou spammery pro zneužívající odkazy a podnikateli, aby optimalizovali návštěvu jejich webových stránek ), a všude jinde, kde byly analyzovány vztahy mezi různými objekty.
Odkazy jsou také odvozeny z podobnosti dočasného chování dvou uzlů. Mezi příklady patří zejména klimatické sítě v klimatologii, kde jsou vazby mezi dvěma místy (uzly) určovány například podobností srážek nebo teplotními výkyvy na těchto dvou místech.
Analýza webových odkazůNěkteré algoritmy pro hodnocení používané webovými vyhledávači používají metriky ústřednosti založené na odkazech, včetně algoritmů PageRank of Google , HITS , CheiRank a TrustRank . Analýzy odkazů se také provádějí v informačních vědách a komunikačních vědách za účelem porozumění a extrakce informačních stránek síťových na webu . Například analýza by se mohla zaměřit na propojení mezi webové stránky nebo blogy z politických činitelů . Dalším použitím je klasifikace stránek podle jejich zmínky na ostatních stránkách ( společný výskyt ).
V popisné statistice a teorii chaosu je rekurentní graf (RP) graf zobrazující pro daný okamžik časy, kdy trajektorie fázového prostoru navštěvuje přibližně stejnou oblast fázového prostoru. Matrice z opakování grafu lze považovat za přilehlosti matrice z o neorientovaného a neváženého sítě . To umožňuje analýzu časových řad pomocí měření v síti. Aplikace sahají od detekce změn rychlosti po charakterizaci dynamiky , včetně synchronizační analýzy .
Vzájemně závislá síť je systém spojených sítí, kde uzly jedné nebo více sítí závisí na uzlech jiných sítí. V reálných sítích jsou tyto závislosti posíleny vývojem moderní technologie . Závislosti mohou způsobit kaskádové selhání mezi sítěmi: relativně malá chyba může vést ke katastrofickému selhání většího systému. Tyto výpadky proudu jsou důležitou součástí demo hraje závislostí mezi sítěmi. Nedávná studie vyvinula analytický rámec pro studium kaskádových poruch v systému vzájemně závislých sítí.
Tyto modely v teorii sítě jsou základem pro pochopení interakcí v komplexních sítích empirických. Různé modely generování náhodných grafů vytvářejí síťové struktury, které lze použít k jejich porovnání se složitými sítěmi v reálném světě.
Model Erdős - Rényi , pojmenovaný podle Paula Erdőse a Alfréda Rényiho , se používá ke generování náhodného grafu, ve kterém jsou hrany definovány mezi uzly se stejnou pravděpodobností. Může být použit v pravděpodobnostním přístupu k prokázání existence grafů vyhovujících různým vlastnostem nebo k poskytnutí přesné definice toho, co vlastnost znamená pro téměř všechny grafy.
Pro vygenerování Erdős-Rényiho modelu je třeba zadat dva parametry: celkový počet vrcholů n a pravděpodobnost p, že náhodná dvojice vrcholů je spojena hranou.
Protože je model generován bez zkreslení pro konkrétní uzly, je rozdělení stupňů binomické: pro náhodně vybraný vrchol ,
V tomto modelu je koeficient shlukování je 0 SA Reporting . Chování lze rozdělit do tří oblastí:
Větší související komponenta má velkou složitost. Všechny ostatní komponenty jsou jednoduché a malé .
Modelu konfigurace trvá „sled stupňů “ nebo distribuci stupňů (který je potom použit pro generování sekvence stupňů) jako vstup, a produkuje souvisejících grafů náhodně ve všech ohledech. Jiné než pořadí ve stupních.
To znamená, že pro danou posloupnost stupňů je graf vybrán náhodně z možné sady grafů vyhovujících této posloupnosti stupňů. Stupeň z náhodně vybraného vrcholu je nezávislé a stejně rozdělené proměnná s celočíselnou hodnotu. Když konfigurace grafu obsahuje připojenou komponentu zvanou „obří“, která má nekonečnou velikost. Zbytek jeho komponent má konečnou velikost, kterou lze kvantifikovat pomocí představy o velikosti distribuce. Pravděpodobnost, že je náhodně vzorkovaný vrchol spojen s komponentou velikosti, je dána „ konvoluční silou “ (to je iterace konvoluce sama se sebou) rozložení stupňů:
w(ne)={E[k]ne-1u1∗ne(ne-2),ne>1,u(0)ne=1,{\ displaystyle w (n) = {\ begin {cases} {\ frac {\ mathbb {E} [k]} {n-1}} u_ {1} ^ {* n} (n-2), & n > 1, \\ u (0) & n = 1, \ end {cases}}}kde udává rozdělení stupňů a . Obří součást může být zničena náhodným odstraněním kritické frakce ze všech okrajů. Tento proces se nazývá perkolace na náhodných sítích .
Když je druhý moment rozložení studia je konečná ,, tento kritický okraj je dána , a průměrný vrchol k vrcholu vzdálenost za obří připojených komponent váhy logarithimically o celkové velikosti mřížky ,.
V konfiguraci modelu řízeného grafu je stupeň vrcholu dán dvěma čísly, stupněm a stupněm , a proto je rozdělení stupňů dvojrozměrné. Očekávaný počet okrajů a okrajů se proto shoduje . Konfigurační model obsahující směrovaný graf obsahuje obří komponentu , právě když
2E[kv]E[kvkven]-E[kv]E[kven2]-E[kv]E[kv2]+E[kv2]E[kven2]-E[kvkven]2>0.{\ displaystyle 2 \ mathbb {E} [k _ {\ text {in}}] \ mathbb {E} [k _ {\ text {in}} k _ {\ text {out}}] - \ mathbb {E } [k_ {\ text {in}}] \ mathbb {E} [k _ {\ text {out}} ^ {2}] - \ mathbb {E} [k _ {\ text {in}}] \ mathbb {E} [k_ {\ text {in}} ^ {2}] + \ mathbb {E} [k _ {\ text {in}} ^ {2}] \ mathbb {E} [k _ {\ text { out}} ^ {2}] - \ mathbb {E} [k _ {\ text {in}} k _ {\ text {out}}] ^ {2}> 0.} Všimněte si, že a jsou stejné, a proto jsou zaměnitelné v poslední nerovnosti. Pravděpodobnost, že náhodně vybraný vrchol patří do komponenty velikosti, je dána vztahem: hv(ne)=E[kine]ne-1u~v∗ne(ne-2),ne>1,u~v=kv+1E[kv]∑kven≥0u(kv+1,kven),{\ displaystyle h _ {\ text {in}} (n) = {\ frac {\ mathbb {E} [k_ {in}]} {n-1}} {\ tilde {u}} _ {\ text { in}} ^ {* n} (n-2), \; n> 1, \; {\ tilde {u}} _ {\ text {in}} = {\ frac {k _ {\ text {in} } + 1} {\ mathbb {E} [k _ {\ text {in}}]}} \ sum \ limity _ {k _ {\ text {out}} \ geq 0} u (k _ {\ text { in}} + 1, k _ {\ text {out}}),} pro komponentu a
pro out-komponentu.
Model malého světa navržený Wattsem a Strogatzem je model generování náhodných grafů, který vytváří grafy s vlastnostmi malého světa .
Počáteční síť se používá ke generování sítě „malého světa“ . Každý vrchol sítě je zpočátku spojen s těmito nejbližšími sousedy. Další parametr je určen jako pravděpodobnost opětovného připojení; každá hrana má pravděpodobnost, že bude znovu připojena k grafu jako náhodná hrana. Očekávaný počet opětovných připojení v tomto modelu je .
Když model Watts a Strogatz začíná s nenáhodnou síťovou strukturou, vykazuje velmi vysoký shlukovací koeficient i vysokou průměrnou délku cesty . Každé opětovné připojení pravděpodobně vytvoří zástupce mezi silně propojenými komponentami . Jak se zvyšuje pravděpodobnost opětovného připojení, shlukový koeficient klesá pomaleji než průměrná délka cesty. Vyšší hodnoty p přinutí více hran k opětovnému připojení, čímž se Watts a Strogatzův model stanou náhodnou sítí .
Model Barabasi-Albert je model náhodné sítě a bez stupnice použité k prokázání preferenčního přílohu, nebo, jinými slovy, že „bohatí bohatnou.“ V tomto modelu, hrana je více pravděpodobné, že se váže k vrcholům, které mají vyšší úroveň než oni, nebo jinými slovy: „Proč moji přátelé jsou často více populární než já.“ Modelování začíná s počátečním sítí m 0 maxima. m 0 ≥ 2 a kde by stupeň každého vrcholu v počáteční síti měl být alespoň 1, jinak vždy zůstane odpojen od zbytku sítě (vyloučeno).
V modelu BA jsou nové vrcholy přidávány do sítě jeden po druhém. Každý nový vrchol je připojen k existujícím vrcholům s pravděpodobností, která je úměrná počtu odkazů, které tento vrchol již v síti má. Formálně je pravděpodobnost p i , že nový vrchol je spojen s vrcholem i, je
kde k i je stupeň vrcholu i . Silně propojené vrcholy („ rozbočovače “) mají tendenci rychle akumulovat ještě více odkazů, zatímco vrcholy s několika odkazy pravděpodobně nebudou vybrány, aby vytvořily nový odkaz. Nové výšky mají „přednost“ spojovat se s výškami silně spojenými s ostatními.
Distribuce stupňů vyplývajících z modelu BA je bezšupinatý, zejména se jedná o moc zákon ve tvaru:
Rozbočovače ( rozbočovače ) mají centrálnost vysoká, což umožňuje, aby mezi vrcholy existovaly nejkratší cesty. Výsledkem je, že model BA má tendenci mít velmi krátké průměrné délky dráhy. Koeficient shlukování tohoto modelu má rovněž tendenci 0. Zatímco průměr D o několik modelů včetně toho Erdős a Rényiho stejně jako několik sítí „malý světa“ je úměrná log D , na BA model představuje D ~ loglogN ( ultramalých svět ). Všimněte si, že průměrná vzdálenost se liší v závislosti na průměru N.
Preferenční model připoutání umožňující vznik komunitJe-li komunita je definována v užším slova smyslu jako soubor herců a sdílené sémantické prvky, které jsou vzájemně propojeny, stačí modulovat preferenční přílohu podle předem definované míře homophilia tak jako zvýhodňovat vazby mezi vrcholy. Silně podobné , aniž by byl identické je možné vidět vznik a vývoj komunity.
Mediační preferenční model přílohy (MDA)V preferenčním modelu připojení založeném na mediaci (model zprostředkování řízeného připojení (MDA) ) přichází s novými hranami špiček , poté náhodně vybere již připojený k síti a připojí vrchol, nikoli na vrchol, ale také jeho sousedů vybráno náhodně. Pravděpodobnost, že je vybrán vrchol existujícího vrcholu, je:
Faktor je inverzní k harmonickému průměru (HMI) stupňů sousedů vrcholu . Výzkum naznačuje, že přibližně střední hodnota inverze harmonického průměru ve velkém limitu se stává konstantou, což znamená , že čím více spojů (vysoký stupeň) má vrchol, tím je pravděpodobnější získat ještě více spojů, protože lze jich dosáhnout několika způsoby prostřednictvím mediátorů, kteří v podstatě ztělesňují myšlenku připoutanosti k modelu Barabasi-Albert (BA). Je tedy vidět, že síť MDA se řídí pravidlem preferenčního připojení, ale maskovaným způsobem.
Popisuje však, že vítěz bere všechno, protože se ukázalo, že téměř z celkových vrcholů má pouze jeden stupeň, zatímco vrchol je velmi bohatý na stupeň. Jak se hodnota zvyšuje, rozdíly mezi superbohatými a chudými se zmenšují a kdy dochází k přechodu od „bohatší bohatší“ k „bohatá bohatší vazby“.
Fitness model je model vývoje sítě, to znamená, že to vyjadřuje způsob, jakým jsou vazby mezi vrcholy v průběhu času vyvíjet a závisí na tvaru vrcholů. Nejvhodnější uzly přitahují více odkazů na úkor těch méně vhodných, což zavedli Caldarelli a kol.
V tomto modelu je vytvořeno spojení mezi dvěma vrcholy s pravděpodobností danou relační funkcí adaptability příslušných vrcholů. Stupeň vrcholu je dán vztahem:
Pokud je invertibilní a rostoucí funkcí , pak je pravděpodobnostní rozdělení dáno vztahem:
V důsledku toho, je-li fitness distribuován jako silový zákon , pak budou i stupně vrcholů.
Méně intuitivně, s rychlým spojem klesá pravděpodobnost rozdělení pravděpodobnosti av a funkce odkazu
s konstantní funkcí a funkcí Heavyside dostaneme také sítě bez měřítka .
Takový model byl úspěšně použit k popisu obchodních vztahů mezi zeměmi využívajících HDP jako prostředek adaptace na různé vrcholy a takovou spojovací funkci.
V roce 1927 vytvořili WO Kermack a AG McKendrick epidemiologický model, ve kterém uvažují o dané populaci pouze se třemi oddíly (kategoriemi): zdravými , infikovanými a remitovanými . Kategorie použité v tomto modelu se skládají ze tří tříd:
Tok tohoto modelu lze vidět následovně:
Pomocí dané populace odvodili Kermack a McKendrick následující rovnici:
Z této formulace vyplynulo několik hypotéz : zaprvé, u jedince v populaci je třeba mít za to, že má stejnou pravděpodobnost nakažení chorobou jako ostatní jedinci v míře , která se považuje za míru infekce nemoci. Infikovaný jedinec tedy interaguje a je schopen přenášet nemoc na ostatní za jednotku času a zlomek kontaktů infikovaného jedincem je pravděpodobně takový . Počet nových infekcí v dané časové jednotce je :, podle míry nových infekcí (nebo těch, které zůstávají v kategorii pravděpodobné infekce) jako (Brauer & Castillo-Chavez, 2001). U druhé a třetí rovnice považujeme populaci opouštějící vnímavou kategorii za rovnou zlomku ( což představuje průměrnou míru remise a průměrnou dobu onemocnění) míře infekčních lidí, kteří tuto kategorii opouštějí. jednotka času, vstoupit do třídy uzdravených. Tyto současně se vyskytující procesy odkazují na zákon hromadné akce , což je široce přijímaná myšlenka, že míra kontaktu mezi dvěma skupinami v populaci je úměrná velikosti každé z těchto skupin (Daley & Gani, 2005). Nakonec se předpokládá, že míra infekce a remise je rychlejší než doba narození a úmrtí, a proto tento model tyto faktory ignoruje.
Podezření na infekci
Výše uvedený vzorec popisuje „sílu“ infekce pro každou vnímavou jednotku v infekční populaci, kde β je ekvivalentní rychlosti přenosu uvedené choroby.
Chcete-li sledovat změnu zranitelných osob v infekční populaci:
Nakažený k prominutí
V průběhu doby, počet nakažených kolísá: určenou hodnotu remise, zastoupené ale odečíst průměrné infekčního období , počet infekčních jedinců: a změna v době: .
Infekční období
To, zda pandemie porazí populaci, s ohledem na model SIR , závisí na hodnotě nebo „průměru lidí nakažených infikovaným jednotlivcem“
Hlavní rovnice lze popsat vývoj k neřízené sítě , kde je v každém daném období, nový vrchol se přidává do sítě, spojené s staré vrcholu (vybrané náhodně bez preference). Počáteční síť je tvořena dvěma vrcholy a dvěma spoji mezi nimi v čase , tato konfigurace je nutná pouze pro zjednodušení dalších výpočtů, pak v době, kdy má síť vrcholy a odkazy.
Hlavní rovnice pro tento typ sítě je:
kde je pravděpodobnost, že vrchol bude mít určitý stupeň v čase , a je to časový interval, během kterého byl tento vrchol přidán do sítě. Všimněte si, že pro starý summit existují pouze dva způsoby, jak mít časové odkazy :
Po zjednodušení je rozdělení stupňů :
Na základě této rozšiřující se sítě se vyvíjí model epidemie podle jednoduchého pravidla : pokaždé, když se přidá nový vrchol a po výběru starého vrcholu, který se má vázat, je rozhodnuto: určit, zda bude tento nový vrchol infikován. Klíčová rovnice tohoto epidemiologického modelu je následující:
kde představuje rozhodnutí infikovat ( ) nebo ne ( ). Vyřešením této hlavní rovnice se získá následující řešení:
Tyto sítě obvykle mají vlastnosti, které mohou být měřeny analyzovat jejich vlastnosti a charakteristiky. Chování těchto síťových vlastností často definuje síťové vzory a lze je použít k analýze kontrastu určitých vzorů. Teorie grafů lexikon obsahuje mnoho definic dalších termínů používaných v síťovém vědě .
Velikost sítě může odkazovat na počet uzlů nebo méně často na součet hran, které (u připojených grafů bez více hran) se mohou pohybovat od (strom) do (úplný graf). V případě jednoduchého grafu, kde mezi každou dvojicí vrcholů existuje nejvýše jedna hrana a kde k sobě není připojen žádný vrchol, to dává :; pro směrovaný graf (bez uzlu připojeného k sobě) :; pro orientovaný graf pro automatické přihlášení: . V případě grafu, kde může existovat více hran mezi dyád: .
Průměr sítě je nejkratší vzdálenost mezi dvěma nejvzdálenějšími uzly v síti. Jinými slovy, jakmile se vypočítá nejkratší délka cesty z každého uzlu do všech ostatních uzlů, je průměr největší ze všech vypočtených délek cesty. Průměr je reprezentativní pro lineární velikost sítě.
Průměrná vzdálenost nejkratší cestou se vypočítá hledání nejkratší cesty mezi všemi páry uzlů a při průměr všech cest v délce (délka je počet mezilehlých hran obsažené v cestě: je vzdálenost mezi dvěma hranami z graf). To ukazuje v průměru počet kroků, které je třeba provést při přechodu z jednoho člena sítě na druhého. Chování očekávané průměrné nejkratší délky cesty (tj. Stanovený průměr průměrné nejkratší délky cesty) jako funkce počtu vrcholů náhodného síťového modelu určuje, zda tento model představuje účinek malého světa; pokud definuje , model generuje malé světové sítě. Pro rychlejší než logaritmický růst model neprodukuje malé světy. Zvláštní případ je znám jako efekt ultra malého světa.
Hustotu sítě, definovanou jako poměr počtu hran k počtu možných odkazů na uzly v síti, poskytuje (v případě jednoduchých grafů) binomický koeficient , což . Další možnou rovnicí je situace, kdy jsou odkazy jednosměrné (Wasserman & Faust 1994).
Hustotu sítě, když neexistuje žádný průnik mezi hranami, definovanou jako poměr počtu hran k možnému počtu hran k uzlům v síti, poskytuje rovinný graf poskytující
Stupeň uzlu je počet hran s ním spojených. Střední stupeň úzce souvisí s hustotou sítě: (nebo, v případě směrovaného grafu :; Faktor 2 vyplývající z každé hrany v neorientovaném grafu přispívající ke stupni dvou odlišných vrcholů). V modelu náhodného grafu ER ( ) je možné vypočítat očekávanou hodnotu (rovnající se očekávané hodnotě z libovolného uzlu): náhodná hrana má k dispozici další hrany v síti, s pravděpodobností připojení ke každému . Tedy: .
Seskupení koeficient je mírou tranzitivity. To je někdy popsáno pod pravidlem: „přátelé mých přátel jsou moji přátelé“. Přesněji řečeno, seskupovací koeficient uzlu je poměr existujících spojů spojujících sousedy uzlu k maximálnímu možnému počtu těchto spojů. Koeficient seskupení pro celou síť je průměrem koeficientů seskupení všech uzlů. Vysoký koeficient shlukování pro síť je dalším ukazatelem malého světa a sociální soudržnosti.
Koeficient přeskupení i -tého vrcholu je:
when je počet sousedů prvního vrcholu a je počet spojení mezi jeho sousedy. Maximální možný počet spojení mezi sousedy je pak:
Z pravděpodobnostního hlediska je očekávaným lokálním koeficientem shlukování pravděpodobnost, že existuje spojení mezi dvěma libovolnými sousedy stejného uzlu.
Způsob, jakým je síť připojena, hraje důležitou roli v tom, jak jsou sítě analyzovány a interpretovány. Sítě jsou rozděleny do čtyř různých kategorií:
Informace o relativní důležitosti uzlů a / nebo hran v grafu lze získat pomocí opatření ústřednosti , široce používaných v oborech, jako je sociologie .
Například vlastní vektor centralita využívá charakteristických vektorů na matice přilehlosti odpovídající síti určit, které uzly mají tendenci být na často. Formálně zavedená ústřednost měří stupeň ústřednosti , ústřednost blízkosti , ústřednost mezi , ústřednost vlastního vektoru , ústřednost podgrafu a ústřednost Katze . Účel analýzy obecně určuje typ opatření centrálnosti, který se má použít. Například pokud se někdo zajímá o dynamiku sítí nebo robustnost sítě, dynamický význam uzlu je často nejrelevantnějším měřítkem z hlediska centrality. Existuje také míra ústřednosti založená na nehustotě grafu ( číslo k-jádra ).
Indexy centrálnosti jsou přesné pouze k identifikaci nejcentrálnějších uzlů. Měření jsou pro ostatní uzly v síti zřídka, pokud vůbec, užitečná. Jejich indikace jsou navíc přesné pouze v kontextu předpokládané důležitosti a v jiných kontextech bývají nespolehlivé. Omezení týkající se opatření ústřednosti vedla k vývoji obecnějších opatření. Jedním příkladem a očekávanou silou odvozenou z očekávané hodnoty infekce síly d generované uzlem je přístupnost, která využívá rozmanitost náhodných procházek k měření toho, jak přístupný je zbytek sítě z daného spouštěcího uzlu.
Koncept centrálnosti v kontextu statických sítí byl rozšířen na základě empirického a teoretického výzkumu o dynamickou ústřednost v kontextu dočasných sítí.
Tyto koncepty se používají k charakterizaci předvoleb připojení koncentrátorů ( rozbočovačů ) v síti. Tyto uzly jsou uzly s velkým počtem odkazů: o celebrity , na vrátných , významných institucí, atd Některé rozbočovače mají tendenci se připojovat k jiným rozbočovačům, zatímco jiné se vyhýbají připojování k rozbočovačům a upřednostňují připojení k slabě připojeným uzlům. Rozbočovač je assortative, když má tendenci se připojit k jiné uzly. Nesouhlasné náboje zabrání připojení dalších rozbočovačů. Pokud mají rozbočovače spojení s očekávanými náhodnými pravděpodobnostmi, říká se o nich, že jsou neutrální. Pojem assortativity se používá při analýze sociální sítě a je podobný tomu homophilia . Nesoulad je v sociálním světě vzácný a může vyplynout ze strategie optimalizace sociálního kapitálu vytvářením strukturálních děr .
Obsah složité sítě se může šířit dvěma hlavními metodami: konzervované šíření a nekonzervované šíření. V konzervovaném šíření zůstává celkové množství obsahu vstupujícího do složité sítě konstantní, jak prochází. Model konzervovaného šíření lze nejlépe představit džbánem obsahujícím pevné množství vody nalité do řady nálevek spojených trubkami. Zde džbán představuje původní zdroj a vodu, která má být vylita. Spojovací nálevky a trubice představují uzly a spojení mezi uzly. Jak voda přechází z jedné trychtýře do druhé, okamžitě zmizí z trychtýře, který byl předtím vystaven vodě. Pokud šíření není zachováno, mění se množství obsahu při vstupu a průchodu složitou sítí. Model nekonzervovaného šíření lze nejlépe představovat nepřetržitě fungujícím kohoutkem procházejícím řadou nálevek spojených trubicemi. Zde je množství vody z původního zdroje nekonečné. Dále, všechny trychtýře, které byly vystaveny vodě, nadále zažívá voda, i když prochází následujícími trychtýři. Nekonzervovaný model je nejvhodnější pro vysvětlení přenosu většiny infekčních onemocnění , neuronální excitace , šíření informací a pověstí atd.
Strukturální robustnost sítí je studována pomocí teorie perkolace . Když je kritická část uzlů (nebo odkazů) odstraněna ze sítě, síť se rozpadne na odlišné komponenty. Tento proces perkolace představuje fázový přechod poruchy řádu s kritickými exponenty . Teorie perkolace umožňuje předvídat velikost největší složky (nazývané obří složka), kritického prahu a kritických exponentů.
Problémy se sítí, které zahrnují hledání optimálního způsobu provedení daného úkolu, jsou studovány pod názvem kombinatorická optimalizace . Mezi případy, které je třeba vyřešit, patří zejména ty, které se týkají tokových sítí , problémy s nejkratší cestou , problémy v teorii dopravy , problémy s umístěním zařízení , problémy spojování , problémy přiřazení , problémy. zhutnění , stohování, směrování , kritická cesta a PERT ( Program Evaluation & Technical Review ).
Za účelem rozložení úlohy optimalizace sítě NP-difficile na dílčí úkoly se síť rozloží na relativně nezávislé podsítě.