The clustering coefficient of an unweighted network has been extensively used to quantify how tightly connected is the neighbor around a node and it has been widely adopted for assessing the quality of nodes in a social network. The computation of the clustering coefficient is challenging since it requires to count the number of triangles in the graph. Several recent works proposed efficient sampling, streaming and MapReduce algorithms that allow to overcome this computational bottleneck. As a matter of fact, the intensity of the interaction between nodes, that is usually represented with weights on the edges of the graph, is also an important measure of the statistical cohesiveness of a network. Recently various notions of weighted clustering coefficient have been proposed but all those techniques are hard to implement on large-scale graphs. In this work we show how standard sampling techniques can be used to obtain efficient estimators for the most commonly used measures of weighted clustering coefficient. Furthermore we also propose a novel graph-theoretic notion of clustering coefficient in weighted networks. © Springer International Publishing Switzerland 2014.

Efficient Computation of the Weighted Clustering Coefficient / Lattanzi, Silvio; Leonardi, Stefano. - STAMPA. - 8882:(2014), pp. 34-46. (Intervento presentato al convegno 11th International Workshop Algorithms and Models for the Web Graph (WAW) tenutosi a Beijing, China) [10.1007/978-3-319-13123-8_4].

Efficient Computation of the Weighted Clustering Coefficient

LATTANZI, SILVIO;LEONARDI, Stefano
2014

Abstract

The clustering coefficient of an unweighted network has been extensively used to quantify how tightly connected is the neighbor around a node and it has been widely adopted for assessing the quality of nodes in a social network. The computation of the clustering coefficient is challenging since it requires to count the number of triangles in the graph. Several recent works proposed efficient sampling, streaming and MapReduce algorithms that allow to overcome this computational bottleneck. As a matter of fact, the intensity of the interaction between nodes, that is usually represented with weights on the edges of the graph, is also an important measure of the statistical cohesiveness of a network. Recently various notions of weighted clustering coefficient have been proposed but all those techniques are hard to implement on large-scale graphs. In this work we show how standard sampling techniques can be used to obtain efficient estimators for the most commonly used measures of weighted clustering coefficient. Furthermore we also propose a novel graph-theoretic notion of clustering coefficient in weighted networks. © Springer International Publishing Switzerland 2014.
2014
11th International Workshop Algorithms and Models for the Web Graph (WAW)
Theoretical Computer Science; Computer Science (all)
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Efficient Computation of the Weighted Clustering Coefficient / Lattanzi, Silvio; Leonardi, Stefano. - STAMPA. - 8882:(2014), pp. 34-46. (Intervento presentato al convegno 11th International Workshop Algorithms and Models for the Web Graph (WAW) tenutosi a Beijing, China) [10.1007/978-3-319-13123-8_4].
File allegati a questo prodotto
File Dimensione Formato  
Lattanzi_Efficient-Computation_2014.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.2 MB
Formato Adobe PDF
1.2 MB Adobe PDF   Contatta l'autore
Lattanzi_Efficient-Computation_Frontespizio-indice_2014.pdf

solo gestori archivio

Tipologia: Altro materiale allegato
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.51 MB
Formato Adobe PDF
1.51 MB Adobe PDF   Contatta l'autore
VE_2014_11573-951135.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.2 MB
Formato Adobe PDF
1.2 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/951135
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact