Local Knowledge Discovery in Attributed Graphs

We address the problem of finding local patterns and related local knowledge in an attributed graph. Our approach consists in extending the methodology of frequent closed pattern mining to the case in which the set of objects, in which are to be found the patterns support sets, is the set of vertices of a graph, typically representing a social network. We propose an algorithm to enumerate triples (c,e,l) where c is a (global) closed pattern which leads in the region e of the graph to a local closed pattern l and define a basis of implication rules expressing what new attributes l\c appear when focussing in this region. We discuss how to apply this methodology to the detection of frequent k-communities.