Coefficiente di clustering

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

L'evidenza suggerisce che nella maggiorparte 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, quindi, dende ad essere maggiore rispetto a quello di grafi in cui i collegamenti sono generati casualmente.^[1][2]

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.

Local clustering coefficient

 

Esempio di coefficiente di clustering localein un grafo non orientato:
1. Nel primo caso, i collegamenti fra i vicini del nodo blu sono tre su tre, quindi il coefficiente risulta essere 1.
2. Nel secondo caso, i collegamenti sono uno su tre, quindi il coefficiente è 1/3.
3. Nel terzo caso i collegamenti sono inesistenti, quindi il coefficiente è nullo.

Il coefficiente di clustering locale The local clustering coefficient of a vertex (node) in a graph quantifies how close its neighbors are to being a clique (complete graph). Duncan J. Watts and Steven Strogatz introduced the measure in 1998 to determine whether a graph is a small-world network.

A graph ${\displaystyle G=(V,E)}$  formally consists of a set of vertices ${\displaystyle V}$  and a set of edges ${\displaystyle E}$  between them. An edge ${\displaystyle e_{ij}}$  connects vertex ${\displaystyle v_{i}}$  with vertex ${\displaystyle v_{j}}$ .

The neighbourhood ${\displaystyle N_{i}}$  for a vertex ${\displaystyle v_{i}}$  is defined as its immediately connected neighbours as follows:

${\displaystyle N_{i}=\{v_{j}:e_{ij}\in E\land e_{ji}\in E\}.}$ 

We define ${\displaystyle k_{i}}$  as the number of vertices, ${\displaystyle |N_{i}|}$ , in the neighbourhood, ${\displaystyle N_{i}}$ , of a vertex.

The local clustering coefficient ${\displaystyle C_{i}}$  for a vertex ${\displaystyle v_{i}}$  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, ${\displaystyle e_{ij}}$  is distinct from ${\displaystyle e_{ji}}$ , and therefore for each neighbourhood ${\displaystyle N_{i}}$  there are ${\displaystyle k_{i}(k_{i}-1)}$  links that could exist among the vertices within the neighbourhood (${\displaystyle k_{i}}$  is the number of neighbors of a vertex). Thus, the local clustering coefficient for directed graphs is given as ^[2]

${\displaystyle C_{i}={\frac {|\{e_{jk}:v_{j},v_{k}\in N_{i},e_{jk}\in E\}|}{k_{i}(k_{i}-1)}}.}$ 

An undirected graph has the property that ${\displaystyle e_{ij}}$  and ${\displaystyle e_{ji}}$  are considered identical. Therefore, if a vertex ${\displaystyle v_{i}}$  has ${\displaystyle k_{i}}$  neighbours, ${\displaystyle {\frac {k_{i}(k_{i}-1)}{2}}}$  edges could exist among the vertices within the neighbourhood. Thus, the local clustering coefficient for undirected graphs can be defined as

${\displaystyle C_{i}={\frac {2|\{e_{jk}:v_{j},v_{k}\in N_{i},e_{jk}\in E\}|}{k_{i}(k_{i}-1)}}.}$ 

Let ${\displaystyle \lambda _{G}(v)}$  be the number of triangles on ${\displaystyle v\in V(G)}$  for undirected graph ${\displaystyle G}$ . That is, ${\displaystyle \lambda _{G}(v)}$  is the number of subgraphs of ${\displaystyle G}$  with 3 edges and 3 vertices, one of which is ${\displaystyle v}$ . Let ${\displaystyle \tau _{G}(v)}$  be the number of triples on ${\displaystyle v\in G}$ . That is, ${\displaystyle \tau _{G}(v)}$  is the number of subgraphs (not necessarily induced) with 2 edges and 3 vertices, one of which is ${\displaystyle v}$  and such that ${\displaystyle v}$  is incident to both edges. Then we can also define the clustering coefficient as

