In many real-world networks, nodes have class labels, attributes, or variables that affect the network's topology. If the topology of the network is known but the labels of the nodes are hidden, we would like to select a small subset of nodes such that, if we knew their labels, we could accurately predict the labels of all the other nodes. We develop an active learning algorithm for this problem which uses information-theoretic techniques to choose which nodes to explore. We test our algorithm on networks from three different domains: a social network, a network of English words that appear adjacently in a novel, and a marine food web. Our algorithm makes no initial assumptions about how the groups connect, and performs well even when faced with quite general types of network structure. In particular, we do not assume that nodes of the same class are more likely to be connected to each other---only that they connect to the rest of the network in similar ways.
Supervised and semi-supervised data mining techniques require labeled data. However, labeling examples is costly for many real-world applications. To address this problem, active learning techniques have been developed to guide the labeling process in an effort to minimize the amount of labeled data without sacrificing much from the quality of the learned models. Yet, most of the active learning methods to date have remained relatively agnostic to the rich structure offered by network data, often ignoring the relationships between the nodes of a network. On the other hand, the relational learning community has shown that the relationships can be very informative for various prediction tasks. In this paper, we propose different ways of adapting existing active learning work to network data while utilizing links to select better examples to label. Recent studies have shown that graph-based approaches are effective for semi-supervised learning. The key idea behind many graph-based approaches is to enforce the consistency between the class assignment of unlabeled examples and the pairwise similarity between examples. One major limitation with most graph-based approaches is that they are unable to explore dissimilarity or negative similarity. This is because the dissimilar relation is not transitive, and therefore is difficult to be propagated. Furthermore, negative similarity could result in unbounded energy functions, which makes most graph-based algorithms unapplicable. In this paper, we propose a new graph-based approach, termed as "mixed label propagation" which is able to effectively explore both similarity and dissimilarity simultaneously. In particular, the new framework determines the assignment of class labels by (1) minimizing the energy function associated with positive similarity, and (2) maximizing the energy function associated with negative similarity. Our empirical study with collaborative filtering shows promising performance of the proposed approach.