The first explores the space of communities that meet certain criteria in terms of density, in search for those that are also homogeneous with respect to some of the attributes (Moser et al. There are two complementary approaches, as stated in Atzmueller et al. Research on local pattern mining in attributed graphs has so far focused on identifying dense vertex-induced subgraphs, dubbed communities, that are coherent also in terms of attributes.
Such subgroup rules are local patterns, in that they provide information only about a certain part of the data. To address this, the local pattern mining community introduced the concept of subgroup discovery, where the aim is to identify subgroups of data points for which a target attribute has homogeneous and/or outstanding values (Herrera et al. Such global models often fail to provide insight though. One approach to identify the relations between the connectivity and the attributes is to train a link prediction classifier, with as input the attribute values of a vertex pair, predicting the edge as present or absent (Gong et al. Hence, it appears likely it should be possible to understand the connectivity of a graph in terms of those attributes, at least to a certain extent. The attributes of individuals affect the likelihood of them meeting in the first place, and, if they meet, of becoming friends. The connectivity of the network is usually highly related to those attributes (Fond and Neville 2010 McPherson et al. In social networks for example, where vertices correspond to individuals, vertex attributes can include the individuals’ interests, education, residency, and more. Real-life graphs (also known as networks) often contain attributes for the vertices. Finally, we propose algorithms for efficiently finding interesting patterns of these different types. We demonstrate empirically that in the special case of dense subgraphs, this approach yields results that are superior to the state-of-the-art. Second, we develop a novel information-theoretic approach for quantifying the subjective interestingness of such patterns, by contrasting them with prior information an analyst may have about the graph’s connectivity. The first contribution in this paper is to generalize this type of pattern to densities between a pair of subgroups, as well as between all pairs from a set of subgroups that partition the vertices. Prior work has already considered the search for dense subgraphs (‘communities’) with homogeneous attributes. Such rules present potentially actionable and generalizable insight into the graph. The high-level structure of a graph can thus possibly be described well by means of patterns of the form ‘the subgroup of all individuals with certain properties X are often (or rarely) friends with individuals in another subgroup defined by properties Y’, ideally relative to their expected connectivity.
In social networks for example, the probability of a friendship between any pair of people depends on a range of attributes, such as their age, residence location, workplace, and hobbies. The connectivity structure of graphs is typically related to the attributes of the vertices.
0 kommentar(er)
