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

DOI10.1093/COMNET/CNU043zbMATH Open1397.68156arXiv1312.7258OpenAlexW2963621728MaRDI QIDQ4689367FDOQ4689367

Authors: Leto Peel 

Publication date: 16 October 2018

Published in: Journal of Complex Networks (Search for Journal in Brave)

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 are 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 in order 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 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 optimisation, 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.

Full work available at URL: https://arxiv.org/abs/1312.7258

Recommendations

• Active exploration for large graphs
• Overlapping communities and roles in networks with node attributes: probabilistic graphical modeling, Bayesian formulation and variational inference
• Discovery of nodal attributes through a rank-based model of network structure
• Mixture models and exploratory analysis in networks
• Role models for complex networks

zbMATH Keywords

blockmodelscommunity detectionsupport vector machinessemi-supervised learningactive learningcollective classification

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)

Cited In (6)

• Active exploration for large graphs
• Joint label inference in networks
• Structure-oriented prediction in complex networks
• Network specialization: a topological mechanism for the emergence of cluster synchronization
• Role detection and prediction in dynamic political networks
• Actively learning to infer social ties

This page was built for publication: Active discovery of network roles for predicting the classes of network nodes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4689367)