Sekoitus kuvioita

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 11. toukokuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Sekoitusmallit viittaavat verkon yhden tyyppisen solmun systemaattiseen taipumukseen muodostaa yhteys toiseen tyyppiin. Esimerkiksi solmut voivat pyrkiä muodostamaan yhteyden muihin solmuihin, jotka ovat hyvin samanlaisia tai hyvin erilaisia. Tämä ominaisuus on melko yleinen monissa sosiaalisissa verkostoissa , vaikka se näkyy joskus myös muissa kuin sosiaalisissa verkostoissa. Sekoitusmallit liittyvät läheisesti lajitteluun ; Kuitenkin tässä artikkelissa termiä käytetään viittaamaan lajitteluun tai disassortatiiviseen sekoitukseen, riippuen todellisista topologisista tai sosiologisista tekijöistä.

Sekoita kuviotyypit

Sekoituskuviot ovat verkonlaajuinen ominaisuus, joka osoittaa solmujen taipumuksen muodostaa yhteys muihin samanlaisiin tai erilaisiin solmuihin. Sekoitus voidaan siten luokitella assortatiiviseksi tai disassortatiiviseksi. Assortatiivisella sekoituksella tarkoitetaan solmujen taipumusta yhdistää samankaltaisiin solmuihin, kun taas disassortatiivisella sekoituksella tarkoitetaan päinvastaista tapausta, jossa on kytketty hyvin erilaisia solmuja.

Parien välisten linkkien muodostukseen osallistuvien solmujen erityisominaisuudet muodostavat verkon sekoituskuviot. Esimerkiksi seksuaalisuhteiden verkostoa hallitsevat todennäköisesti miehen ja naisen siteet, kun taas ystävyyssuhteiden verkostoa voivat hallita miehen ja naisen suhteet. Erilaisten solmuominaisuuksien ryhmien tarkastelu voi siten paljastaa verkon yhteisöjä tai muita rakenteellisia ominaisuuksia. Yleensä näiden ominaisuuksien käyttämiseen on kahdenlaisia menetelmiä. Yksi niistä perustuu analyyttisiin laskelmiin generointifunktioita käyttäen . Toinen on numeerinen ja perustuu Monte Carlo -simulaatioihin kuvaajien luomista varten. [yksi]

Tutkiessaan sekoitusmalleja verkoissa MEJ Newman aloittaa luokittelemalla solmuominaisuudet kahteen luokkaan. Vaikka reaalimaailman solmujen ominaisuuksien määrä on käytännössä rajaton, ne voidaan jakaa kahteen tyyppiin: diskreetti ja skalaari/topologinen. Seuraavissa osissa määritellään näiden luokkien väliset erot ja annetaan esimerkkejä jokaisesta. Jokaiselle kategorialle Newman esitteli ja kuvaili lyhyesti verkkomalleja, joissa on sekoitus.

Sekoitus erillisten ominaisuuksien perusteella

Solmun erilliset ominaisuudet ovat kategorisia, nimellisiä tai enumeratiivisia ja usein kvalitatiivisia. Esimerkiksi rotu, sukupuoli ja seksuaalinen suuntautuminen ovat usein tutkittuja erillisiä ominaisuuksia.

Mittaakseen sekoittumista verkossa diskreettien ominaisuuksien perusteella, Newman [1] määrittelee määrän niiden reunojen suhteeksi verkossa, jotka yhdistävät tyyppiset solmut tyyppiin (katso kuva 1). $e_{ij}$ $i$ $j$ [ missä? ] . Ohjaamattomassa verkossa tämä luku on symmetrinen indekseihinsä nähden, kun taas suunnatussa verkossa se voi olla epäsymmetrinen. Se täyttää summaussäännöt: ${\displaystyle e_{ij}=e_{ji))$

\sum _{ij}{e_{ij}=1},\quad \sum _{j}{e_{ij}=a_{i}},\quad \sum _{i}{e_{ij }=b_{j}}~,

missä ja ovat tyypin solmuihin kiinnitetyn reunan kunkin päätytyypin murto-osat . $a_{{i}}$ $b_{{i}}$ $i$

Suuntaamattomissa graafisissa kaavioissa, joissa linkin päiden välillä ei ole fyysistä eroa, ts. reunojen päät ovat kaikki samaa tyyppiä, . $a_{i}=b_{i}$

Tällöin lajitelmakerroin on kahden erillisten ominaisuuksien joukon solmun samankaltaisuuden tai eron voimakkuuden mitta, joka voidaan määritellä seuraavasti:

r={\frac {\sum _{i}{e_{ii}}-\sum _{i}{a_{i}b_{i}}}{1-\sum _{i}{a_ {i}b_{i}}}}}

Kanssa

r_{min}=-{\frac {\sum _{i}{a_{i}b_{i))}{1-\sum _{i}{a_{i}b_{i))} }~.

