Coefficiente di clustering: differenze tra le versioni

Versione delle 20:24, 26 lug 2014

Versione attuale delle 19:04, 15 mar 2025

(20 versioni intermedie di 11 utenti non mostrate)

Riga 1:

Nella [[teoria dei grafi]], il '''coefficiente di clustering''' (o '''transitività''') è la misura del grado in cui i [[Vertice (teoria dei grafi)|nodi]] di un [[grafo]] tendono ad essere connessi fra loro.

L'evidenza suggerisce che nella maggiorpartemaggior parte delle reti del mondo reale, e in particolare nelle [[reti sociali]], i nodi tendono a creare gruppi fortemente uniti e caratterizzati da una densità di collegamenti relativamente alta; il coefficiente di clustering delle reti reali, tende quindi, dende ad essere maggiore rispetto a quello didei grafi in cui i collegamenti sono generati casualmente.<ref>{{CiteCita journalpubblicazione|author autore= P. W. Holland, S. Leinhardt|title titolo= Transitivity in structural models of small groups|year anno= 1971|journal rivista= Comparative Group Studies|volume = 2|pages pp= 107&ndash;-124}}</ref><ref name=WattsStrogatz1998>{{CiteCita journalpubblicazione|author autore= [[Duncan Watts|D. J. Watts]], [[Steven Strogatz|S. H. Strogatz]]|title titolo= Collective dynamics of 'small-world' networks|year anno= 1998|url = httphttps://www.nature.com/nature/journal/v393/n6684/full/393440a0.html|journal rivista= [[Nature (journal)|Nature]]|volume = 393|pages pp= 440&ndash;-442|month mese= Junegiugno|doi = 10.1038/30918|pmid = 9623998|issue numero= 6684|bibcode=1998Natur.393..440W}}</ref>

Può essere misurato in due modi diversi: globale e locale. Quello globale descrive in generale l'intensità del fenomeno di clustering nella rete, mentre quella locale riguarda il livello di radicamento dei singoli nodi.

== Coefficiente di clustering globalelocale ==

== Local clustering coefficient ==

[[ImageFile:Clustering coefficient example.svg|thumb|upright=0.7|Esempio di coefficiente di clustering localeinlocale in un grafo non orientato:<br />1. Nel primo caso, i collegamenti fra i vicini del nodo blu sono tre su tre, quindi il coefficiente risulta essere 1.<br />2. Nel secondo caso, i collegamenti sono uno su tre, quindi il coefficiente è 1/3.<br />3. Nel terzo caso i collegamenti sono inesistenti, quindi il coefficiente è nullo.]]

Il '''coefficiente di clustering locale''' di un [[Vertice (teoria dei grafi)|nodo]] in un grafo è una misura di quanto i suoi vicini tendano a formare una [[Cricca (teoria dei grafi)|cricca]] (o un [[grafo completo]]). [[Duncan J. Watts]] e [[Steven Strogatz]] introdussero questa misura nel 1998 per determinare se un grafo sia o meno una rete rientrante nella [[teoria del mondo piccolo]].

Il '''coefficiente di clustering locale'''

The '''local clustering coefficient''' of a [[vertex (graph theory)|vertex]] (node) in a [[Graph (mathematics)|graph]] quantifies how close its [[Neighbourhood (graph theory)|neighbors]] are to being a [[Clique (graph theory)|clique]] (complete graph). [[Duncan J. Watts]] and [[Steven Strogatz]] introduced the measure in 1998 to determine whether a graph is a [[small-world network]].

AUn graphgrafo <math>G=(V,E)</math> formallyconsiste consistsformalmente ofdi aun set of verticesinsieme <math>V</math> anddi avertici sete ofun edgesinsieme <math>E</math> betweendi themcollegamenti. AnUn edgecollegamento <math>e_{ij}</math> connectsconnette vertexun vertice <math>v_i</math> withcon un vertexvertice <math>v_j</math>.

