This chapter presents the terminology and concepts of graph theory, and describes basic matrix operations that are used in social network analysis. Both graph theory and matrix operations have served as the foundations of many concepts in the analysis of social networks (Hage and Harary 1983; Harary, Norman, and Cartwright 1965). In this chapter, the notation presented in Chapter 3 is used, and more concepts and ideas from graph theory are described and illustrated with examples. The topics covered in this chapter are important for the methods discussed in the remaining chapters of the book, but they are especially important in Chapter 5 (Centrality, Prestige, and Related Actor and Group Measures), Chapter 6 (Structural Balance, Clusterability, and Transitivity), Chapter 7 (Cohesive Subgroups), and Chapter 8 (Affiliations, Co-memberships, and Overlapping Subgroups).

We start this chapter with a discussion of some reasons why graph theory and graph theoretic concepts are important for social network analysis. We then define a graph for representing a nondirectional relation. We begin with simple concepts, and progressively build on these to achieve more complicated, and more interesting, graph theoretic concepts. We then define and discuss directed graphs, for representing directional relations. Again, we begin with simple directed graph concepts and build to more complicated ideas. Following this, we discuss signed and valued graphs. We then define and discuss hypergraphs, which are used to represent affiliation networks.