Tässä kaavassa , jos ei ole lajitelmasekoitusta, koska tässä tapauksessa , ja jos verkko on täysin lajiteltu. Jos verkko on täysin disassortiivinen, ts. jokainen linkki yhdistää kaksi erityyppistä solmua, sitten , joka yleensä kuuluu alueeseen . Tämä alue for osoittaa, että täysin disassortiivinen verkko on yleensä lähempänä satunnaista sekoitusverkkoa kuin täysin lajitteleva verkko. Kun solmutyyppejä on useita, satunnainen sekoitus yhdistää useimmissa tapauksissa erilaisia solmuja, mikä johtaa siihen, että tällainen verkko näyttää enimmäkseen dissortatiiviselta. Siksi on luonnollista, että satunnaisen verkon arvon tulee olla lähempänä täysin dissortatiivisen verkon arvoa kuin täysin assortatiivisen verkon arvoa. $r = 0$ ${\displaystyle e_{ij}=a_{i}b_{j))$ $r=1$ $r=r_{min}$ $-1\leq r<0$ $r_{min}$ $r = 0$

Generointifunktiomenetelmä perustuu ajatukseen, että joka kerta lasketaan sopiva generointifunktio kiinnostaville jakaumille ja mahdollistaa verkon rakenteeseen liittyvän tiedon poimia niitä eriyttämällä. Olettaen, että tyyppisolmujen astejakauma ja matriisin arvo (ja siten arvot ja ) ovat tiedossa. Kuvaajien joukosta saadaan osoitetut ja verkon kollektiiviset (makroskooppiset) ominaisuudet. Yleensä generointifunktiot ja niiden ensimmäinen hetki on annettu muodossa ${\displaystyle p_{k}^{(i)))$ $i$ $e_{ij}$ $a_{{i}}$ $b_{{i}}$ ${\displaystyle p_{k}^{(i)))$ $e_{ij}$ ${\displaystyle p_{k}^{(i)))$

G_{0}^{(i)}(x_{1},...,x_{n})=\sum _{k}p_{k}^{(i)}x^{k}

G_{1}^{(i)}={\frac {1}{z_{i))}{\frac {dG_{0}^{(i))){dx)){\Bigg | }_{x=1}~,

missä:

x_{i}={\frac {\sum _{j}e_{ij}x_{j}}{\sum _{j}e_{ij}}}

– tyyppinen solmu ( määränä);

i

{\displaystyle r_{i))

{\displaystyle z_{i))

on tämän tyyppisten solmujen keskimääräinen aste.

Seuraavat jakaumat ovat erityisen kiinnostavia.

Solmujen kokonaismäärän jakautumisella, joka on saavutettavissa tyypin solmuun saapuvan reunan jälkeen, on generoiva toiminto . Samoin satunnaisesti valitusta tyyppisestä solmusta saavutettavien solmujen lukumäärän jakaumalla on generointifunktio . Tästä voidaan saada joitain verkon ominaisuuksia. Tyyppisolmulta tavoitettavissa olevien solmujen keskimääräinen määrä on $i$ $H_{1}^{(i)}(x)=xG_{1}^{(i)}[H_{1}^{(1)}(x),...,H_{1} ^{(n)}(x)]$ $i$ $H_{0}^{(i)}(x)=xG_{0}^{(i)}[H_{1}^{(1)}(x),...,H_{1} ^{(n)}(x)]$ ${\displaystyle s_{i))$ $i$

s_{i}={\frac {dH_{0}^{(i)}}{dx}}{\Bigg |}_{x=1}=1+G_{0}^{(i) '}(1){\frac {\sum _{j}e_{ij}H_{1}^{(i)'}(1)}{\sum _{j}e_{ij}}}~.

Lisäksi, jos on todennäköisyys, että tyyppinen solmu (valittu seuraamalla satunnaisesti valittua linkkiä kaaviossa) ei kuulu jättiläisklusteriin , tämän klusterin muodostavien solmujen kokonaisosuus saadaan $u_{{i}}$ $i$ $S$

S=1-\sum _{i}{\frac {a_{i}}{z_{i}}}G_{0}^{(i)}(u_{1},...,u_ {n})~.

Monte Carlon menetelmään perustuvat numeeriset laskelmat näyttävät olevan sopusoinnussa edellä kuvatuilla kaavoilla saatujen analyysitulosten kanssa.

Sekoitus skalaari- tai topologisten ominaisuuksien perusteella

