Clustering networks play a key role in many scientific fields, from Biology to Sociology and Computer Science. Some clustering approaches are called global because they exploit knowledge about the whole network topology. Vice versa, so-called local methods require only a partial knowledge of the network topology. Global approaches yield accurate results but do not scale well on large networks; local approaches, vice versa, are less accurate but computationally fast. We propose CONCLUDE (COmplex Network CLUster DEtection), a new clustering method that couples the accuracy of global approaches with the scalability of local methods. CONCLUDE generates random, non-backtracking walks of finite length to compute the importance of each edge in keeping the network connected, i.e., its edge centrality. Edge centralities allow for mapping vertices onto points of a Euclidean space and compute all-pairs distances between vertices; those distances are then used to partition the network into clusters. © 2013 Elsevier Inc.

Mixing local and global information for community detection in large networks / P. De Meo, E. Ferrara, G. Fiumara, A. Provetti. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - 80:1(2014 Feb), pp. 72-87. [10.1016/j.jcss.2013.03.012]

Mixing local and global information for community detection in large networks

A. Provetti
Ultimo
2014

Abstract

Clustering networks play a key role in many scientific fields, from Biology to Sociology and Computer Science. Some clustering approaches are called global because they exploit knowledge about the whole network topology. Vice versa, so-called local methods require only a partial knowledge of the network topology. Global approaches yield accurate results but do not scale well on large networks; local approaches, vice versa, are less accurate but computationally fast. We propose CONCLUDE (COmplex Network CLUster DEtection), a new clustering method that couples the accuracy of global approaches with the scalability of local methods. CONCLUDE generates random, non-backtracking walks of finite length to compute the importance of each edge in keeping the network connected, i.e., its edge centrality. Edge centralities allow for mapping vertices onto points of a Euclidean space and compute all-pairs distances between vertices; those distances are then used to partition the network into clusters. © 2013 Elsevier Inc.
Community detection; Complex networks; Social network analysis; Social networks
Settore INF/01 - Informatica
feb-2014
3-apr-2013
https://www.sciencedirect.com/science/article/pii/S0022000013000767?via=ihub
Article (author)
File in questo prodotto:
File Dimensione Formato  
J8-de_meo-mixing-JCSS14.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 541.73 kB
Formato Adobe PDF
541.73 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

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/2434/962382
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 115
  • ???jsp.display-item.citation.isi??? 97
social impact