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

Abstract : 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.
Liste complète des métadonnées

Littérature citée [45 références]  Voir  Masquer  Télécharger

Contributeur : Dimitrios M. Thilikos <>
Soumis le : vendredi 19 juillet 2013 - 19:36:23
Dernière modification le : jeudi 7 février 2019 - 16:59:09
Document(s) archivé(s) le : lundi 21 octobre 2013 - 11:16:07


Fichiers éditeurs autorisés sur une archive ouverte



Christos Giatsidis, Dimitrios M. Thilikos, Michalis Vazirgiannis. D-cores: measuring collaboration of directed graphs based on degeneracy. Knowledge and Information Systems (KAIS), Springer, 2012, 35 (2), pp.311 - 343. 〈http://link.springer.com/article/10.1007%2Fs10115-012-0539-0〉. 〈10.1007/s10115-012-0539-0〉. 〈lirmm-00846768〉



Consultations de la notice


Téléchargements de fichiers