Koeficient shlukování
V teorii grafů a v analýze sociálních sítí je shlukovací koeficient grafu (nazývaný také koeficient aglomerace , připojení , seskupování , agregace nebo tranzitivita ) měřítkem seskupení uzlů v síti. Přesněji řečeno, tento koeficient je pravděpodobnost, že jsou dva uzly spojeny s vědomím, že mají společného souseda.
Toto je jeden z parametrů studovaných na sociálních sítích : jsou přátelé mých přátel mými přáteli?
Definice
Existují dvě různé definice klastrového koeficientu : globální verze a místní verze.
Globální koeficient
Celkový koeficient shlukování je definován jako:
VS=3×|trojúhelníky||dvojice odlišných sousedů|{\ displaystyle C = {\ frac {3 \ krát | {\ mbox {trojúhelníky}} |} {| {\ mbox {páry odlišných sousedů}} |}}}![{\ displaystyle C = {\ frac {3 \ krát | {\ mbox {trojúhelníky}} |} {| {\ mbox {páry odlišných sousedů}} |}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f20894d89dcb174b0752cf208d2843bf45674ce2)
kde trojúhelník je klika tří uzlů.
Počet párů odlišných sousedů uzlu stupně, který se rovná , získáme:
d{\ displaystyle d}
(d2){\ displaystyle {d \ vyberte 2}}![{\ displaystyle {d \ vyberte 2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a33c7eb0e5fc6369e046b1b50f1a5d1059e841fc)
VS=3×|trojúhelníky|∑i∈PROTI(di2),{\ displaystyle C = {\ frac {3 \ krát | {\ mbox {trojúhelníky}} |} {\ součet _ {i \ ve V} {d_ {i} \ vyberte 2}}},}![{\ displaystyle C = {\ frac {3 \ krát | {\ mbox {trojúhelníky}} |} {\ součet _ {i \ ve V} {d_ {i} \ vyberte 2}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1bea0045a300bf77100f3efcb6ff255940311d87)
kde je stupeň uzlu a množina uzlů grafu.
di{\ displaystyle d_ {i}}
i{\ displaystyle i}
PROTI{\ displaystyle V}![PROTI](https://wikimedia.org/api/rest_v1/media/math/render/svg/af0f6064540e84211d0ffe4dac72098adfa52845)
Máme , s rovností právě tehdy, když je graf množinou klik s velikostí alespoň 3 ( úplný graf, pokud je graf připojen).
VS≤1{\ displaystyle C \ leq 1}![C \ leq 1](https://wikimedia.org/api/rest_v1/media/math/render/svg/149c808c02f06ecc8c11a1f2ce6bf58da7a3a039)
Místní koeficient
Koeficient lokálního shlukování uzlu je definován jako:
i{\ displaystyle i}![i](https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20)
VSi=|vrcholové trojúhelníky i||dvojice odlišných sousedů i|,{\ displaystyle C_ {i} = {\ frac {| {\ mbox {vrcholové trojúhelníky}} i |} {| {\ mbox {páry odlišných sousedů}} i |}},}![{\ displaystyle C_ {i} = {\ frac {| {\ mbox {vrcholové trojúhelníky}} i |} {| {\ mbox {páry odlišných sousedů}} i |}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97fe8dda2ff3fd27075db5d3d393c4cc3b9ced36)
je
VSi=|vrcholové trojúhelníky i|(di2).{\ displaystyle C_ {i} = {\ frac {| {\ mbox {vrcholové trojúhelníky}} i |} {d_ {i} \ zvolte 2}}.}![{\ displaystyle C_ {i} = {\ frac {| {\ mbox {vrcholové trojúhelníky}} i |} {d_ {i} \ zvolte 2}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4de965b006fd6fb1850fc0378db279e53dd370b9)
Je to zlomek jeho párů spojených sousedů, rovný 0, pokud podle konvence.
di≤1{\ displaystyle d_ {i} \ leq 1}![{\ displaystyle d_ {i} \ leq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e662be6ca512346a408782351c80c15272075a57)
Máme , s rovností právě tehdy, když uzel a jeho okolí tvoří kliku alespoň 3 uzlů.
VSi≤1{\ displaystyle C_ {i} \ leq 1}
i{\ displaystyle i}![i](https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20)
Vezmeme-li průměr z místních koeficientů, získáme průměrný místní koeficient:
VS¯=∑i∈PROTIVSi|PROTI|{\ displaystyle {\ bar {C}} = {\ frac {\ součet _ {i \ ve V} C_ {i}} {| V |}}}![{\ displaystyle {\ bar {C}} = {\ frac {\ součet _ {i \ ve V} C_ {i}} {| V |}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/734d503849ad08bac863ec1c6af70ab0bb5d1a16)
.
Rovněž máme rovnost právě tehdy, když je graf množinou klik s velikostí alespoň 3.
VS¯≤1{\ displaystyle {\ bar {C}} \ leq 1}![{\ displaystyle {\ bar {C}} \ leq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/618437ae70aa52c0881b322394c9859cac4e4680)
Vlastnosti a varianty
Vztah mezi těmito dvěma verzemi a interpretací
Globální koeficient je vyjádřen z místních koeficientů jako:
VS{\ displaystyle C}![VS](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
VS=∑i∈PROTI(di2)VSi∑i∈PROTI(di2).{\ displaystyle C = {\ frac {\ součet _ {i \ ve V} {d_ {i} \ zvolit 2} C_ {i}} {\ součet _ {i \ ve V} {d_ {i} \ zvolit 2 }}}.}![{\ displaystyle C = {\ frac {\ součet _ {i \ ve V} {d_ {i} \ zvolit 2} C_ {i}} {\ součet _ {i \ ve V} {d_ {i} \ zvolit 2 }}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7a80bdee22efc08ed26ff3e22647aad04cef2ef)
Jedná se tedy o vážený průměr místních koeficientů, který se liší od průměrného místního koeficientu , s výjimkou zvláštních případů ( například pravidelný graf ). Uzly vysokého stupně proto mají větší váhu než uzly nízkého stupně. Váhy sestupují k výběru uzlu v poměru k počtu jeho párů odlišných sousedů, takže globální shlukovací koeficient je interpretován jako pravděpodobnost, že dva odlišné uzly jsou spojeny s vědomím, že mají společného souseda.
VS¯{\ displaystyle {\ bar {C}}}
VS{\ displaystyle C}![VS](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
Výraz z matice sousedství
Poukazem na sousednosti matice grafu, binární matricí, jejíž vstup je rovno 1, jestliže a pouze v případě, že uzly jsou sousedy, koeficient shlukování je psáno:
NA{\ displaystyle A}
i,j{\ displaystyle i, j}
i,j{\ displaystyle i, j}![já, j](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4cbf8bbc622154cda8208d6e339495fe16a1f9a)
VS=∑i≠j≠kNAijNAikNAjk∑i≠j≠kNAijNAik.{\ displaystyle C = {\ frac {\ součet _ {i \ neq j \ neq k} A_ {ij} A_ {ik} A_ {jk}} {\ součet _ {i \ neq j \ neq k} A_ {ij } A_ {ik}}}.}![{\ displaystyle C = {\ frac {\ součet _ {i \ neq j \ neq k} A_ {ij} A_ {ik} A_ {jk}} {\ součet _ {i \ neq j \ neq k} A_ {ij } A_ {ik}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15bce3de44ffe1b9ced272c199115efd92eedb98)
Ve skutečnosti se čitatel rovná šestinásobku počtu trojúhelníků a jmenovatel se rovná .
∑i∈PROTIdi(di-1){\ displaystyle \ sum _ {i \ ve V} d_ {i} (d_ {i} -1)}![{\ displaystyle \ sum _ {i \ ve V} d_ {i} (d_ {i} -1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9f2155148719e258727642bc5fddeddc618df78)
Při absenci smyček ( nulová úhlopříčka ) je čitatel součtem diagonálních prvků matice a jmenovatelem součet nediagonálních prvků matice .
NA{\ displaystyle A}
NA3{\ displaystyle A ^ {3}}
NA2{\ displaystyle A ^ {2}}![{\ displaystyle A ^ {2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a6f30e4c77b5a5e1e49ed2592e144389eade5ba)
Varianty
Existují verze koeficientu vhodné pro určité typy grafů, jako jsou vážené grafy nebo bipartitní grafy .
Modelka
Modelu Watts-Strogatz je to možné pro generování náhodných grafů, který má jak vysoký koeficient shlukování a takzvaný malý svět majetku . Tyto dvě vlastnosti jsou charakteristické pro velké reálné grafy, jako jsou například ty, které tvoří sociální sítě.
Historický
Globální koeficient je často přičítán Barratovi a Weigtovi za článek O vlastnostech modelů malých sítí publikovaných v roce 2000. Místní průměrný koeficient je přičítán Wattsovi a Strogatzovi, u článku Kolektivní dynamika sítí „malého světa“ z 1998.
Podívejte se také
Poznámky a odkazy
-
Mark EJ Newman , „ Struktura a funkce komplexních sítí “, recenze SIAM, SIAM, sv. 45, n O 2
2003, str. 167-256
-
A. Barrat, M. Barthelemy, R. Pastor-Satorras a A. Vespignani, „ Architektura komplexních vážených sítí “, Sborník Národní akademie věd , sv. 101, n o 11,
2004, str. 3747-3752 ( PMID 15007165 , PMCID 374315 , DOI 10.1073 / pnas.0400087101 , arXiv cond-mat / 0311416 )
-
M. Latapy, C. Magnien a N. Del Vecchio, „ Základní pojmy pro analýzu velkých dvourežimových sítí “, Social Networks , sv. 30, n o 1,
2008, str. 31–48 ( DOI 10.1016 / j.socnet.2007.04.006 )
-
Alain Barrat a Martin Weigt , „ O vlastnostech síťových modelů malého světa “, The European Physical Journal B-Condensed Matter and Complex Systems , Springer, sv. 13, n o 3,
2000, str. 547-560
-
Duncan J. Watts a Steven H Strogatz , „ Kolektivní dynamika sítí „ malého světa “, Nature , Nature Publishing Group, sv. 393, n O 6684,
1998, str. 440-442
-
Albert-Laszlo Barabasi, síťová věda ,2016
-
Například v ( Newman 2003 ) a ( Porter 2014 )
Bibliografie
- (en) Mark EJ Newman , „ The structure and function of complex networks “ , SIAM review , SIAM, vol. 45, n O 22003, str. 167-256
externí odkazy
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">