Solmun skalaariominaisuudet ovat numeerisia ominaisuuksia. Ne voivat olla jatkuvia tai diskreettejä järjestysmuuttujia, kuten count. Ikä on luultavasti yksinkertaisin esimerkki, vaikka älykkyys ja hyödyketulot ovat muita ilmeisiä mahdollisia esimerkkejä. Joitakin verkon topologisia ominaisuuksia voidaan käyttää myös skalaariominaisuuksiin perustuvan sekoittumisen tutkimiseen. Erityisesti solmuaste on usein erittäin tärkeä ominaisuus kuvioiden sekoittamisessa verkoissa. [2] Topologiset skalaarisingulariteetit ovat erittäin hyödyllisiä, koska toisin kuin muut eksponentit, ne ovat aina käytettävissä. Joskus niitä käytetään karkeana indikaattorina todellisesta "sosiaalisuudesta" (sosiaalisuus, taipumus luoda sosiaalisia siteitä). [yksi]

Skalaarimuuttujien lajittelun mittaamiseksi, kuten diskreetissä tapauksessa (katso edellä), voidaan määrittää assortitiivisuuskerroin. Se voidaan mitata käyttämällä standardia Pearson-korrelaatiota , kuten Newman on osoittanut. [1] Kuvassa 2[ missä? ] , esimerkiksi Pearson-korrelaatiokertoimen laskeminen antaa r = 0,574. Tämä osoittaa melko vahvan yhteyden aviomiesten ja vaimojen iän välillä avioliiton aikana.

Vaihtoehtoinen kerroin voidaan laskea mittaamalla sekoitus huipputehojen yli. Newman [1] johti seuraavan lausekkeen

{\displaystyle r={\frac {\sum _{jk}jk(e_{jk}-q_{j}q_{k})}{\sigma _{q}^{2))))

suuntaamattomalle verkolle. Tässä kaavassa if viittaa graafin astejakaumaan (eli todennäköisyyteen, että solmulla on aste ), niin . Tämä viittaa solmun ylimäärään tai muiden kuin parhaillaan tutkittavan reunojen määrään. tarkoittaa keskimääräistä tehoa verkossa ja tarkoittaa jakauman keskihajontaa . Suunnatussa verkossa vastaava lauseke on $p_{k}$ $k$ $\textstyle q_{k}={\frac {(k+1)p_{k+1}}{z}}$ $z$ ${\displaystyle \sigma _{q))$ $q_{k}$

r={\frac {\sum _{jk}jk(e_{jk}-q_{j}^{in}q_{k}^{out})}{\sigma _{in}\sigma _ {out}}}~.

Tämä korrelaatio on positiivinen, kun solmut ovat assortatiivisia, ja negatiivinen, kun verkko on dissortatiivinen. Siten tämä mitta antaa yleiskuvan verkon sekoituskuvioista. Syvällisempi analyysi on artikkelissa Assortatiivisuus .

Funktioiden generointimenetelmä on edelleen käyttökelpoinen tässä tapauksessa, mutta löydettäviä funktioita voidaan harvoin määrittää analyyttisesti. Näin ollen numeeriset laskelmat näyttävät olevan ainoa tapa saada lopputulos. Tässä tapauksessa käytetään uudelleen Monte Carlo -menetelmää. Verkkojen tapauksessa, joiden potenssilakijakauma on astetta , , on erilainen keskiarvo, lukuun ottamatta tapausta , joka on harvinainen. [3] Sen sijaan eksponentiaalisesti lyhennetty teholakijakauma antaa jakauman tyypin yliteholle . Tämän tapauksen tulokset kuvataan alla. ${\displaystyle p_{k}\sim k^{-\tau ))$ ${\displaystyle q_{k))$ $\tau >3$ $\textstyle p_{k}={\frac {k^{-\tau }\mathrm {e} ^{-k/\kappa }}{\mathrm {Li} _{\tau }(\mathrm { e} ^{-1/\kappa })}}\ \mathrm {for} \k\geq 1$ ${\displaystyle q_{k}\sim (k+1)^{1-\tau }\mathrm {e} ^{-(k+1)/\kappa ))$

1) Vaihemuutoksen sijainti, jossa jättiläisklusteri siirtyy korkeampiin arvoihin , kun taas arvo pienenee $\kappa$ $r$ . Toisin sanoen mitä valikoivampi verkko on, sitä pienempi on reunatiheyden kynnys jättimäisen klusterin esiintymiselle.

2) Jättimäisen klusterin koko suuressa rajassa on pienempi graafille, jossa on lajiteltu sekoitus, kuin neutraaleille ja disassortatiivisille kaavioille $\kappa$ .

3) Assortatiivinen sekoitus verkossa vaikuttaa verkon vakauteen, kun solmut poistetaan . Assortatiivisten verkkojen on poistettava noin kymmenen kertaa enemmän solmuja korkeilla asteilla tuhotakseen jättiläisklusterin kuin normaalissa verkossa (tavallisella tarkoitetaan neutraalia verkkoa), kun taas disassortatiivisten verkkojen kohdalla tilanne on päinvastoin. ne ovat herkempiä kuin neutraalit korkealaatuisten solmujen poistamiselle.

