Klaszterezési együttható
A gráfelmélet és szociális háló elemzés , a clustering együttható grafikonja (más néven a együtthatója agglomeráció , kapcsolat , csoportosítás , aggregáció vagy tranzitivitás ), olyan intézkedés a csoportosítás a csomópontok a hálózatban. Pontosabban, ez az együttható annak a valószínűsége, hogy két csomópont összekapcsolódik, tudva, hogy van egy közös szomszédjuk.
Ez a közösségi hálózatokban vizsgált paraméterek egyike : a barátaim barátai az én barátaim?
Definíciók
A fürtözési együtthatónak két különböző meghatározása van : globális és helyi változat.
Globális együttható
A teljes klaszterezési együtthatót a következők határozzák meg:
VS=3×|háromszögek||pár különálló szomszéd|{\ displaystyle C = {\ frac {3 \ szor | {\ mbox {háromszögek}} |} {| {\ mbox {különálló szomszédok párja}} |}}}}ha egy háromszög egy klikk három csomópont.
A fokozatú csomópont elkülönülő szomszédjainak párjainak száma megegyezik , így kapjuk meg:
d{\ displaystyle d}(d2){\ displaystyle {d \ select 2}}
VS=3×|háromszögek|∑én∈V(dén2),{\ displaystyle C = {\ frac {3 \ alkalommal | {\ mbox {háromszögek}} |} {\ sum _ {i \ in V} {d_ {i} \ select 2}}},}hol van a csomópont mértéke és a gráf csomópontja.
dén{\ displaystyle d_ {i}}én{\ displaystyle i}V{\ displaystyle V}
Akkor és csak akkor, ha a gráf legalább 3 méretű klikkek halmaza ( teljes gráf, ha a gráf csatlakoztatva van).
VS≤1{\ displaystyle C \ leq 1}
Helyi együttható
Egy csomópont helyi fürtözési együtthatója a következő :
én{\ displaystyle i}
VSén=|csúcs háromszögek én||pár különálló szomszédja én|,{\ displaystyle C_ {i} = {\ frac {| {\ mbox {csúcs háromszögek}} i |} {| {\ mbox {}} i |}} külön szomszédjainak párjai,}van
VSén=|csúcs háromszögek én|(dén2).{\ displaystyle C_ {i} = {\ frac {| {\ mbox {csúcs háromszögek}} i |} {d_ {i} \ select 2}}.}Az összekapcsolt szomszédok párjának a töredéke, amely megegyezés szerint 0-val egyenlő .
dén≤1{\ displaystyle d_ {i} \ leq 1}
Akkor és csak akkor, ha a csomópont és szomszédsága legalább 3 csomópontból álló klikket alkot .
VSén≤1{\ displaystyle C_ {i} \ leq 1}én{\ displaystyle i}
A helyi együtthatók átlagának figyelembe vételével megkapjuk az átlagos helyi együtthatót:
VS¯=∑én∈VVSén|V|{\ displaystyle {\ bar {C}} = {\ frac {\ sum _ {i \ in V} C_ {i}} {| V |}}}.
Akkor is , csak akkor, ha a grafikon legalább 3 méretű klikkek halmaza .
VS¯≤1{\ displaystyle {\ bar {C}} \ leq 1}
Tulajdonságok és változatok
A két változat kapcsolata és értelmezése
A globális együtthatót a helyi együtthatók alapján fejezzük ki:
VS{\ displaystyle C}
VS=∑én∈V(dén2)VSén∑én∈V(dén2).{\ displaystyle C = {\ frac {\ sum _ {i \ in V} {d_ {i} \ select 2} C_ {i}} {\ sum _ {i \ in V} {d_ {i} \ select 2 }}}.}Ezért a helyi együtthatók súlyozott átlaga , amely eltér az átlagos helyi együtthatótól , kivéve a speciális eseteket ( például rendszeres grafikon ). A magas fokú csomóknak tehát nagyobb a súlyuk, mint az alacsony fokú csomóknak. A súlyok abból adódnak, hogy egy csomópontot a szomszédos párok számának arányában választanak ki, így a globális klaszterezési együtthatót annak a valószínűségének értelmezik, hogy két külön csomópont kapcsolódik, tudván, hogy van egy közös szomszédjuk.
VS¯{\ displaystyle {\ bar {C}}}VS{\ displaystyle C}
Kifejezés a szomszédsági mátrixból
Figyelembe véve a grafikon szomszédsági mátrixát , egy bináris mátrixot, amelynek bemenete egyenlő 1-vel, és csak akkor, ha a csomópontok szomszédok, a fürtözési együtthatót írják:
NÁL NÉL{\ displaystyle A}én,j{\ displaystyle i, j}én,j{\ displaystyle i, j}
VS=∑én≠j≠kNÁL NÉLénjNÁL NÉLénkNÁL NÉLjk∑én≠j≠kNÁL NÉLénjNÁL NÉLénk.{\ displaystyle C = {\ frac {\ sum _ {i \ neq j \ neq k} A_ {ij} A_ {ik} A_ {jk}} {\ sum _ {i \ neq j \ neq k} A_ {ij } A_ {ik}}}.}Valóban, a számláló megegyezik a háromszögek számának 6-szorosával, a nevező pedig egyenlő .
∑én∈Vdén(dén-1){\ displaystyle \ sum _ {i \ in V} d_ {i} (d_ {i} -1)}
Hurkok ( nulla átló ) hiányában a számláló a mátrix átlós elemeinek összege, a nevező pedig a mátrix nem átlós elemeinek összege .
NÁL NÉL{\ displaystyle A}NÁL NÉL3{\ displaystyle A ^ {3}}NÁL NÉL2{\ displaystyle A ^ {2}}
Változatok
Az együtthatónak vannak olyan változatai, amelyek alkalmasak bizonyos típusú grafikonokra, például súlyozott grafikákra vagy kétoldalas grafikonokra .
Modell
A Watts-Strogatz modell lehetővé teszi véletlenszerű grafikonok előállítását, amelyek mind magas fürtözési együtthatóval, mind az úgynevezett kis világtulajdonsággal rendelkeznek . Ez a két tulajdonság a nagy valós grafikonokra jellemző, például a közösségi hálózatok által alkotott.
Történelmi
A globális tényező gyakran tulajdonítják Barrat és Weigt a cikkhez A tulajdonságait kis világ hálózati modellek 2000-ben közzétett Az átlagos lokális tényező annak tulajdonítják, hogy Watts és Strogatz, a cikkhez kollektív dinamikája „kis világ” hálózatok re 1998.
Lásd is
Megjegyzések és hivatkozások
-
Mark EJ Newman , „ A komplex hálózatok felépítése és funkciója ”, SIAM áttekintés , SIAM, vol. 45, n o 2
2003, P. 167–256
-
A. Barrat, M. Barthelemy, R. Pastor-Satorras és A. Vespignani, „ A komplex súlyozott hálózatok architektúrája ”, Proceedings of the National Academy of Sciences , vol. 101, n o 11,
2004, P. 3747-3752 ( PMID 15007165 , PMCID 374315 , DOI 10.1073 / pnas.0400087101 , arXiv cond-mat / 0311416 )
-
M. Latapy, C. Magnien és N. Del Vecchio, „ A nagy kétmódú hálózatok elemzésének alapfogalmai ”, Social Networks , vol. 30, n o 1,
2008, P. 31-48 ( DOI 10.1016 / j.socnet.2007.04.006 )
-
Alain Barrat és Martin Weigt , „ A kis világ hálózati modelljeinek tulajdonságairól ”, The European Physical Journal B-Condensed Matter and Complex Systems , Springer, vol. 13, n o 3,
2000, P. 547-560
-
Duncan J. Watts és Steven H Strogatz , „A kis világhálózatok kollektív dinamikája ”, Nature , Nature Publishing Group, vol. 393, n ° 6684,
1998, P. 440-442
-
Barabási Albert-László, hálózat Science ,2016
-
Például ( Newman 2003 ) és ( Porter 2014 )
Bibliográfia
- (en) Mark EJ Newman , „ A komplex hálózatok felépítése és funkciója ” , SIAM áttekintés , SIAM, vol. 45, n o 22003, P. 167–256
Külső linkek
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">