Detecting community patterns capturing exceptional link trails

摘要

We present a new method for detecting descriptive community patterns capturing exceptional (sequential) link trails. For that, we provide a novel problem formalization: We model sequential data as first-order Markov chain models, mapped to an attributed weighted network represented as a graph. Then, we detect subgraphs (communities) using exceptional model mining techniques: We target subsets of sequential transitions between nodes that are exceptional in that sense that they either conform strongly to a specific reference or show significant deviations, estimated by a quality measure. In particular, such a community is described by a community pattern composed of descriptive features (of the attributed graph) covering the respective community. We present a comprehensive modeling approach and discuss results of a case study analyzing data from two real-world social networks.