Network Science Week 4:
Graph Theory II

Overview, Activity, and Discussion

Overview

This week, we continue our "crash course" in graph theory to develop our understanding of local and global properties of the graphical/topological structure of a given network. In particular, we will encounter:

an important property local to a particular vertex of a graph known as the degree of a vertex (this serves as our first example of measuring the importance or centrality of a vertex within a network)
walks and paths between vertices in a given network. These substructures of a network are used to define further measures and metrics such as the distance between vertices (which then gives rise to global properties of a network such as its diameter), components of a network, and the connectivity of a network.
The Graph Laplacian - another matrix associated with a network (like the adjacency matrix), which can, surprisingly, be combined with surprisingly simple computations to detect communities in networks, understand network diffusion, help us find a "nice" way to visualize a network, and reveal answers to combinatorial questions about a network (e.g., how many labeled spanning trees exist in a given network)

To make progress on the learning objectives, you should complete the following tasks this week:

Read sections 6.10 through 6.14.
Watch the video content associated with these sections.
Complete "Activity for Week 4" and submit your solutions.

Learning Objectives

By the end of the week, you should be able to:

Determine the degrees of the vertices of a given network both computationally (through matrices) and by visual inspection
Compute the distance between two vertices, the diameter of a network, and identify the components of a network visually
Use matrix operations and the adjacency matrix of a network to compute the number of walks of a given length between two vertices, the degrees of the vertices, and the number of triangles in a network.
Compute the graph Laplacian of a network