In/Out Degree Distribution
In degree, the measure of how many directed edges are coming into a node, and out degree, the measure of how many directed edges are starting from a node, are used as comparative metrics to quantify the differences between network structure.
All Pairs Max Flow
To measure all pairs max flow, we employ two algorithms, the Edmonds-Karp Algorithm\citep{edmonds1972theoretical} and the Push-Relabel Algorithm \citep{goldberg1985new}
The Edmonds-Karp Algorithm is defined in \ref{601679} and runs in \(O\left(VE^2\right)\)
The Push-Relabel Algorithm is defined in \ref{606334} and runs in \(O\left(V^3\right)\)
Related Work
Methods
To test this hypothesis, we collected natural networks and built out a series of artificial and random networks. To setup, build, run analysis on, and visualize the networks, a Python module named graph-tool was used, which allows for multi-core analysis.
// NAREN ANN BUILDING DESCRIPTION HERE
Similar to the ANNs, natural networks were imported into graph-tool using their edge lists. Random networks were generated using packages found within the graph-tool module.
Measured Metrics
Betweennes Centrality
Betweenness measures the centrality of a node on the metric of shortest paths. Essentially, it measures how many shortest paths for pairs of vertices pass through the measured node, essentially checking if a node is causing bottlenecking in a network. This metric is defined by the following equation:LaTeX
\begin{equation}
C_{B}(v)=\sum_{s\neq v\neq t\in V}\frac{\sigma_{st}(v)}{\sigma_{st}}\nonumber \\
\end{equation}
Where \(\sigma_{st}\) is the total number of geodesic paths from \(s\) to \(t\) and \(\sigma_{st}(v)\) is the number of geodesic paths from \(s\) to \(t\) which pass through \(v\) \citep{freeman1977set}\cite{anthonisse1971rush}