6.1 Degree, Closeness, and Betweenness Centrality

Network centrality measures are crucial for understanding node importance in complex systems. Degree, closeness, and betweenness centrality each offer unique insights into a node's role and influence within a network.

These measures help identify key players, efficient communicators, and critical connectors. By analyzing networks through these lenses, we can optimize information flow, resource distribution, and overall network resilience across various domains.

Degree Centrality in Networks

Calculating and Interpreting Degree Centrality

Top images from around the web for Calculating and Interpreting Degree Centrality

• 

  The Hierarchy Structure in Directed and Undirected Signed Networks View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

• 

  Directed graph - Wikipedia View original

  Is this image relevant?

• 

  The Hierarchy Structure in Directed and Undirected Signed Networks View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

1 of 3

Top images from around the web for Calculating and Interpreting Degree Centrality

• 

  The Hierarchy Structure in Directed and Undirected Signed Networks View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

• 

  Directed graph - Wikipedia View original

  Is this image relevant?

• 

  The Hierarchy Structure in Directed and Undirected Signed Networks View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

1 of 3

• Degree centrality measures number of direct connections a node has in a network representing immediate influence or importance
• For undirected networks calculate by counting edges connected to a node
• In directed networks divide into in-degree (incoming connections) and out-degree (outgoing connections) providing different insights into node's role
• Normalize degree centrality to account for network size allowing comparisons across networks of different sizes
• Calculate normalized degree centrality using formula $CD(v) = deg(v) / (n-1)$ where deg(v) represents degree of node v and n represents total number of nodes in network
• Identify local centers of influence or hubs within network structure (social media influencers, airport hubs)

Limitations and Applications of Degree Centrality

• Focuses on local connections potentially oversimplifying node's importance in complex network structures
• May not capture global network dynamics or indirect influences
• Useful in identifying key players in social networks (popular individuals)
• Applied in epidemiology to identify potential super-spreaders of diseases
• Utilized in transportation networks to determine major connection points (busy intersections, central train stations)
• Helps in analyzing communication networks to find nodes with high direct connectivity (central servers, key communication hubs)

Closeness Centrality and its Implications

Calculating Closeness Centrality

• Measures how quickly node can reach all other nodes in network indicating efficiency in spreading information or influence
• Determine shortest paths between node and all other nodes in network
• Calculate using formula $CC(v) = (n-1) / Σd(v,u)$ where d(v,u) represents shortest path distance between nodes v and u, and n represents total number of nodes
• Adapt calculations for disconnected networks to handle infinite distances between unconnected components
• Nodes with high closeness centrality considered central to network's structure efficiently disseminating information or resources

Applications and Significance of Closeness Centrality

• Analyze information flow in communication networks (identifying efficient message broadcasters)
• Study disease spread in epidemiological networks (locating potential rapid infection sources)
• Examine resource distribution in supply chain networks (finding optimal distribution centers)
• Detect structural changes or anomalies in dynamic networks (identifying shifting influential nodes over time)
• Evaluate efficiency of transportation systems (determining optimal locations for public services)
• Assess influence in social networks (finding individuals who can quickly reach others)

Betweenness Centrality for Influential Nodes

Understanding and Calculating Betweenness Centrality

• Quantifies extent to which node acts as bridge between other nodes controlling information flow or connectivity
• Determine fraction of shortest paths between all pairs of nodes passing through given node
• Calculate using formula $CB(v) = Σs≠v≠t (σst(v) / σst)$ where σst represents total number of shortest paths from node s to node t, and σst(v) represents number of those paths passing through v
• Identify nodes serving as critical connectors or bottlenecks in network potentially controlling access to different network communities
• Pinpoint nodes bridging structural holes in network which may not be apparent from degree or closeness centrality measures

Applications and Challenges of Betweenness Centrality

• Analyze communication networks to find key intermediaries (gatekeepers of information flow)
• Study transportation systems to identify critical junctions (important transfer points, potential traffic bottlenecks)
• Examine social networks to locate brokers between different communities (individuals connecting diverse groups)
• Identify potential points of network vulnerability (nodes whose removal would significantly disrupt network connectivity)
• Computationally intensive for large networks often requiring approximation algorithms for practical application
• Useful in detecting individuals or entities with control over resource flow (middlemen in trade networks)
• Applied in biological networks to find proteins crucial for multiple pathways

Degree vs Closeness vs Betweenness Centrality

Conceptual Differences and Computational Aspects

• Degree centrality focuses on local connectivity while closeness and betweenness consider global network structure and paths between nodes
• Computational complexity increases from degree (simplest) to closeness to betweenness (most complex) affecting applicability to large-scale networks
• Degree centrality identifies hubs (popular social media accounts)
• Closeness centrality highlights efficient information disseminators (news outlets with broad reach)
• Betweenness centrality pinpoints critical bridges or gatekeepers (intermediaries in business networks)
• Measures can provide conflicting results node may have high degree centrality but low betweenness if not on many shortest paths between other nodes

Practical Applications and Measure Selection

• Closeness and betweenness centrality more sensitive to overall network topology changes compared to degree centrality
• Combine analysis of all three measures for comprehensive understanding of node's importance and role within network structure
• Choose centrality measure based on specific research question network type and aspect of node importance being investigated
• Apply in social network analysis to identify different types of influential individuals (connectors, broadcasters, bridges)
• Utilize in transportation planning to optimize network design (hub locations, efficient routes, critical transfer points)
• Implement in cybersecurity to identify vulnerable points in computer networks (central servers, key routers)
• Use in organizational studies to understand information flow and decision-making processes (key decision-makers, information brokers, team connectors)