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 metadatas

Cited literature [45 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00846768
Contributor : Dimitrios Thilikos <>
Submitted on : Friday, July 19, 2013 - 7:36:23 PM
Last modification on : Monday, May 4, 2020 - 9:42:03 AM
Document(s) archivé(s) le : Monday, October 21, 2013 - 11:16:07 AM

File

955253d2d52b1e475839da406dd65e...
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

642

Files downloads

1058