What are k-cores and f-cores?

Abstract - Community subgraphs are characterized by dense connections or interactions among its nodes. Community detection and evaluation is an important task in graph mining. A variety of measures have been proposed to evaluate the quality of such communities. In our research, we evaluate communities based on the k-core concept, as means of evaluating their collaborative nature - a property not captured by the single node metrics or by the established community evaluation metrics. Based on the k-core, which essentially measures the robustness of a community under degeneracy, we extend it to weighted graphs, devising a novel concept of k-cores on weighted graphs - called f-cores. We applied the k-core approach on large real world graphs - such as DBLP and report interesting results.

For more details see the full paper:
Christos Giatsidis, Dimitrios M. Thilikos, Michalis Vazirgiannis: Evaluating Cooperation in Communities with the k-Core Structure. ASONAM 2011: 87-93

Relevant ACM KDD 2012 Demo track paper:
Christos Giatsidis, Klaus Berberich, Dimitrios M. Thilikos, Michalis Vazirgiannis: Visual exploration of collaboration networks based on graph degeneracy. KDD 2012: 1512-1515

In the following links we present visualizations from the k-core and f-core hop-1 findings for authors that are in the DBLP dataset.
This is a video displaying the above f-core DBLP demo

Video for the KDD 2012 DEMO Track

Additionally we present visualizations from the f-core hop-1 findings for authors that are in the ARXIV (High Energy Physics - Theory) dataset.

What are D-cores?

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 among its nodes. A large variety of measures have been proposed to evaluate the quality 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 community 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 essentially 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 real-world graphs such as Wikipedia and DBLP and report interesting results at the graph as well at node level.

For more details see the full paper:
Christos Giatsidis, Dimitrios M. Thilikos, Michalis Vazirgiannis: D-cores: Measuring Collaboration of Directed Graphs Based on Degeneracy. ICDM 2011: 201-210

Journal Version:
D-cores: measuring collaboration of directed graphs based on degeneracy Christos Giatsidis, Dimitrios M. Thilikos, Michalis Vazirgiannis in Knowledge and Information Systems, September 2012, 10.1007/s10115-012-0539-0

In the following link we present a visualization of the D-core frontier for authors that are in the DBLP dataset.