Centrality

PortfolioOptimisers.AbstractCentralityAlgorithm — Type
abstract type AbstractCentralityAlgorithm <: AbstractPhylogenyAlgorithm

Abstract 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 of g. centrality_graph builds g with 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 of g, 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 returns nothing, so a new algorithm runs on the plain graph until it declares a polarity. Declare DistancePolarity for a routine over shortest paths, and SimilarityPolarity for a routine that reads the adjacency matrix.

Arguments

  • ct: The instance of the subtype.

Returns

  • polarity::Option{<:AbstractCentralityPolarity}: The effective polarity, or nothing for an algorithm that reads the topology alone.

Related

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".
source
PortfolioOptimisers.TopologyOnly — Type
struct TopologyOnly <: AbstractAlgorithm

Withdraws 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

source
PortfolioOptimisers.BetweennessCentrality — Type
struct BetweennessCentrality{__T_args, __T_kwargs, __T_ov} <: AbstractCentralityAlgorithm

Scores 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. TopologyOnly asks for the centrality over the network's topology alone, so centrality_polarity answers nothing and centrality_graph builds the plain graph. nothing leaves the algorithm's declared polarity in force.

Constructors

BetweennessCentrality(;    args::Tuple = (),    kwargs::NamedTuple = (;),    ov::Option{TopologyOnly} = nothing) -> BetweennessCentrality

Keywords correspond to the struct's fields.

Validation

  • No entry of args is an AbstractMatrix. The weights reach a centrality algorithm through the graph that centrality_graph builds for its centrality_polarity, and never through args.

Examples

julia> BetweennessCentrality()BetweennessCentrality    args ┼ Tuple{}: ()  kwargs ┼ @NamedTuple{}: NamedTuple()      ov ┴ nothing

Related

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.jl runs.
source
PortfolioOptimisers.ClosenessCentrality — Type
struct ClosenessCentrality{__T_args, __T_kwargs, __T_ov} <: AbstractCentralityAlgorithm

Scores 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. TopologyOnly asks for the centrality over the network's topology alone, so centrality_polarity answers nothing and centrality_graph builds the plain graph. nothing leaves the algorithm's declared polarity in force.

Constructors

ClosenessCentrality(;    args::Tuple = (),    kwargs::NamedTuple = (;),    ov::Option{TopologyOnly} = nothing) -> ClosenessCentrality

Keywords correspond to the struct's fields.

Validation

  • No entry of args is an AbstractMatrix. The weights reach a centrality algorithm through the graph that centrality_graph builds for its centrality_polarity, and never through args.

Examples

julia> ClosenessCentrality()ClosenessCentrality    args ┼ Tuple{}: ()  kwargs ┼ @NamedTuple{}: NamedTuple()      ov ┴ nothing

Related

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.
source
PortfolioOptimisers.DegreeCentrality — Type
struct DegreeCentrality{__T_kind, __T_kwargs} <: AbstractCentralityAlgorithm

Counts 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. 0 counts the total degree, 1 the in-degree, and 2 the out-degree.
  • kwargs: Keyword arguments for the centrality function.

Constructors

DegreeCentrality(;    kind::Integer = 0,    kwargs::NamedTuple = (;)) -> DegreeCentrality

Keywords correspond to the struct's fields.

Validation

  • 0 <= kind <= 2.

Examples

julia> DegreeCentrality(; kind = 1)DegreeCentrality    kind ┼ Int64: 1  kwargs ┴ @NamedTuple{}: NamedTuple()

Related

References

  • [117] D. Cajas. A Graph Theory Approach to Portfolio Optimization. Available at SSRN 4602019 (2023). Section 2.3.1, Equation 3.
  • [137] L. C. Freeman. Centrality in social networks conceptual clarification. Social Networks 1, 215–239 (1979). Page 221, for the division by $n - 1$.
source
PortfolioOptimisers.EigenvectorCentrality — Type
struct EigenvectorCentrality{__T_ov} <: AbstractCentralityAlgorithm

Scores 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. TopologyOnly asks for the centrality over the network's topology alone, so centrality_polarity answers nothing and centrality_graph builds the plain graph. nothing leaves the algorithm's declared polarity in force.

Constructors

EigenvectorCentrality(;    ov::Option{TopologyOnly} = nothing) -> EigenvectorCentrality

Keywords correspond to the struct's fields.

Examples

julia> EigenvectorCentrality()EigenvectorCentrality  ov ┴ nothing

Related

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.
source
PortfolioOptimisers.KatzCentrality — Type
struct KatzCentrality{__T_alpha} <: AbstractCentralityAlgorithm

Scores 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 when alpha is below the reciprocal of the largest eigenvalue of the adjacency matrix, and the constructor does not check it.

Constructors

KatzCentrality(;    alpha::Number = 0.3) -> KatzCentrality

Keywords correspond to the struct's fields.

Validation

  • alpha > 0.

Examples

julia> KatzCentrality(; alpha = 0.1)KatzCentrality  alpha ┴ Float64: 0.1

Related

References

  • [141] L. Katz. A new status index derived from sociometric analysis. Psychometrika 18, 39–43 (1953). Pages 41-42.
source
PortfolioOptimisers.Pagerank — Type
struct Pagerank{__T_n, __T_alpha, __T_epsilon} <: AbstractCentralityAlgorithm

Scores 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.pagerank raises 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) -> Pagerank

Keywords 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-8

Related

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.
source
PortfolioOptimisers.RadialityCentrality — Type
struct RadialityCentrality{__T_ov} <: AbstractCentralityAlgorithm

Scores 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. TopologyOnly asks for the centrality over the network's topology alone, so centrality_polarity answers nothing and centrality_graph builds the plain graph. nothing leaves the algorithm's declared polarity in force.

Constructors

RadialityCentrality(;    ov::Option{TopologyOnly} = nothing) -> RadialityCentrality

Keywords correspond to the struct's fields.

Examples

julia> RadialityCentrality()RadialityCentrality  ov ┴ nothing

Related

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.
source
PortfolioOptimisers.StressCentrality — Type
struct StressCentrality{__T_args, __T_kwargs, __T_ov} <: AbstractCentralityAlgorithm

Counts 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. TopologyOnly asks for the centrality over the network's topology alone, so centrality_polarity answers nothing and centrality_graph builds the plain graph. nothing leaves the algorithm's declared polarity in force.

Constructors

StressCentrality(;    args::Tuple = (),    kwargs::NamedTuple = (;),    ov::Option{TopologyOnly} = nothing) -> StressCentrality

Keywords correspond to the struct's fields.

Validation

  • No entry of args is an AbstractMatrix. The weights reach a centrality algorithm through the graph that centrality_graph builds for its centrality_polarity, and never through args.

Examples

julia> StressCentrality()StressCentrality    args ┼ Tuple{}: ()  kwargs ┼ @NamedTuple{}: NamedTuple()      ov ┴ nothing

Related

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.
source
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

  1. Select the routine of Graphs.jl that the type of ct names, from the list under # Arguments.

  2. Splat the configuration of ct into that call.

  3. 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

source

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).