SUBJECTIVELY INTERESTING PATTERNS IN NETWORKS

Abstract

Graph mining is one of the well-established elds of data mining. Still, it remains an active research area, considering that in many real-world scenarios (e.g., social media, airline operations), a large amount of data comes in the form of graphs. Graphs are helpful when the structure of data is equally important as the content, and necessarily, graphs are used to model relationships between entities. Graph mining methods focus on discovering subsets of vertices in a graph, as patterns representing useful structural insights about the data. The usefulness of a pattern for an analyst is mainly quanti ed using an interestingness measure. In general, most of the interestingness measures are data-driven, i.e., the interestingness is determined only based on the available data and the pre-speci ed patterns' structures to be discovered, with minimal analyst's interaction. However, in practice, the concept of interestingness is mostly subjective, as the usefulness of a pattern is dependent on the analyst and his/her prior knowledge. Here, a pattern is considered to be subjectively interesting if it departs from the analyst's expectations. Notably, the existing notion of subjective interestingness is largely limited for simple graphs (graphs having a single edge between a vertex-pair). This marks a major research gap, since, there do exist many real-world scenarios which could be realistically modelled through multigraphs, characterized by multiple edges between a vertex-pair. For example, in the co-authorship network, two authors may have multiple co-authored publications, a scenario that could be modelled through multiple edges (each representing a unique co-authored publication) between the two vertices (representing each author). One of the fundamental contributions of this thesis relates to bridging the research gap, through the proposition of a subjective interestingness measure for multigraph patterns. Subsequently, an algorithm to iteratively discover subjectively interesting multigraph patterns is developed. The proposed algorithm's advantages over existing methods are demonstrated by extensive experiments on synthetic and real-world datasets, such as co-actor and co-authorship networks.