Menu
Home
Log in / Register
 
Home arrow Computer Science arrow Social Computing, Behavioral-Cultural Modeling and Prediction
< Prev   CONTENTS   Next >

Labeling Actors in Social Networks Using a Heterogeneous Graph Kernel

Abstract. We consider the problem of labeling actors in social networks where the labels correspond to membership in specific interest groups, or other attributes of the actors. Actors in a social network are linked to not only other actors but also items (e.g., video and photo) which in turn can be linked to other items or actors. Given a social network in which only some of the actors are labeled, our goal is to predict the labels of the remaining actors. We introduce a variant of the random walk graph kernel to deal with the heterogeneous nature of the network (i.e., presence of a large number of node and link types). We show that the resulting heterogeneous graph kernel (HGK) can be used to build accurate classifiers for labeling actors in social networks. Specifically, we describe results of experiments on two real-world data sets that show HGK classifiers often significantly outperform or are competitive with the state-of-the-art methods for labeling actors in social networks.

1 Introduction

Social networks (e.g. Facebook) and social media (e.g. Youtube) have provided large amounts of network data that link actors (individuals) with other actors, as well as diverse types of digital objects or items e.g., photos, videos, articles, etc. Such data are naturally represented using heterogeneous networks with multiple types of nodes and links. We consider the problem of labeling actors in social networks where the labels correspond to membership in specific interest groups, participation in specific activities, or other attributes of the actors. However, in many real-world social networks, labels are available for only a subset of the actors. Given a social network in which only some of the actors are labeled, our goal is to predict the labels of the remaining actors.

Accurate prediction of actor labels is important for many applications, e.g., recommending specific items (e.g., movies, musics) to actors. A variety of approaches to labeling nodes in social networks have been explored in the literature including methods that develop a relational learner to classify an actor by iteratively labeling an actor to the majority class of its neighbors [1, 2]; methods that effectively exploit correlations among the labels and attributes of objects [3–5]; semi-supervised learning or transductive learning methods [6, 7] such as random-walk based methods [8, 9] that assign a label to an actor based on the known label(s) of objects represented by node(s) reachable via random walk(s) originating at the node representing the actor. However, with the exception of RankClass [10], Graffiti [8], EdgeCluster [11], and Assort [12, 13], most of the current approaches to labeling actors in social networks focus on homogeneous networks, i.e., networks that consist of a single type of nodes and/or links. RankClass and Graffiti offer probabilistic models for labeling actors in heterogeneous social networks. EdgeCluster mines the latent multi-relational information of a social network and convert it into useful features which can be used in constructing a classifier. Assort augments network data by combining explicit links with links mined from the nodes' local attributes to increase the amount of the information in the network and hence improve the performance of the network classifier [2]. Against this background, we introduce a heterogeneous graph kernel (HGK), a variant of the random walk graph kernel for labeling actors in a heterogeneous social network.

HGK is based on the following intuition: Two actors can be considered “similar” if they occur in the similar contexts; and “similar” actors are likely to have similar labels. We define the context of an object to include its direct and indirect neighbors and links between those neighbors. The similarity of two actors is defined in terms of the similarity of the corresponding contexts. We extend the random walk graph kernel [14– 16] which has been previously used for labeling nodes in homogeneous networks to the setting of heterogeneous networks. The resulting HGK is able to exploit the information provided by the multiple types of links and objects in a social networks to accurately label actors in such networks. Results of experiments on two real-world data sets show that HGK classifiers often significantly outperform or are competitive with the state-ofthe-art methods for labeling actors in social networks.

 
Found a mistake? Please highlight the word and press Shift + Enter  
< Prev   CONTENTS   Next >
 
Subjects
Accounting
Business & Finance
Communication
Computer Science
Economics
Education
Engineering
Environment
Geography
Health
History
Language & Literature
Law
Management
Marketing
Philosophy
Political science
Psychology
Religion
Sociology
Travel