Mining exceptional closed patterns in attributed graphs

作者:Anes Bendimerad, Marc Plantevit, Céline Robardet

摘要

Geo-located social media provide a large amount of information describing urban areas based on user descriptions and comments. Such data make possible to identify meaningful city neighborhoods on the basis of the footprints left by a large and diverse population that uses this type of media. In this paper, we present some methods to exhibit the predominant activities and their associated urban areas to automatically describe a whole city. Based on a suitably attributed graph model, our approach identifies neighborhoods with homogeneous and exceptional characteristics. We introduce the novel problem of exceptional subgraph mining in attributed graphs and propose a complete algorithm that takes benefits from closure operators, new upper bounds and pruning properties. We also define an approach to sample the space of closed exceptional subgraphs within a given time budget. Experiments performed on ten real datasets are reported and demonstrated the relevancy of both approaches, and also showed their limits.

论文关键词:Exceptional subgraph mining, Pattern mining, Urban data analysis

论文评审过程:

论文官网地址:https://doi.org/10.1007/s10115-017-1109-2