The Degree Centrality Algorithm: A Simple but Powerful Centrality Algorithm

The Degree Centrality algorithm is the most common centrality algorithm, used to find the “popularity” of each node in a graph database by calculating the number of incoming and outgoing relationships. In our previous Betweenness Centrality article, we introduced one of the most common centrality graph algorithms types.

Why is the Degree Centrality Algorithm Widely Used?

The degree centrality algorithm is the easiest centrality algorithm to calculate in graph data science, as it just considers the total number of relationships connected to a particular node. It is a simple count of the total number of relationships linked to a node, showing how many connections a person has (J. Golbeck, 2015).

Other centrality algorithms have also been discussed in our previous articles about betweenness centrality and closeness centrality. To learn more about other graph data science algorithms, check our article on graph algorithms.

Degree Centrality Scoring

Sometimes the degree centrality score is normalized into a 0-1 scale, particularly when we want to compare the score between different networks, and draw conclusions regardless of the number of nodes. For that we divide the score (total number of relationships connected to the node) by the highest-degree node in the network. The node with the highest degree in the network will have a degree centrality of 1, and every other node’s centrality will be the fraction of its degree. For example, if the highest-degree node in a network has 50 edges, a node with 40 edges would have a degree centrality of 0.8=40/50. A node with a degree of 5 would have a degree centrality of 0.1=5/50.

In the case of a directed network, such as a job recommendation, the degree centrality score can be split into:

• The out-degree score is the number of relationships from the node to other nodes: i.e., the number of people someone has recommended for a job.
• The in-degree score, referring to the number of relationships that point to the node: i.e., number of people who have received recommendations for a job from others.

What Does Having a High Degree Centrality Score Mean?

The higher the degree, the more connections the node has, but we should keep in mind that having a high degree centrality score does not necessarily mean that the node spreads the information efficiently or that it is central to the main group.

The nodes in a graph can generally be split into two different “clusters”, one very large and dense (called the core of the network) and another where one node is connected to chain of low-degree nodes, with no other connection than a relationship to one node in the core network (called the periphery of the network) as the Fig. 1 shows (see J. Golbeck, 2013 for more details).

Use Cases

The degree centrality algorithm has been used in different kind of real-world network case, such as:

• Social Network Analysis: Degree centrality identifies in social networks the most “popular” individuals (nodes), as the ones with the largest number of followers or friends.
• Marketing: we can help companies to successfully promote and advertise products, by reaching out at key influencers in a target market
• Cybersecurity: We can identify potential targets for cyberattacks as individuals (nodes) with high degree centrality are likely to be more critical to the network as a whole.
• Transportation networks: We can identify the importance of different nodes in a transportation network (e.g., airports, train stations, bus stops), explore and avoid potential bottlenecks in the network. An example is shown in this article.

Conclusions

Degree centrality is a widely used algorithm in graph data science. It measures the importance of a node importance in a network analysis, by quantifying the number of connections a node has to other nodes within the network, thereby allowing it to provide insight into the structure of a network. It is used to identify influential nodes, detect communities, and understand the spread of information in a network.

As shown in Fig. 1, it is important to note that degree centrality alone may not provide a complete picture of a network, and other centrality measures may also be useful for different types of networks or questions. Nevertheless, degree centrality remains a valuable tool for network analysis and can provide uniquely valuable information about the structure and dynamics of networks.

Note on the degree centrality FORMULA:

For those interested in the degree centrality formula: the complexity of the degree centrality estimation for all the nodes in a graph takes O(m²), where m is the number of nodes in a dense adjacency matrix representation of the graph, and for edges takes O(n), where n is the number of edges in a sparse matrix representation (see reference for more details).

If you are considering whether an AI project can and should be a fit for your needs, read about whether an AI consulting partner like Graphable is right for you to help evaluate and deliver your project. Also, check out this article on understanding Large Language Models (LLMs) as it relates to your data science / AI initiatives.

Read Related Articles

• What is Graph Data Science?
• What is Neo4j Graph Data Science?
• What are Graph Algorithms?
• Graph Traversal Algorithms (a.k.a Pathfinding algorithms)
• Pathfinding Algorithms (Top 5, with examples)
• Closeness Centrality
• Betweenness Centrality
• PageRank
• Conductance Graph Community Detection: Python Examples
• Graph Embeddings (for more on graph embedding algorithms)

Also read this related article on graph analytics for more on analytics within the graph database context.