The [[Neighbourhood (graph theory)|neighbourhood]] L'insieme <math> N_i </math> fordei avicini vertexdi un vertice <math>v_i</math> isè definito definedcome asl'insieme itsdei immediatelynodi connecteddirettamente neighboursconnessi asad followsesso:

: <math>N_i = \{v_j : e_{ij} \in Eleft \andlangle e_{ji}, e_{ij} \right \rangle \in E^2\}.</math>

We defineDefiniamo <math>k_i</math> ascome thela number[[cardinalità]] of vertices,di <math>|N_i|</math>, inovvero theil neighbourhood,numero di vicini di un vertice <math>N_iv_i</math>, of a vertex.

:<dfn>Il coefficiente di clustering locale <math>C_i</math> di un vertice <math>v_i</math> è dato dal numero di collegamenti fra i membri di <math>N_i</math> fratto il numero di collegamenti potenziali fra loro.</dfn>

The local clustering coefficient <math>C_i</math> for a vertex <math>v_i</math> is then given by the proportion of links between the vertices within its neighbourhood divided by the number of links that could possibly exist between them. For a directed graph, <math>e_{ij}</math> is distinct from <math>e_{ji}</math>, and therefore for each neighbourhood <math>N_i</math> there are <math>k_i(k_i-1)</math> links that could exist among the vertices within the neighbourhood (<math>k_i</math> is the number of neighbors of a vertex). Thus, the '''local clustering coefficient for directed graphs''' is given as <ref name=WattsStrogatz1998 />

In un [[grafo orientato]], <math>e_{ij}</math> è distinto da <math>e_{ji}</math>, dunque per ogni <math>N_i</math> ci sono <math>k_i(k_i-1)</math> collegamenti possibili fra i suoi membri. Di conseguenza, il coefficiente di clustering locale per grafi orientati è dato da:<ref name=WattsStrogatz1998/>

: <math>C_i = \frac{|\{e_{jk}: v_j,v_k \in N_i, e_{jk} \in E\}|}{k_i(k_i-1)}.</math>

AnLa undirectedproprietà graphcaratteristica hasdi theun propertygrafo thatnon orientato è invece che <math>e_{ij}</math> ande <math>e_{ji}</math> aresono consideredconsiderati identical. Thereforeidentici, ifdunque aper vertexogni <math>v_iN_i</math> hasci <math>k_i</math> neighbours,sono <math>\frac{k_i(k_i-1)}{2}</math> edgescollegamenti couldpossibili existfra amongi thesuoi verticesmembri. withinDi theconseguenza, neighbourhood. Thus,il thecoefficiente '''localdi clustering coefficientlocale forper undirectedgrafi graphs'''non canorientati beè defineddato asda:

: <math>C_i = \frac{2\cdot|\{e_{jk}: v_j,v_k \in N_i, e_{jk} \in E\}|}{k_i(k_i-1)}.</math>

== Coefficiente di clustering globale ==

: <math>C_i = \frac{2|\{e_{jk}: v_j,v_k \in N_i, e_{jk} \in E\}|}{k_i(k_i-1)}.</math>

Il concetto di '''coefficiente di clustering globale''' è basato su triple di nodi. Una tripla consiste di tre nodi connessi da due (tripla aperta) o tre (tripla chiusa) collegamenti. Ogni tripla è incentrata su un nodo. Un triangolo consiste di tre triple chiuse incentrate sui tre stessi nodi che le compongono.

Il coefficiente di clustering globale è, dunque, il numero di triple chiuse (o 3 volte il numero di triangoli) fratto il numero totale di triple (somma di quelle aperte e chiuse). Il primo tentativo di misurarlo fu effettuato da [[Robert Duncan Luce|Robert D. Luce]] e Albert D. Perry (1949).<ref>{{CiteCita journalpubblicazione|author autore= [[Robert Duncan Luce|R. D. Luce]], A. D. Perry|title titolo= A method of matrix analysis of group structure|year anno= 1949|journal rivista= Psychometrika|volume = 14|pages pp= 95&ndash;-116|doi = 10.1007/BF02289146|issue numero= 1|pmid=18152948}}</ref> Questo metodo può essere applicato sia alleai retigrafi orientateorientati che non orientate (often called transitivity)orientati.<ref>Stanley Wasserman, Kathrine Faust, 1994. ''Social Network Analysis: Methods and Applications.'', p. 243. Cambridge: Cambridge University Press.</ref>

