Laboratoire d'informatique de l'École polytechnique
Sémin'Ouvert : « Graph degeneracy for citation networks exploration », par Michalis Vazirgiannis
Speaker:
Michalis Vazirgiannis
Location:
Salle G. Kahn
Date: Thu, 19 Jan 2017, 14:30-15:30
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. We applied the k-core approach on large real world graphs - such as DBLP and report interesting results. We further extend introduce novel metrics for evaluating the collaborative nature of /directed graphs/ 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 aminer.org citation data and report interesting results. The D-core metric has been adopted by aminer as part of its reported metrics - see an example here.