${\displaystyle C_{i}={\frac {\lambda _{G}(v)}{\tau _{G}(v)}}.}$ 

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

${\displaystyle \tau _{G}(v)=C({k_{i}},2)={\frac {1}{2}}k_{i}(k_{i}-1).}$ 

These measures are 1 if every neighbour connected to ${\displaystyle v_{i}}$  is also connected to every other vertex within the neighbourhood, and 0 if no vertex that is connected to ${\displaystyle v_{i}}$  connects to any other vertex that is connected to ${\displaystyle v_{i}}$ .

Coefficiente di clustering globale

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.

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 D. Luce e Albert D. Perry (1949).^[3] Questo metodo può essere applicato sia alle reti orientate che non orientate (often called transitivity).^[4]

Watts e Strogatz, invece, definirono il coefficiente di clustering come la media dei coefficienti locali:^[5]

Supponiamo che un nodo ${\displaystyle v}$  abbia ${\displaystyle k_{v}}$  vicini; allora possono esistere massimo ${\displaystyle k_{v}(k_{v}-1)/2}$  collegamenti fra loro (ciò accade quando tutti i vicini di ${\displaystyle v}$  sono connessi fra loro). Denotando con ${\displaystyle C_{v}}$  la frazione di tali collegamenti che effettivamente esiste, si definisce ${\displaystyle C}$  come la media dei ${\displaystyle C_{v}}$  fratto il numero di nodi.

Quest'ultima definizione è equivalente alla prima se si utilizza la media ponderata, pesando ogni ${\displaystyle C_{v}}$  con il numero di triple in cui il nodo è centrale:

${\displaystyle 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}}}}$ .

Dove:

• ${\displaystyle n_{\Delta }(G)}$  è il numero di triangoli del grafo;
• ${\displaystyle n_{\land }(G)}$  è il numero complessivo di triple del grafo;
• ${\displaystyle w_{i}}$  è il peso del vertice i-esimo (numero di triple in cui il nodo è centrale);

Notare che ${\displaystyle \sum _{i=1}^{n}w_{i}\equiv n_{\land }(G)}$ .

Esempio

 

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:

Vertice	Collegamenti 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,5⟩, ⟨5,4,6⟩
5	1/3	3	⟨1,5,2⟩, ⟨1,5,4⟩, ⟨2,5,4⟩
6	0	0	—

${\displaystyle {\frac {3\cdot n_{\Delta }(G)}{n_{\land }(G)}}={\frac {3}{11}};}$ 

${\displaystyle {\frac {\sum _{i=1}^{n}(C_{i}\cdot w_{i})}{\sum _{i=1}^{n}w_{i}}}={\frac {1\cdot 1+{\frac {1}{3}}\cdot 3+{\frac {1}{3}}\cdot 3}{1\cdot 2+3\cdot 3}}={\frac {3}{11}};}$ 

${\displaystyle \Rightarrow C={\frac {3}{11}}.}$ 

Note

1. ^ P. W. Holland, S. Leinhardt, Transitivity in structural models of small groups, in Comparative Group Studies, vol. 2, 1971, pp. 107–124.
2. D. J. Watts, S. H. Strogatz, Collective dynamics of 'small-world' networks, in Nature, vol. 393, n. 6684, June 1998, pp. 440–442, DOI:10.1038/30918.
3. ^ R. D. Luce, A. D. Perry, A method of matrix analysis of group structure, in Psychometrika, vol. 14, n. 1, 1949, pp. 95–116, DOI:10.1007/BF02289146.
4. ^ Stanley Wasserman, Kathrine Faust, 1994. Social Network Analysis: Methods and Applications., p. 243. Cambridge: Cambridge University Press.
5. ^ D. J. Watts, S. H. Strogatz, Figure 2 : Collective dynamics of 'small-world' networks, in Nature, vol. 393, n. 6684, June 1998, pp. 440–442, DOI:10.1038/30918.

<nowiki>