Tämä tulos verkon stabiilisuuden riippuvuudesta solmusekoituksesta voidaan selittää seuraavasti. Määritelmän mukaan assortatiivisten verkkojen korkean asteen solmut yleensä muodostavat ydinryhmän niiden välille. Tällainen ydinryhmä tarjoaa verkon vakauden keskittämällä kaikki näennäiset kohdesolmut yhteen kaavion yhteen osaan. Näiden korkean asteen solmujen poistaminen on edelleen yksi tehokkaimmista tavoista tuhota verkkoyhteyksiä, mutta vähemmän tehokasta (verrattuna neutraaliin verkkoon), koska poistamalla ne kaikki samasta kaavion osasta emme hyökkää verkon muita osia vastaan. kaavio. Jos nämä muut osat ovat stabiileja yksinään, jättiläisklusteri säilyy, vaikka korkean asteen solmut katoavat. Toisaalta verkot, joissa on disassortatiivista sekoittumista, ovat erityisen herkkiä korkean asteen solmujen poistamiselle, koska nämä solmut ovat hajallaan kaukana toisistaan koko verkossa, joten niihin hyökkääminen on kuin hyökkää kaikkia verkon osia samanaikaisesti.

Esimerkit ja sovellukset

Tyypillinen sekoitusmallien sovellus on taudin leviämisen tutkimus. Esimerkiksi monet tutkimukset käyttävät sekoitusta AIDSin ja muiden tarttuvien tautien leviämisen tutkimiseen. [4] [5] [6] Näissä artikkeleissa havaitaan vahva yhteys sekoittumismallien ja taudin leviämisnopeuden välillä. Tulokset voivat olla hyödyllisiä myös reaalimaailman verkkojen kasvun mallintamiseen, kuten esimerkiksi [7] , tai yhteisöjen löytämiseen verkoista.

Muistiinpanot

↑ 1 2 3 4 5 Newman, MEJ (2003-02-27). "Kuvioiden sekoittaminen verkoissa". Fyysinen arvostelu E. 67 (2): 026126. arXiv : cond-mat/0209450 . Bibcode : 2003PhRvE..67b6126N . DOI : 10.1103/physreve.67.026126 . ISSN 1063-651X . PMID 12636767 .
↑ Newman, MEJ (2002-10-28). "Assortative Mixing in Networks". Physical Review Letters . 89 (20): 208701. arXiv : cond-mat/0205405 . Bibcode : 2002PhRvL..89t8701N . DOI : 10.1103/physrevlett.89.208701 . ISSN 0031-9007 . PMID 12443515 .
↑ Albert, Reka; Barabasi, Albert-Lászlo (30.1.2002). "Monimutkaisten verkkojen tilastollinen mekaniikka". Modernin fysiikan arvostelut . 74 (1): 47-97. arXiv : cond-mat/0106096 . Bibcode : 2002RvMP...74...47A . DOI : 10.1103/revmodphys.74.47 . ISSN 0034-6861 .
↑ Aral, SO; Hughes, JP; Stoner, B; Whittington, W; Handsfield, HH; Anderson, R.M.; Holmes, KK (1999). "Seksuaaliset sekoittumismallit gonokokki- ja klamydiainfektioiden leviämisessä" . American Journal of Public Health . American Public Health Association. 89 (6): 825-833. DOI : 10.2105/ajph.89.6.825 . ISSN 0090-0036 . PMC 1508665 . PMID 10358670 .
↑ Garnett, Geoffrey P.; HUGHES, James P.; Anderson, Roy M.; Stoner, Bradley P.; Aral, Sevgi O.; et ai. (1996). "Seksuaalisesti tarttuvien tautien klinikoilla käyvien potilaiden seksuaaliset sekoittumismallit." Sukupuolitaudit . Ovid Technologies (Wolters Kluwer Health). 23 (3): 248-257. DOI : 10.1097/00007435-199605000-00015 . ISSN 0148-5717 . PMID 8724517 .
↑ Ford, Kathleen; Sohn, Woosung; Lepkowski, James (2002). "American Adolescents: Sexual Mixing Patterns, Bridge Partners, and Concurrency" . Sukupuolitaudit . Ovid Technologies (Wolters Kluwer Health). 29 (1): 13-19. DOI : 10.1097/00007435-200201000-00003 . ISSN 0148-5717 . PMID 11773873 .
↑ Catanzaro, Michele; Caldarelli, Guido; Pietronero, Luciano (2004). "Sosiaalisen verkoston kasvu assortatiivisella sekoituksella". Physica A: Tilastollinen mekaniikka ja sen sovellukset . Elsevier BV. 338 (1-2): 119-124. Bibcode : 2004PhyA..338..119C . DOI : 10.1016/j.physa.2004.02.033 . ISSN 0378-4371 .