Let <math>\lambda_G(v)</math> be the number of triangles on <math>v \in V(G)</math> for undirected graph <math>G</math>. That is, <math>\lambda_G(v)</math> is the number of subgraphs of <math>G</math> with 3 edges and 3 vertices, one of which is <math>v</math>. Let <math>\tau_G(v)</math> be the number of triples on <math>v \in G</math>. That is, <math>\tau_G(v)</math> is the number of subgraphs (not necessarily induced) with 2 edges and 3 vertices, one of which is <math>v</math> and such that <math>v</math> is incident to both edges. Then we can also define the clustering coefficient as

Watts e Strogatz, invece, definirono il coefficiente di clustering come la media dei coefficienti locali:<ref>{{CiteCita journalpubblicazione|authorautore=[[Duncan Watts|D. J. Watts]], [[Steven Strogatz|S. H. Strogatz]]|titletitolo=Figure 2 : Collective dynamics of 'small-world' networks|yearanno=1998|url=httphttps://www.nature.com/nature/journal/v393/n6684/fig_tab/393440a0_F2.html|journalrivista=[[Nature (journal)|Nature]]|volume=393|pagespp=440&ndash;-442|monthmese=Junegiugno|doi=10.1038/30918|pmid=9623998|issuenumero=6684|bibcode=1998Natur.393..440W}}</ref>

: <math>C_i = \frac{\lambda_G(v)}{\tau_G(v)}.</math>

:<dfn>Supponiamo che un nodo <math>v</math> abbia <math>k_v</math> vicini; allora possono esistere massimo <math>k_v(k_v - 1)/2</math> collegamenti fra loro (ciò accade quando tutti i vicini di <math>v</math> sono connessi fra loro). Denotando con <math>C_v</math> la frazione di tali collegamenti che effettivamente esiste, si definisce <math>C</math> come la media dei <math>C_v</math> fratto il numero di nodi.</dfn>

Quest'ultima definizione è equivalente alla prima se si utilizza la [[media ponderata]], pesando ogni <math>C_v</math> con il numero di triple in cui il nodo è centrale:

It is simple to show that the two preceding definitions are the same, since

:<math>C = \frac{3\cdot n_\Delta(G)}{n_\land(G)} = \frac{\sum_{i=1}^{n} (C_i \cdot w_i)}{\sum_{i=1}^{n} w_i}</math>.

Dove:

*<math>n_\Delta(G)</math> è il numero di triangoli del grafo;

*<math>n_\land(G)</math> è il numero complessivo di triple del grafo;

*<math>w_i</math> è il peso del vertice <math>v_i</math> (numero di triple in cui il nodo è centrale);

Notare che <math>\sum_{i=1}^{n} w_i \equiv n_\land(G)</math>.

=== Esempio ===

: <math>\tau_G(v) = C({k_i},2) = \frac{1}{2}k_i(k_i-1).</math>

[[File:6n-graf-clique.svg|thumb|Grafo non orientato a sei nodi. I vertici cerchiati in rosso sono centri di triple chiuse.]]

Nell'esempio sulla destra c'è un solo triangolo, formato dai vertici 1, 2 e 5. Le caratteristiche del grafo sono le seguenti:

{| class="wikitable" style="text-align:center"

! Vertice !! Collegamenti<br />fra vicini !! Peso !! Triple in cui il nodo è centrale

|-

| 1 || 1 || 1 || ⟨2,1,5⟩

|-

| 2 || 1/3 || 3 || ⟨1,2,3⟩, ⟨1,2,5⟩, ⟨3,2,5⟩

|-

| 3 || 0 || 1 || ⟨2,3,4⟩

|-

| 4 || 0 || 3 || ⟨3,4,5⟩, ⟨3,4,6⟩, ⟨5,4,6⟩

|-

| 5 || 1/3 || 3 || ⟨1,5,2⟩, ⟨1,5,4⟩, ⟨2,5,4⟩

|-

| 6 || 0 || 0 || —

|}

:<math>\frac{3\cdot n_\Delta(G)}{n_\land(G)} = \frac{3}{11};</math>

:<math>\frac{\sum_{i=1}^{n} (C_i \cdot w_i)}{\sum_{i=1}^{n} w_i} = \frac{1\cdot1+\frac{1}{3}\cdot3+\frac{1}{3}\cdot3}{1\cdot2+3\cdot3} = \frac{3}{11};</math>

: <math>C_i\Rightarrow C = \frac{\lambda_G(v)3}{\tau_G(v)11}.</math>

== Note ==

These measures are 1 if every neighbour connected to <math>v_i</math> is also connected to every other vertex within the neighbourhood, and 0 if no vertex that is connected to <math>v_i</math> connects to any other vertex that is connected to <math>v_i</math>.

<references/>

== Altri progetti ==

== Coefficiente di clustering globale ==

{{interprogetto}}

Il '''coefficiente di clustering globale''' è basato su triple di nodi. Una tripla consiste di tre nodi connessi da due (tripla aperta) o tre (tripla chiusa) collegamenti. Ogni tripla è incentrata su un nodo. Un triangolo consiste di tre triple chiuse incentrate sui tre stessi nodi che le compongono.

{{Portale|informatica|matematica}}

Il coefficiente di clustering globale è, dunque, il numero di triple chiuse (o 3 volte il numero di triangoli) fratto il numero totale di triple (somma di quelle aperte e chiuse). Il primo tentativo di misurarlo fu effettuato da [[Robert Duncan Luce|Robert D. Luce]] e Albert D. Perry (1949).<ref>{{Cite journal|author = [[Robert Duncan Luce|R. D. Luce]], A. D. Perry|title = A method of matrix analysis of group structure|year = 1949|journal = Psychometrika|volume = 14|pages = 95&ndash;116|doi = 10.1007/BF02289146|issue = 1|pmid=18152948}}</ref> Questo metodo può essere applicato sia alle reti orientate che non orientate (often called transitivity).<ref>Stanley Wasserman, Kathrine Faust, 1994. ''Social Network Analysis: Methods and Applications.'', p. 243. Cambridge: Cambridge University Press.</ref>

Watts e Strogatz, invece, definirono il coefficiente di clustering come la media dei coefficienti locali:<ref>{{Cite journal|author=[[Duncan Watts|D. J. Watts]], [[Steven Strogatz|S. H. Strogatz]]|title=Figure 2 : Collective dynamics of 'small-world' networks|year=1998|url=http://www.nature.com/nature/journal/v393/n6684/fig_tab/393440a0_F2.html|journal=[[Nature (journal)|Nature]]|volume=393|pages=440&ndash;442|month=June|doi=10.1038/30918|pmid=9623998|issue=6684|bibcode=1998Natur.393..440W}}</ref>

:<dfn>Supponiamo che un nodo <math>v</math> abbia <math>k_v</math> vicini; allora possono esistere massimo <math>k_v(k_v - 1)/2</math> collegamenti fra loro (ciò accade quando tutti i vicini di <math>v</math> sono connessi fra loro). Denotando con <math>C_v</math> la frazione di tali collegamenti che effettivamente esiste, si definisce <math>C</math> come la media dei <math>C_v</math> fratto il numero di nodi.</dfn>

== Note ==

<references/>

<nowiki>[[Categoria:Teoria dei grafi]]

[[Categoria:Reti sociali]]