D-cores: measuring collaboration of directed graphs based on degeneracy - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Knowledge and Information Systems (KAIS) Année : 2012

D-cores: measuring collaboration of directed graphs based on degeneracy

Résumé

Community detection and evaluation is an important task in graph mining. In many cases, a community is defined as a subgraph characterized by dense connections or interactions between its nodes. A variety of measures are proposed to evaluate different quality aspects of such communities--in most cases ignoring the directed nature of edges. In this paper, we introduce novel metrics for evaluating the collaborative nature of directed graphs--a property not captured by the single node metrics or by other established commu- nity evaluation metrics. In order to accomplish this objective, we capitalize on the concept of graph degeneracy and define a novel D-core framework, extending the classic graph-theoretic notion of k-cores for undirected graphs to directed ones. Based on the D-core, which essen- tially can be seen as a measure of the robustness of a community under degeneracy, we devise a wealth of novel metrics used to evaluate graph collaboration features of directed graphs. We applied the D-core approach on large synthetic and real-world graphs such as Wikipedia, DBLP, and ArXiv and report interesting results at the graph as well at the node level.
Fichier principal
Vignette du fichier
955253d2d52b1e475839da406dd65e0f.pdf (1.08 Mo) Télécharger le fichier
Origine Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

lirmm-00846768 , version 1 (19-07-2013)

Identifiants

Citer

Christos Giatsidis, Dimitrios M. Thilikos, Michalis Vazirgiannis. D-cores: measuring collaboration of directed graphs based on degeneracy. Knowledge and Information Systems (KAIS), 2012, 35 (2), pp.311 - 343. ⟨10.1007/s10115-012-0539-0⟩. ⟨lirmm-00846768⟩
409 Consultations
1288 Téléchargements

Altmetric

Partager

More