Course contentsShow
← Machine Learning and Deep Learning
Lesson 2487 of 3,53854. Graph Neural NetworksFree lesson

Graph Properties: Degree, Connectivity, and Paths

Compute node degree; understand graph connectivity, shortest paths, and diameter as structural properties.

Graph Properties: Degree, Connectivity, and Paths

You'll learn how to measure fundamental structural properties of graphs that determine how information flows through networks.

Understanding Core Graph Properties

Graphs aren't just collections of nodes and edges—their structure matters tremendously for machine learning tasks. Three fundamental properties help characterize this structure:

Node Degree

The degree of a node is simply how many edges connect to it. Think of it like counting someone's friends in a social network. In directed graphs, you distinguish between in-degree (incoming edges) and out-degree (outgoing edges). High-degree nodes are often "hubs" that play outsized roles in information diffusion.

Graph Connectivity

Connectivity describes whether you can reach any node from any other node by following edges. A graph is connected if there's at least one path between every pair of nodes. In social networks, disconnected components might represent isolated communities. This property determines whether information can flow globally or remains trapped in clusters.

Paths and Distance

A path is a sequence of edges connecting two nodes. The shortest path between nodes is the path with the fewest edges (or minimum total weight in weighted graphs). The diameter of a graph is the longest shortest path between any pair of nodes—essentially measuring how "wide" the graph is. Small-world networks (like social graphs) have surprisingly short diameters despite having millions of nodes.

Why This Matters for GNNs

Graph Neural Networks use these structural properties to determine how information propagates. Node degree influences aggregation (high-degree nodes pool information from many neighbors), connectivity determines which nodes can influence each other, and path lengths affect how many GNN layers you need to capture long-range dependencies.

Key Takeaway: Node degree, connectivity, and path structure are fundamental graph properties that govern information flow and directly influence how Graph Neural Networks process and learn from graph-structured data.