Centrality in valued graphs: A measure of betweenness based on network flow

Centrality in valued graphs: A measure of betweenness based on network flow

1991-06-01 | Freeman, Linton C; Borgatti, Stephen P; White, Douglas R
This paper introduces a new measure of centrality, $ C_F $, based on network flow, which extends the earlier betweenness-based measure $ C_B $. The new measure is applicable to both valued and non-valued graphs, making it more versatile for analyzing network data. Unlike $ C_B $, which focuses on geodesic paths, $ C_F $ considers all independent paths between pairs of points in the network. This approach allows for a more accurate representation of communication flows, as information may travel through multiple routes rather than only the shortest paths. The measure $ C_F $ is calculated by determining the proportion of maximum flow that passes through a given point. This is done by computing the maximum flow between all pairs of points and then assessing the contribution of each point to this flow. A normalized version of $ C_F $, $ C_F' $, is also introduced, which varies between 0 and 1. The centralization of the graph is also defined, measuring how much communication flow is concentrated in a single point. The paper compares $ C_F $ with $ C_B $, noting that they differ when cycles are present in the graph. In acyclic graphs, $ C_F $ and $ C_B $ may yield similar results, but in graphs with cycles, $ C_F $ accounts for all paths, while $ C_B $ only considers geodesics. This makes $ C_F $ more realistic in depicting network structures where communication may not be restricted to the shortest paths. The paper also discusses the application of $ C_F $ to valued graphs, where edges have associated weights representing the strength of social connections. This allows for a more nuanced analysis of network centrality, capturing subtle differences in relationship strengths. The new measures are more flexible and realistic, particularly in networks where communication flows are not limited to the shortest paths. The paper concludes that while $ C_F $ may produce different results than $ C_B $, it provides a more comprehensive and accurate measure of centrality in complex networks.This paper introduces a new measure of centrality, $ C_F $, based on network flow, which extends the earlier betweenness-based measure $ C_B $. The new measure is applicable to both valued and non-valued graphs, making it more versatile for analyzing network data. Unlike $ C_B $, which focuses on geodesic paths, $ C_F $ considers all independent paths between pairs of points in the network. This approach allows for a more accurate representation of communication flows, as information may travel through multiple routes rather than only the shortest paths. The measure $ C_F $ is calculated by determining the proportion of maximum flow that passes through a given point. This is done by computing the maximum flow between all pairs of points and then assessing the contribution of each point to this flow. A normalized version of $ C_F $, $ C_F' $, is also introduced, which varies between 0 and 1. The centralization of the graph is also defined, measuring how much communication flow is concentrated in a single point. The paper compares $ C_F $ with $ C_B $, noting that they differ when cycles are present in the graph. In acyclic graphs, $ C_F $ and $ C_B $ may yield similar results, but in graphs with cycles, $ C_F $ accounts for all paths, while $ C_B $ only considers geodesics. This makes $ C_F $ more realistic in depicting network structures where communication may not be restricted to the shortest paths. The paper also discusses the application of $ C_F $ to valued graphs, where edges have associated weights representing the strength of social connections. This allows for a more nuanced analysis of network centrality, capturing subtle differences in relationship strengths. The new measures are more flexible and realistic, particularly in networks where communication flows are not limited to the shortest paths. The paper concludes that while $ C_F $ may produce different results than $ C_B $, it provides a more comprehensive and accurate measure of centrality in complex networks.
Reach us at info@study.space
[slides] Centrality in valued graphs%3A A measure of betweenness based on network flow | StudySpace