  When dealing with large graphs, such as those that arise in the context of
online social networks, a subset of nodes may be labeled. These labels can
indicate demographic values, interest, beliefs or other characteristics of the
nodes (users). A core problem is to use this information to extend the labeling
so that all nodes are assigned a label (or labels). In this chapter, we survey
classification techniques that have been proposed for this problem. We consider
two broad categories: methods based on iterative application of traditional
classifiers using graph information as features, and methods which propagate
the existing labels via random walks. We adopt a common perspective on these
methods to highlight the similarities between different approaches within and
across the two categories. We also describe some extensions and related
directions to the central problem of node classification.
