Node degree

As explained in Graph Algorithms for Data Science

Node degree is the number of graph relationships incident to a node, with directed graphs potentially distinguishing incoming and outgoing relationships.

Node degree counts the links incident to a node. Measuring degree across a network helps reveal whether connections are distributed evenly or concentrated in a small number of highly connected nodes. section 5.0

For directed networks, separate the connections by direction:

• In-degree counts incoming connections. section 5.6
• Out-degree counts outgoing links. section 5.6
• The overall degree distribution describes how many links nodes typically have. Random-network models are associated with a Gaussian distribution, whereas real-world networks commonly follow a power-law distribution with many low-degree nodes and a few highly connected ones. section 5.0 section 5.6

Web pages and URL links

Treat web pages as nodes and URL links as directed relationships. A page’s in-degree counts pages linking to it, while its out-degree counts the links it publishes. Comparing these values helps distinguish rarely connected pages from unusually connected ones. section 5.0

Figure 5.1 Random network degree distribution

Use the random-network distribution figure to compare the expected concentration of node links. section 5.0

Figure 5.2 Scale-free network degree distribution

Use the scale-free distribution figure to see how real-world networks can contain many low-degree nodes and a small number of hubs. section 5.0

How Graph Algorithms for Data Science covers it

How deep it goes

Defines degree and distinguishes directed in-degree from out-degree, but does not develop a calculation procedure or implementation.

Examples

Uses handshakes, web pages, and URL links to illustrate links, directed degree, and contrasting degree distributions.

What you can do after

Evaluate network structure by identifying typical connectivity, low-degree nodes, and highly connected nodes.

How it connects

Connects node degree with random networks, Gaussian distributions, power-law distributions, directed networks, and PageRank.

liveBookmanning.com

Read Graph Algorithms for Data Science on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Knowledge Graphs and LLMs in ActionNode degree is the number of edges incident to a node, optionally separated by incoming and outgoing direction.
• 

  liveBookmanning.com
  Graph Neural Networks in ActionThe degree of a node is the number of graph edges incident to it, subject to conventions such as self-loop counting.
• 

  liveBookmanning.com
  Fabulous Adventures in Data Structures and AlgorithmsGraph degree is the number of edges incident to a given graph node.

Compare how 4 books explain node degree →

Related concepts

• Adamic-Adar indexused by · The Adamic-Adar index is a link-prediction metric that scores node pairs by weighting common neighbors more highly when they have lower degree.
• common neighbor countmeasured by · Common neighbor count is the number of nodes directly connected to both members of a node pair, often used as a link-prediction score.
• degree-weighted path countused by · A degree-weighted path count is a path-based graph metric that weights paths according to the degrees of the entities they traverse.
• PageRankcontrasts with · PageRank is a link-analysis algorithm that estimates the relative importance of nodes in a directed graph from the structure and importance of incoming links.
• undirected graphcontrasts with · An undirected graph is a graph whose edges have no orientation, so each edge connects its endpoints symmetrically.

This explainer was generated by Manning's knowledge graph from the text of Graph Algorithms for Data Science. The section links point to the parts of the book it draws on.