Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata

Cited literature [45 references]  Display  Hide  Download
Contributor : Dimitrios Thilikos Connect in order to contact the contributor
Submitted on : Friday, July 19, 2013 - 7:36:23 PM
Last modification on : Friday, August 5, 2022 - 3:02:53 PM
Long-term archiving on: : Monday, October 21, 2013 - 11:16:07 AM


Publisher files allowed on an open archive




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. ⟨10.1007/s10115-012-0539-0⟩. ⟨lirmm-00846768⟩



Record views


Files downloads