- 1 Introduction
- 2 Graphs
- 2.1 Social Network Analysis: From Relationships to Graphs
- 2.2 The Building Blocks of Graphs: Edges and Nodes
- 2.3 Symmetric Relations and Undirected Graphs
- 2.4 Asymmetric Relations and Directed Graphs
- 2.5 Anti-Symmetric Ties and Tree Graphs
- 2.6 Order and Size
- 2.7 Average Degree
- 2.8 Degree Distributions
- 2.9 Density
- 2.10 Ego-Centric Networks
- 2.11 Weighted Ties as a Measure of Strength
- 2.12 Di-Graphs
- 2.13 Collecting Network Data
- 2.14 Practice Problems

- 3 Matrices
- 4 Centrality and Composition
- 5 Subgraphs
- 6 Where Do Networks Come From?
- 7 Social Capital: Network Structure and Social Outcomes
- 8 Whole Network
- 9 Diffusion

As graphs are really just representations of real world relationships, they can be as varied as those relationships. As such, language has developed to explain different facets of a graph.

The **order** of a graph is the number of nodes in the graph. More accurately, keeping in mind that the graph is really a set of a set of nodes and edges, the order is the cardinality of V(N). Cardinality is simply a mathematical term for how many components/elements there are in a set. Thus, the graph in Figure 1.3 has an order of nine, while Figure 1.4 has an order of seven. The variable n represents the number of nodes in the graph.

Likewise, the **cardinality** of the set E(M) is the number of edges in the graph. The cardinality of the set E(M) in Figure 1.3 is 16, while in Figure 1.4 it is 11. If you say the cardinality of the graph in Figure 1.3 is 16, we can all understand that you are referring to the number of edges, as you would use the term order if you were talking about the number of nodes. Likewise, in future notation, the number of edges in the graph will be represented as variable m. We use order to refer to the cardinality of the set V(N), while just saying cardinality to refer to the cardinality of set E(M).

Finally, the **size** of the graph is defined as how many edges there could possibly be if everyone had a relationship with everyone else in the network. It is the maximum possible number of ties, and is calculated as [n(n-1)]/2 for an undirected network, and [n(n-1)] for a directed network.