This repository has been archived by the owner on Oct 8, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 184
/
stress.jl
77 lines (66 loc) · 2.21 KB
/
stress.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
"""
stress_centrality(g[, vs])
stress_centrality(g, k)
Calculate the [stress centrality](http://med.bioinf.mpi-inf.mpg.de/netanalyzer/help/2.7/#stressDist)
of a graph `g` across all vertices, a specified subset of vertices `vs`, or a random subset of `k`
vertices. Return a vector representing the centrality calculated for each node in `g`.
The stress centrality of a vertex ``n`` is defined as the number of shortest paths passing through ``n``.
### References
- Barabási, A.L., Oltvai, Z.N.: Network biology: understanding the cell's functional organization. Nat Rev Genet 5 (2004) 101-113
- Shimbel, A.: Structural parameters of communication networks. Bull Math Biophys 15 (1953) 501-507.
# Examples
```jldoctest
julia> using LightGraphs
julia> stress_centrality(star_graph(3))
3-element Array{Int64,1}:
2
0
0
julia> stress_centrality(cycle_graph(4))
4-element Array{Int64,1}:
2
2
2
2
```
"""
function stress_centrality(g::AbstractGraph, vs=vertices(g))
n_v = nv(g)
k = length(vs)
isdir = is_directed(g)
stress = zeros(Int, n_v)
for s in vs
if degree(g, s) > 0
state = dijkstra_shortest_paths(g, s; allpaths=true, trackvertices=true)
_stress_accumulate_basic!(stress, state, g, s)
end
end
return stress
end
stress_centrality(g::AbstractGraph, k::Integer) =
stress_centrality(g, sample(vertices(g), k))
function _stress_accumulate_basic!(stress::Vector{<:Integer},
state::DijkstraState,
g::AbstractGraph,
si::Integer)
n_v = length(state.parents) # this is the ttl number of vertices
δ = zeros(Int, n_v)
P = state.predecessors
laststress = copy(stress)
# make sure the source index has no parents.
P[si] = []
# we need to order the source vertices by decreasing distance for this to work.
S = reverse(state.closest_vertices) #Replaced sortperm with this
for w in S # w is the farthest vertex from si
for v in P[w] # get the predecessors of w
if v > 0
δ[v] += δ[w] + 1 # increment sp of pred
end
end
δ[w] *= length(P[w]) # adjust the # of sps of vertex
if w != si
stress[w] += δ[w]
end
end
return nothing
end