Centrality
PortfolioOptimisers.AbstractCentralityAlgorithm — Type
abstract type AbstractCentralityAlgorithm <: AbstractPhylogenyAlgorithmAbstract supertype for the algorithms that score how central each asset is in a network.
Every member wraps one routine of Graphs.jl.
Every concrete or abstract type that selects a centrality algorithm must subtype AbstractCentralityAlgorithm.
Each member declares the weights it needs
A member states through centrality_polarity which quantity its edge weights must be, and centrality_graph gives it that quantity. The declaration is about correctness, because a shortest path over similarities gives the reverse order. It is not about capability. A member that declares nothing, and a source that carries no weights, both run on the plain graph with no error. The method on the abstract type declares nothing, so a new member is unweighted until it declares a polarity.
The five members that declare a polarity have an ov field. TopologyOnly in that field withdraws the declaration for that instance. centrality_polarity returns the effective polarity, and not the declared one.
The rule is the one of [136]. It weights the degree and the eigenvector centrality by a similarity, $1 + \rho_{i,\,j}$, and the betweenness, the eccentricity and the closeness by the distance $\sqrt{2(1 - \rho_{i,\,j})}$.
Interfaces
To add a centrality algorithm, subtype AbstractCentralityAlgorithm with the configuration of its routine as fields. Then implement calc_centrality. Implement centrality_polarity too if the algorithm reads edge weights.
calc_centrality
calc_centrality(ct::MyCentrality, g::Graphs.AbstractGraph) -> VecNum: Score every vertex ofg.centrality_graphbuildsgwith the weights of the polarity that the algorithm declares. The method only calls the routine, and checks nothing.
Arguments
ct: The instance of the subtype.g: The graph to score. The declared polarity decides whether it is weighted or plain.
Returns
scores::VecNum: One score for each vertex ofg, in the order of the vertices.
centrality_polarity
centrality_polarity(ct::MyCentrality) -> Option{<:AbstractCentralityPolarity}: Declare which quantity the edge weights must be. The method on the abstract type returnsnothing, so a new algorithm runs on the plain graph until it declares a polarity. DeclareDistancePolarityfor a routine over shortest paths, andSimilarityPolarityfor a routine that reads the adjacency matrix.
Arguments
ct: The instance of the subtype.
Returns
polarity::Option{<:AbstractCentralityPolarity}: The effective polarity, ornothingfor an algorithm that reads the topology alone.
Related
centrality_polaritycentrality_graphTopologyOnlyBetweennessCentralityClosenessCentralityDegreeCentralityEigenvectorCentralityKatzCentralityPagerankRadialityCentralityStressCentrality
References
- [136] F. Pozzi, T. Di Matteo and T. Aste. Spread of risk across financial markets: better to invest in the peripheries. Scientific Reports 3, 1665 (2013). Section "Methods", "Centrality and Peripherality measures".
PortfolioOptimisers.TopologyOnly — Type
struct TopologyOnly <: AbstractAlgorithmWithdraws an algorithm's polarity declaration, so it reads the network's topology alone.
An algorithm that declares a polarity receives weights wherever the source carries them. TopologyOnly in its ov field withdraws that request. centrality_polarity then returns nothing, and centrality_graph builds the plain Graphs.SimpleGraph of phylogeny_matrix. DegreeCentrality, Pagerank and KatzCentrality already run on that graph. TopologyOnly selects a route that exists, and it adds no estimator.
The override runs one way only
It removes weights and never adds them. No value forces a polarity on an algorithm, and the type of the field is not AbstractCentralityPolarity on purpose. A forced polarity runs with no error, because calc_distance_weighted_graph carries distances on both branches. The algorithm then reads a distance where it needs a similarity, and reverses its order with no error. No check at run time can find a wrong polarity.
Every source honours the request
Every source can give the answer over the topology alone. The override never warns, and no source ignores it. A partition source, a precomputed PhylogenyResult, and the tree branch under SimilarityPolarity already build the plain graph. On these sources, the answer is already the answer that the override asks for.
Only the five algorithms that declare a polarity have an ov field. DegreeCentrality, Pagerank and KatzCentrality already return the answer over the topology alone. They have nothing to override, so DegreeCentrality(; ov = TopologyOnly()) raises a MethodError.
It is a choice, not a simplification, and it moves no default
A centrality over the topology alone can be more stable across folds, for the same reason that a fixed dmax is stable across folds under PathLength. That is not a reason to make it the default.
The shipped default is already unweighted. The default ct of CentralityEstimator is DegreeCentrality, which declares no polarity. A caller who names no algorithm already gets this answer. A default of ov = TopologyOnly() changes the answer only for a caller who selected one of the five. For those five, the weights of the source give the correct answer, and AbstractCentralityPolarity states why.
The override makes sep active again. The route of the plain graph reads the separation closure that phylogeny_matrix builds, and the weighted routes do not read it. The override replaces the edge weights by a second parameter, and does not remove a parameter. Over twenty assets, all five algorithms with the override give different answers at HopCount(; n = 1) and at n = 3. Four of them do not read sep without the override. Under a default PathLength, that parameter is the observed diameter. The diameter depends on the data, and the argument for stability across folds tries to avoid such a quantity.
Examples
julia> ClosenessCentrality(; ov = TopologyOnly())ClosenessCentrality args ┼ Tuple{}: () kwargs ┼ @NamedTuple{}: NamedTuple() ov ┴ TopologyOnly()julia> isnothing(centrality_polarity(ClosenessCentrality(; ov = TopologyOnly())))truejulia> centrality_polarity(ClosenessCentrality())DistancePolarity()Related
PortfolioOptimisers.BetweennessCentrality — Type
struct BetweennessCentrality{__T_args, __T_kwargs, __T_ov} <: AbstractCentralityAlgorithmScores each asset by the share of the network's shortest paths that run through it.
BetweennessCentrality selects the betweenness centrality of Graphs.jl. It measures how much an asset lies on the shortest paths between other assets.
It declares DistancePolarity, unless ov overrides it. It is defined over shortest paths, so its weights must be distances. On a tree, the weighted answer is equal to the unweighted one. A tree has exactly one path between two vertices, so no weights can change the set of shortest paths. This is a property of the tree, and it does not hold on the similarity branch. Set ov to TopologyOnly to withdraw the declaration and read the topology alone.
Mathematical definition
\[\begin{align} \mathrm{BC}_i &= \dfrac{1}{(n - 1)(n - 2)} \sum_{s \neq i \neq t} \dfrac{\sigma_{s,\,t}(i)}{\sigma_{s,\,t}}\,, \end{align}\]
Where:
- $\mathrm{BC}_i$: Betweenness centrality of asset $i$.
- $\sigma_{s,\,t}$: Number of shortest paths between assets $s$ and $t$.
- $\sigma_{s,\,t}(i)$: Number of the shortest paths between assets $s$ and $t$ that pass through asset $i$.
- $n$: Number of assets, which is the number of vertices of the network.
The sum runs over the ordered pairs of distinct assets, so an undirected network counts each pair two times. The leading factor is therefore the reciprocal of $(n - 1)(n - 2)$, and not of half of it. Graphs.jl applies that factor by default. kwargs = (; normalize = false) replaces it by $1/2$, which gives the count over the unordered pairs. kwargs = (; endpoints = true) also counts the two ends of every path, which raises every score.
A pair that several shortest paths join gives one unit of score, divided among those paths, because the summand is a fraction of $\sigma_{s,\,t}$. StressCentrality does not divide, and counts the paths.
[137] states the measure of [138] again over the unordered pairs. It divides the measure by its largest value, $(n^2 - 3n + 2) / 2$, which the centre of a star reaches. That is the factor above, over the ordered pairs. No copy of the work of 1977 is available.
Fields
args: Positional arguments for the centrality function.
kwargs: Keyword arguments for the centrality function.
ov: Polarity override.TopologyOnlyasks for the centrality over the network's topology alone, socentrality_polarityanswersnothingandcentrality_graphbuilds the plain graph.nothingleaves the algorithm's declared polarity in force.
Constructors
BetweennessCentrality(; args::Tuple = (), kwargs::NamedTuple = (;), ov::Option{TopologyOnly} = nothing) -> BetweennessCentralityKeywords correspond to the struct's fields.
Validation
- No entry of
argsis anAbstractMatrix. The weights reach a centrality algorithm through the graph thatcentrality_graphbuilds for itscentrality_polarity, and never throughargs.
Examples
julia> BetweennessCentrality()BetweennessCentrality args ┼ Tuple{}: () kwargs ┼ @NamedTuple{}: NamedTuple() ov ┴ nothingRelated
AbstractCentralityAlgorithmcentrality_polarityDistancePolarityTopologyOnlyGraphs.betweenness_centrality
References
- [138] L. C. Freeman. A set of measures of centrality based on betweenness. Sociometry 40, 35–41 (1977).
- [137] L. C. Freeman. Centrality in social networks conceptual clarification. Social Networks 1, 215–239 (1979). Pages 223-224. The original source of this formulation was not found. The formulation follows this work and is not checked against the original.
- [139] U. Brandes. A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology 25, 163–177 (2001). Sections 2 and 4, for the sum over the ordered pairs and the algorithm that
Graphs.jlruns.
PortfolioOptimisers.ClosenessCentrality — Type
struct ClosenessCentrality{__T_args, __T_kwargs, __T_ov} <: AbstractCentralityAlgorithmScores each asset by the reciprocal of its mean shortest-path distance to the others.
ClosenessCentrality selects the closeness centrality of Graphs.jl. It measures how near an asset is to all other assets.
It declares DistancePolarity, unless ov overrides it. It sums the lengths of shortest paths, so its weights must be distances. It reads them on both branches, so its answer on a NetworkEstimator source is different from the unweighted one. Over twenty assets, the measured largest absolute change is 0.713 on a triangulated maximally filtered graph and 0.538 on a tree. Set ov to TopologyOnly to withdraw the declaration and read the topology alone.
Mathematical definition
\[\begin{align} \mathrm{CC}_i &= \dfrac{r_i}{\displaystyle\sum_{j \in \mathcal{R}_i} \ell_{i,\,j}} \cdot \dfrac{r_i}{n - 1}\,, \end{align}\]
Where:
- $\mathrm{CC}_i$: Closeness centrality of asset $i$.
- $\mathcal{R}_i$: Set of assets other than asset $i$ that asset $i$ reaches.
- $r_i$: Cardinality of $\mathcal{R}_i$.
- $\ell_{i,\,j}$: Length of a shortest path between assets $i$ and $j$. It counts the edges on an unweighted network, and sums the edge weights on a weighted one.
- $n$: Number of assets, which is the number of vertices of the network.
The first factor is the reciprocal of the mean length from asset $i$ to the assets that it reaches. The second factor is the share of the assets that it reaches. Graphs.jl applies the second factor by default, and kwargs = (; normalize = false) removes it. On a connected network, $r_i = n - 1$ and the second factor is one. The two settings agree there, and are different only on a network with more than one component.
An asset that reaches no asset scores zero, and not an infinity. The sum in the denominator is over $\mathcal{R}_i$ alone, so an unreachable asset never enters it.
[137] states the first factor for a connected network, as the reciprocal of the mean distance. It gives the factor to two earlier works, and no copy of those works is available. The second factor extends the measure to a network with more than one component. It is the rule of Graphs.jl, and no available work states it first.
Fields
args: Positional arguments for the centrality function.
kwargs: Keyword arguments for the centrality function.
ov: Polarity override.TopologyOnlyasks for the centrality over the network's topology alone, socentrality_polarityanswersnothingandcentrality_graphbuilds the plain graph.nothingleaves the algorithm's declared polarity in force.
Constructors
ClosenessCentrality(; args::Tuple = (), kwargs::NamedTuple = (;), ov::Option{TopologyOnly} = nothing) -> ClosenessCentralityKeywords correspond to the struct's fields.
Validation
- No entry of
argsis anAbstractMatrix. The weights reach a centrality algorithm through the graph thatcentrality_graphbuilds for itscentrality_polarity, and never throughargs.
Examples
julia> ClosenessCentrality()ClosenessCentrality args ┼ Tuple{}: () kwargs ┼ @NamedTuple{}: NamedTuple() ov ┴ nothingRelated
AbstractCentralityAlgorithmcentrality_polarityDistancePolarityTopologyOnlyGraphs.closeness_centrality
References
- [137] L. C. Freeman. Centrality in social networks conceptual clarification. Social Networks 1, 215–239 (1979). Pages 225-226. The original source of this formulation was not found. The formulation follows this work and is not checked against the original.
PortfolioOptimisers.DegreeCentrality — Type
struct DegreeCentrality{__T_kind, __T_kwargs} <: AbstractCentralityAlgorithmCounts the network edges that touch each asset, divided by the number of other assets.
DegreeCentrality selects the degree centrality of Graphs.jl. It is the simplest score of the family, and the default ct of CentralityEstimator.
It declares no polarity, and runs on the plain graph. Graphs._degree_centrality counts edges and does not read their weights. The sep of the estimator has an effect on it. The unweighted route reads the separation closure that phylogeny_matrix builds, so HopCount(; n = 2) changes this answer.
It has no ov field, and TopologyOnly does not apply to it. It already reads the topology alone, so it has no declaration to withdraw. DegreeCentrality(; ov = TopologyOnly()) raises a MethodError.
Mathematical definition
The degree vector of an adjacency matrix $\mathbf{A}$ over $n$ assets is
\[\begin{align} \mathbf{D}_n &= \mathbf{A}\,\mathbf{1}_n\,, \end{align}\]
Where:
- $\mathbf{D}_n$: Degree vector of the network, whose $i$-th entry counts the edges that touch asset $i$.
- $\mathbf{A}$: Adjacency matrix of the network. It is binary on the unweighted route, and carries the edge weights of its own branch where the algorithm declares a polarity.
- $\mathbf{1}_n$: Column vector of ones of length $n$.
- $n$: Number of assets, which is the number of vertices of the network.
Graphs._degree_centrality normalises that vector by default, and this type returns $\mathbf{D}_n / (n - 1)$, and not $\mathbf{D}_n$. kwargs = (; normalize = false) gives $\mathbf{D}_n$.
The factor is the only difference, and it does not change the ranking. average_centrality is linear in the score vector, so the average changes by the same factor.
The three kind values agree on these structures
kind = 0 counts the total degree, kind = 1 the in-degree, and kind = 2 the out-degree. Every graph that this library builds is undirected, and on an undirected graph the three are one number. On the same tree, kind = 0, 1 and 2 give the same vector. The field exists because Graphs.jl takes it, and it selects nothing here.
Fields
kind: Degree to count.0counts the total degree,1the in-degree, and2the out-degree.
kwargs: Keyword arguments for the centrality function.
Constructors
DegreeCentrality(; kind::Integer = 0, kwargs::NamedTuple = (;)) -> DegreeCentralityKeywords correspond to the struct's fields.
Validation
0 <= kind <= 2.
Examples
julia> DegreeCentrality(; kind = 1)DegreeCentrality kind ┼ Int64: 1 kwargs ┴ @NamedTuple{}: NamedTuple()Related
References
PortfolioOptimisers.EigenvectorCentrality — Type
struct EigenvectorCentrality{__T_ov} <: AbstractCentralityAlgorithmScores each asset by the leading eigenvector of the network's adjacency matrix.
EigenvectorCentrality selects the eigenvector centrality of Graphs.jl. The score of an asset grows with the scores of its neighbours.
Mathematical definition
\[\begin{align} \mathbf{EC}_n &= \dfrac{1}{\lambda_{\mathrm{max}}}\,\mathbf{A}\,\mathbf{q}_{\mathrm{max}}\,, \end{align}\]
Where:
- $\mathbf{EC}_n$: Eigenvector centrality vector of the network.
- $\mathbf{A}$: Adjacency matrix of the network. It is binary on the unweighted route, and carries the edge weights of its own branch where the algorithm declares a polarity.
- $\lambda_{\mathrm{max}}$: Largest eigenvalue of $\mathbf{A}$.
- $\mathbf{q}_{\mathrm{max}}$: Eigenvector of $\lambda_{\mathrm{max}}$.
The right-hand side is $\mathbf{q}_{\mathrm{max}}$, so the score is the leading eigenvector, with the normalisation of the eigensolver. Graphs.jl returns it with unit 2-norm, and takes the absolute value of every entry. By the Perron-Frobenius theorem, the entries of the leading eigenvector of a non-negative matrix have one sign, so the absolute value changes no order. The returned vector agrees with the formula above to the precision of the eigensolver, which changes by a few ulps between calls on one graph.
The formula above is Equation 4 of [117]. [140] states the measure as $\lambda \mathbf{e} = \mathbf{R}\,\mathbf{e}$, and prefers the largest eigenvalue. It gives the measure to a work of 1972 by the same author, and no copy of that work is available.
It declares SimilarityPolarity, unless ov overrides it, and it is the only member that declares it. It is the leading eigenvector of the adjacency matrix, so a stronger link must give a larger entry. It reads weights on the similarity branch alone. A minimised distance selects a tree, and a tree carries no similarity. This algorithm runs unweighted on a tree, and does not receive the wrong quantity. Set ov to TopologyOnly to withdraw the declaration and read the topology alone.
The weights change this answer less than they change the answers of the shortest path algorithms, but they change it. The weighted and the unweighted vectors are different, and their correlation is high. A withdrawal of the weights also changes the $\lambda_{\mathrm{max}}$ of the structure.
Fields
ov: Polarity override.TopologyOnlyasks for the centrality over the network's topology alone, socentrality_polarityanswersnothingandcentrality_graphbuilds the plain graph.nothingleaves the algorithm's declared polarity in force.
Constructors
EigenvectorCentrality(; ov::Option{TopologyOnly} = nothing) -> EigenvectorCentralityKeywords correspond to the struct's fields.
Examples
julia> EigenvectorCentrality()EigenvectorCentrality ov ┴ nothingRelated
AbstractCentralityAlgorithmcentrality_polaritySimilarityPolarityTopologyOnlyGraphs.eigenvector_centrality
References
- [117] D. Cajas. A Graph Theory Approach to Portfolio Optimization. Available at SSRN 4602019 (2023). Section 2.3.2, Equation 4.
- [140] P. Bonacich. Power and centrality: a family of measures. American Journal of Sociology 92, 1170–1182 (1987). Page 1172, Equations 1-2. The original source of this formulation was not found. The formulation follows this work and is not checked against the original.
PortfolioOptimisers.KatzCentrality — Type
struct KatzCentrality{__T_alpha} <: AbstractCentralityAlgorithmScores each asset by every walk that reaches it, discounted geometrically by the walk's length.
KatzCentrality selects the Katz centrality of Graphs.jl. It counts the walks that reach an asset, and the attenuation factor alpha discounts each walk by its length.
It declares no polarity, and runs on the plain graph. Graphs.katz_centrality reads the adjacency matrix with the element type Bool, through adjacency_matrix(g, Bool). A weight other than 0 or 1 cannot become a Bool, so on a weighted graph the call throws an InexactError. The unweighted route is therefore necessary for this algorithm.
It has no ov field, and TopologyOnly does not apply to it. It already reads the topology alone, so it has no declaration to withdraw. KatzCentrality(; ov = TopologyOnly()) raises a MethodError.
Mathematical definition
\[\begin{align} \boldsymbol{v} &= \sum_{k \geq 0} \alpha^{k}\,\mathbf{A}^{k}\,\mathbf{1}_n = \left(\mathbf{I}_n - \alpha\,\mathbf{A}\right)^{-1}\mathbf{1}_n\,, \\ \mathbf{KC}_n &= \dfrac{\boldsymbol{v}}{\lVert \boldsymbol{v} \rVert_2}\,. \end{align}\]
Where:
- $\boldsymbol{v}$: Walk sum of the network, whose $i$-th entry adds up every walk that reaches asset $i$, discounted by $\alpha$ for each edge on it.
- $\mathbf{KC}_n$: Katz centrality vector, the walk sum at unit 2-norm.
- $\alpha$: Attenuation factor,
alpha. - $\mathbf{A}$: Adjacency matrix of the network. It is binary on the unweighted route, and carries the edge weights of its own branch where the algorithm declares a polarity.
- $\lambda_{\mathrm{max}}$: Largest eigenvalue of $\mathbf{A}$.
- $\mathbf{I}_n$: Identity matrix of order $n$.
- $\mathbf{1}_n$: Column vector of ones of length $n$.
- $n$: Number of assets, which is the number of vertices of the network.
The series converges to the resolvent only for $\alpha < 1 / \lambda_{\mathrm{max}}$, and the two right-hand sides are equal only there. Outside that range, the resolvent is defined at almost every $\alpha$, but its vector is not a sum of walks.
[141] sums the walks of length one and more, $\left(\mathbf{I}_n - \alpha\,\mathbf{A}\right)^{-1} - \mathbf{I}_n$. On $\mathbf{1}_n$, that sum gives $\boldsymbol{v} - \mathbf{1}_n$. [141] then divides by a constant that depends on $n$ and $\alpha$. Graphs.jl keeps the walk of length zero, and scales to unit 2-norm. The ranking is the same, and the scores are not proportional. [141] states the same bound on $\alpha$.
alpha must be below the reciprocal of the largest eigenvalue
Above the bound, the linear solve still returns a vector, but the vector is not a centrality. Some of its scores become negative, and a negative centrality has no meaning.
The constructor cannot check this. $\lambda_{\mathrm{max}}$ is a property of the graph, and centrality_graph builds the graph later. The constructor checks only alpha > 0, and the caller must obey the bound. A dense network has a larger $\lambda_{\mathrm{max}}$, and so a smaller bound. A value that holds on a tree can fail on a triangulated maximally filtered graph over the same assets. The default alpha = 0.3 is not safe for every shape of graph.
Fields
alpha: Attenuation factor. The series of walks converges only whenalphais below the reciprocal of the largest eigenvalue of the adjacency matrix, and the constructor does not check it.
Constructors
KatzCentrality(; alpha::Number = 0.3) -> KatzCentralityKeywords correspond to the struct's fields.
Validation
alpha > 0.
Examples
julia> KatzCentrality(; alpha = 0.1)KatzCentrality alpha ┴ Float64: 0.1Related
References
- [141] L. Katz. A new status index derived from sociometric analysis. Psychometrika 18, 39–43 (1953). Pages 41-42.
PortfolioOptimisers.Pagerank — Type
struct Pagerank{__T_n, __T_alpha, __T_epsilon} <: AbstractCentralityAlgorithmScores each asset by the stationary distribution of a damped random walk over the network.
Pagerank selects the PageRank of Graphs.jl. The score of an asset grows with the scores of the assets that link to it. The damping factor alpha, the number of iterations n and the convergence tolerance epsilon control the iteration.
It declares no polarity, and runs on the plain graph. Graphs.pagerank reads only outdegree and inneighbors, and never reads an edge weight. The weighted graph and the plain graph give the same vector. As for DegreeCentrality, the sep of the estimator has an effect on it, because it reads the separation closure and not the structure.
It has no ov field, and TopologyOnly does not apply to it. It already reads the topology alone, so it has no declaration to withdraw. Pagerank(; ov = TopologyOnly()) raises a MethodError.
Mathematical definition
\[\begin{align} \mathrm{PR}_i &= \dfrac{1 - \alpha}{n} + \dfrac{\alpha}{n}\sum_{j \in \mathcal{D}} \mathrm{PR}_j + \alpha \sum_{j \in \mathcal{I}_i} \dfrac{\mathrm{PR}_j}{k_j}\,, \end{align}\]
Where:
- $\mathrm{PR}_i$: PageRank of asset $i$, the share of time that the damped walk is at asset $i$.
- $\alpha$: Damping factor,
alpha. It is the probability that the walk follows an edge, and does not teleport. - $\mathcal{I}_i$: Set of assets with an edge into asset $i$.
- $k_j$: Number of edges that leave asset $j$.
- $\mathcal{D}$: Set of dangling assets, which no edge leaves.
- $n$: Number of assets, which is the number of vertices of the network.
The three terms are the three moves of the walk. It teleports to an asset drawn uniformly, it teleports out of a dangling asset that it cannot leave, or it follows one of the edges into asset $i$. Every score is non-negative, and the vector sums to one. The members of the family that count edges or paths do not have this property.
[142] writes $\mathrm{PR}_i = (1 - \alpha) + \alpha \sum_{j \in \mathcal{I}_i} \mathrm{PR}_j / k_j$, with no division by $n$ and no term for the dangling assets. The division by $n$ makes the vector sum to one, as [142] states. The uniform spread of the mass of the dangling assets is the rule of Graphs.jl, and no available work states it first.
Every network that this library builds is undirected. On it, $\mathcal{I}_i$ is the neighbourhood of asset $i$, and $k_j$ is the degree of asset $j$. On a connected undirected network, the solution goes to a scaled copy of the degree vector of DegreeCentrality as $\alpha$ goes to one. A smaller $\alpha$ mixes that limit with the uniform distribution.
Fields
n: Largest number of iterations.Graphs.pagerankraises an error if the scores do not converge in this number of sweeps.
alpha: Damping factor. It is the probability that the walk follows an edge, and does not teleport.
epsilon: Convergence threshold. A sweep converges when the L1 change of the score vector falls below this value multiplied by the number of assets.
Constructors
Pagerank(; n::Integer = 100, alpha::Number = 0.85, epsilon::Number = 1e-6) -> PagerankKeywords correspond to the struct's fields.
Validation
n > 0.0 < alpha < 1.epsilon > 0.
Examples
julia> Pagerank(; alpha = 0.9, n = 200, epsilon = 1e-8)Pagerank n ┼ Int64: 200 alpha ┼ Float64: 0.9 epsilon ┴ Float64: 1.0e-8Related
References
- [142] S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems 30, 107–117 (1998). Section 2.1.1. The original source of this formulation was not found. The formulation follows this work and is not checked against the original.
PortfolioOptimisers.RadialityCentrality — Type
struct RadialityCentrality{__T_ov} <: AbstractCentralityAlgorithmScores each asset by its mean shortest-path distance, measured against the network's diameter.
RadialityCentrality selects the radiality centrality of Graphs.jl. It measures how near an asset is to all other assets, relative to the diameter of the network.
It declares DistancePolarity, unless ov overrides it. It reads the lengths of shortest paths against the diameter of the graph, so its weights must be distances. It reads them on both branches, and the weights change its answer. Over twenty assets, the measured largest absolute change is 0.248 on a triangulated maximally filtered graph and 0.234 on a tree. Set ov to TopologyOnly to withdraw the declaration and read the topology alone.
Mathematical definition
\[\begin{align} \bar{\ell}_i &= \dfrac{1}{n - 1}\sum_{j} \ell_{i,\,j}\,, \\ \mathrm{RC}_i &= \dfrac{D + 1 - \bar{\ell}_i}{D}\,. \end{align}\]
Where:
- $\bar{\ell}_i$: Mean length from asset $i$ to every other asset.
- $\mathrm{RC}_i$: Radiality centrality of asset $i$.
- $D$: Diameter of the network, the largest $\ell_{i,\,j}$ over every pair.
- $\ell_{i,\,j}$: Length of a shortest path between assets $i$ and $j$. It counts the edges on an unweighted network, and sums the edge weights on a weighted one.
- $n$: Number of assets, which is the number of vertices of the network.
The diameter makes this score different from ClosenessCentrality. Closeness takes the reciprocal of the mean length. Radiality subtracts the mean length from the diameter plus one, so the score states how far inside the reach of the network an asset is.
The smallest score is $1/D$, for an asset whose mean length is equal to the diameter. On an unweighted network every length is at least $1$, so the largest score is $1$, for an asset one edge away from every other asset. On a weighted network a length can be less than $1$, and a score can be larger than $1$. The bounds change with $D$, so the scores of two networks are comparable only when the two have the same diameter.
[139] states the formula, and gives it to [143]. No copy of that work is available. [139] sums $D + 1 - \ell_{i,\,j}$ over every asset $j$, with the asset $i$, and divides by $(n - 1) D$. In that form every score is larger by $(D + 1) / ((n - 1) D)$, so the ranking is the same. The form above, which Graphs.jl computes, does not include $j = i$.
Fields
ov: Polarity override.TopologyOnlyasks for the centrality over the network's topology alone, socentrality_polarityanswersnothingandcentrality_graphbuilds the plain graph.nothingleaves the algorithm's declared polarity in force.
Constructors
RadialityCentrality(; ov::Option{TopologyOnly} = nothing) -> RadialityCentralityKeywords correspond to the struct's fields.
Examples
julia> RadialityCentrality()RadialityCentrality ov ┴ nothingRelated
AbstractCentralityAlgorithmcentrality_polarityDistancePolarityTopologyOnlyGraphs.radiality_centrality
References
- [143] T. W. Valente and R. K. Foreman. Integration and radiality: measuring the extent of an individual's connectedness and reachability in a network. Social Networks 20, 89–105 (1998).
- [139] U. Brandes. A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology 25, 163–177 (2001). Section 4. The original source of this formulation was not found. The formulation follows this work and is not checked against the original.
PortfolioOptimisers.StressCentrality — Type
struct StressCentrality{__T_args, __T_kwargs, __T_ov} <: AbstractCentralityAlgorithmCounts the shortest paths of the network that pass through each asset.
StressCentrality selects the stress centrality of Graphs.jl. It counts the shortest paths that go through each asset.
It declares DistancePolarity, unless ov overrides it. It counts shortest paths, so its weights must be distances. As for BetweennessCentrality, the weights do not change it on a tree, where the structure alone sets the shortest paths. They change it on the similarity branch. Set ov to TopologyOnly to withdraw the declaration and read the topology alone.
Mathematical definition
\[\begin{align} \mathrm{SC}_i &= \sum_{s \neq i \neq t} \sigma_{s,\,t}(i)\,, \end{align}\]
Where:
- $\mathrm{SC}_i$: Stress centrality of asset $i$.
- $\sigma_{s,\,t}(i)$: Number of the shortest paths between assets $s$ and $t$ that pass through asset $i$.
The sum runs over the ordered pairs of distinct assets, so an undirected network counts each pair two times. The score has no normalisation, so it is a count and not a rate. It grows with the size of the network. The scores of two networks are comparable only when the two have the same number of assets.
[139] states this sum, and gives it to [144]. No copy of that work is available.
It is the sum of BetweennessCentrality without the division by $\sigma_{s,\,t}$. A pair that many shortest paths join adds many units here, and one unit to the betweenness. This score measures how many shortest paths go through an asset. The betweenness measures the share of the shortest paths of each pair that go through it.
Fields
args: Positional arguments for the centrality function.
kwargs: Keyword arguments for the centrality function.
ov: Polarity override.TopologyOnlyasks for the centrality over the network's topology alone, socentrality_polarityanswersnothingandcentrality_graphbuilds the plain graph.nothingleaves the algorithm's declared polarity in force.
Constructors
StressCentrality(; args::Tuple = (), kwargs::NamedTuple = (;), ov::Option{TopologyOnly} = nothing) -> StressCentralityKeywords correspond to the struct's fields.
Validation
- No entry of
argsis anAbstractMatrix. The weights reach a centrality algorithm through the graph thatcentrality_graphbuilds for itscentrality_polarity, and never throughargs.
Examples
julia> StressCentrality()StressCentrality args ┼ Tuple{}: () kwargs ┼ @NamedTuple{}: NamedTuple() ov ┴ nothingRelated
References
- [144] A. Shimbel. Structural parameters of communication networks. The Bulletin of Mathematical Biophysics 15, 501–507 (1953).
- [139] U. Brandes. A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology 25, 163–177 (2001). Section 2. The original source of this formulation was not found. The formulation follows this work and is not checked against the original.
PortfolioOptimisers.calc_centrality — Function
calc_centrality(ct::AbstractCentralityAlgorithm, g::Graphs.AbstractGraph)Compute the centrality score of every vertex of a graph with the algorithm ct.
The type of ct selects one routine of Graphs.jl.
g can be weighted or unweighted, and this function does not check which. The default distmx of every routine of Graphs.jl that takes one is weights(g). centrality_graph makes the choice one time, and this function only calls the routine. centrality_graph does not give a weighted graph to an algorithm that declares no polarity, because Graphs.katz_centrality throws an InexactError on a weighted graph.
Algorithm
Select the routine of
Graphs.jlthat the type ofctnames, from the list under# Arguments.Splat the configuration of
ctinto that call.BetweennessCentrality,ClosenessCentralityandStressCentrality:argsandkwargs.DegreeCentrality:kindandkwargs.KatzCentrality:alpha.Pagerank:alpha,nandepsilon.EigenvectorCentralityandRadialityCentrality: nothing.
Return the scores of that routine, one for each vertex of
g.
Arguments
ct: Centrality algorithm.ct::BetweennessCentrality:Graphs.betweenness_centrality.ct::ClosenessCentrality:Graphs.closeness_centrality.ct::DegreeCentrality:Graphs._degree_centrality.ct::EigenvectorCentrality:Graphs.eigenvector_centrality.ct::KatzCentrality:Graphs.katz_centrality.ct::Pagerank:Graphs.pagerank.ct::RadialityCentrality:Graphs.radiality_centrality.ct::StressCentrality:Graphs.stress_centrality.
g: Graph to score.
Returns
scores::VecNum: One centrality score for each vertex of the graph.
Related
References
- [117]
- D. Cajas. A Graph Theory Approach to Portfolio Optimization. Available at SSRN 4602019 (2023).
- [136]
- F. Pozzi, T. Di Matteo and T. Aste. Spread of risk across financial markets: better to invest in the peripheries. Scientific Reports 3, 1665 (2013).
- [137]
- L. C. Freeman. Centrality in social networks conceptual clarification. Social Networks 1, 215–239 (1979).
- [138]
- L. C. Freeman. A set of measures of centrality based on betweenness. Sociometry 40, 35–41 (1977).
- [139]
- U. Brandes. A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology 25, 163–177 (2001).
- [140]
- P. Bonacich. Power and centrality: a family of measures. American Journal of Sociology 92, 1170–1182 (1987).
- [141]
- L. Katz. A new status index derived from sociometric analysis. Psychometrika 18, 39–43 (1953).
- [142]
- S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems 30, 107–117 (1998).
- [143]
- T. W. Valente and R. K. Foreman. Integration and radiality: measuring the extent of an individual's connectedness and reachability in a network. Social Networks 20, 89–105 (1998).
- [144]
- A. Shimbel. Structural parameters of communication networks. The Bulletin of Mathematical Biophysics 15, 501–507 (1953).