Skip Navigation

Active discovery of network roles for predicting the classes of network nodes

  1. Leto Peel
  1. Department of Computer Science, University of Colorado, Boulder, CO 80309, USA
  1. Corresponding author. Email: leto.peel{at}colorado.edu
  1. Edited by: Ernesto Estrada

  • Received May 28, 2014.
  • Accepted October 18, 2014.

Abstract

Nodes in real world networks often have class labels, or underlying attributes, that are related to the way in which they connect to other nodes. Sometimes this relationship is simple, for instance nodes of the same class may be more likely to be connected. In other cases, however, this is not true, and the way that nodes link in a network exhibits a different, more complex relationship to their attributes. Here, we consider networks in which we know how the nodes are connected, but we do not know the class labels of the nodes or how class labels relate to the network links. We wish to identify the best subset of nodes to label to learn this relationship between node attributes and network links. We can then use this discovered relationship to accurately predict the class labels of the rest of the network nodes. We present a model that identifies groups of nodes with similar link patterns, which we call network roles, using a generative blockmodel. The model then predicts class labels by learning the mapping from network roles to class labels using a maximum margin classifier. We choose a subset of nodes to label according to an iterative margin-based active learning strategy. By integrating the discovery of network roles with the classifier optimization, the active learning process can adapt the network roles to better represent the network for node classification. We demonstrate the model by exploring a selection of real world networks, including a marine food web and a network of English words. We show that, in contrast to other network classifiers, this model achieves good classification accuracy for a range of networks with different relationships between class labels and network links.

Key words

| Table of Contents

This Article

  1. jcomplexnetw 3 (3): 431-449. doi: 10.1093/comnet/cnu043
  1. All Versions of this Article:
    1. cnu043v1
    2. 3/3/431 most recent

Classifications

Share

  1. Email this article

Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.