## Overview ¶

Package network provides network analysis functions.

### Index ¶

- func Betweenness(g graph.Graph) map[int64]float64
- func BetweennessWeighted(g graph.Weighted, p path.AllShortest) map[int64]float64
- func Closeness(g graph.Graph, p path.AllShortest) map[int64]float64
- func Diffuse(dst, h map[int64]float64, by Laplacian, t float64) map[int64]float64
- func DiffuseToEquilibrium(dst, h map[int64]float64, by Laplacian, tol float64, iters int) (eq map[int64]float64, ok bool)
- func EdgeBetweenness(g graph.Graph) map[[2]int64]float64
- func EdgeBetweennessWeighted(g graph.Weighted, p path.AllShortest) map[[2]int64]float64
- func Farness(g graph.Graph, p path.AllShortest) map[int64]float64
- func HITS(g graph.Directed, tol float64) map[int64]HubAuthority
- func Harmonic(g graph.Graph, p path.AllShortest) map[int64]float64
- func PageRank(g graph.Directed, damp, tol float64) map[int64]float64
- func PageRankSparse(g graph.Directed, damp, tol float64) map[int64]float64
- func Residual(g graph.Graph, p path.AllShortest) map[int64]float64
- type HubAuthority
- type Laplacian

### func Betweenness ¶

func Betweenness(g graph.Graph) map[int64]float64

Betweenness returns the non-zero betweenness centrality for nodes in the unweighted graph g.

C_B(v) = \sum_{s ≠ v ≠ t ∈ V} (\sigma_{st}(v) / \sigma_{st})

where \sigma_{st} and \sigma_{st}(v) are the number of shortest paths from s to t, and the subset of those paths containing v respectively.

### func BetweennessWeighted ¶

func BetweennessWeighted(g graph.Weighted, p path.AllShortest) map[int64]float64

BetweennessWeighted returns the non-zero betweenness centrality for nodes in the weighted graph g used to construct the given shortest paths.

C_B(v) = \sum_{s ≠ v ≠ t ∈ V} (\sigma_{st}(v) / \sigma_{st})

where \sigma_{st} and \sigma_{st}(v) are the number of shortest paths from s to t, and the subset of those paths containing v respectively.

### func Closeness ¶

func Closeness(g graph.Graph, p path.AllShortest) map[int64]float64

Closeness returns the closeness centrality for nodes in the graph g used to construct the given shortest paths.

C(v) = 1 / \sum_u d(u,v)

For directed graphs the incoming paths are used. Infinite distances are not considered.

### func Diffuse ¶

func Diffuse(dst, h map[int64]float64, by Laplacian, t float64) map[int64]float64

Diffuse performs a heat diffusion across nodes of the undirected graph described by the given Laplacian using the initial heat distribution, h, according to the Laplacian with a diffusion time of t. The resulting heat distribution is returned, written into the map dst and returned,

d = exp(-Lt)×h

where L is the graph Laplacian. Indexing into h and dst is defined by the Laplacian Index field. If dst is nil, a new map is created.

Nodes without corresponding entries in h are given an initial heat of zero, and entries in h without a corresponding node in the original graph are not altered when written to dst.

### func DiffuseToEquilibrium ¶

func DiffuseToEquilibrium(dst, h map[int64]float64, by Laplacian, tol float64, iters int) (eq map[int64]float64, ok bool)

DiffuseToEquilibrium performs a heat diffusion across nodes of the graph described by the given Laplacian using the initial heat distribution, h, according to the Laplacian until the update function

h_{n+1} = h_n - L×h_n

results in a 2-norm update difference within tol, or iters updates have been made. The resulting heat distribution is returned as eq, written into the map dst, and a boolean indicating whether the equilibrium converged to within tol. Indexing into h and dst is defined by the Laplacian Index field. If dst is nil, a new map is created.

Nodes without corresponding entries in h are given an initial heat of zero, and entries in h without a corresponding node in the original graph are not altered when written to dst.

### func EdgeBetweenness ¶

func EdgeBetweenness(g graph.Graph) map[[2]int64]float64

EdgeBetweenness returns the non-zero betweenness centrality for edges in the unweighted graph g. For an edge e the centrality C_B is computed as

C_B(e) = \sum_{s ≠ t ∈ V} (\sigma_{st}(e) / \sigma_{st}),

where \sigma_{st} and \sigma_{st}(e) are the number of shortest paths from s to t, and the subset of those paths containing e, respectively.

If g is undirected, edges are retained such that u.ID < v.ID where u and v are the nodes of e.

### func EdgeBetweennessWeighted ¶

func EdgeBetweennessWeighted(g graph.Weighted, p path.AllShortest) map[[2]int64]float64

EdgeBetweennessWeighted returns the non-zero betweenness centrality for edges in the weighted graph g. For an edge e the centrality C_B is computed as

C_B(e) = \sum_{s ≠ t ∈ V} (\sigma_{st}(e) / \sigma_{st}),

where \sigma_{st} and \sigma_{st}(e) are the number of shortest paths from s to t, and the subset of those paths containing e, respectively.

If g is undirected, edges are retained such that u.ID < v.ID where u and v are the nodes of e.

### func Farness ¶

func Farness(g graph.Graph, p path.AllShortest) map[int64]float64

Farness returns the farness for nodes in the graph g used to construct the given shortest paths.

F(v) = \sum_u d(u,v)

For directed graphs the incoming paths are used. Infinite distances are not considered.

### func HITS ¶

func HITS(g graph.Directed, tol float64) map[int64]HubAuthority

HITS returns the Hyperlink-Induced Topic Search hub-authority scores for nodes of the directed graph g. HITS terminates when the 2-norm of the vector difference between iterations is below tol. The returned map is keyed on the graph node IDs.

### func Harmonic ¶

func Harmonic(g graph.Graph, p path.AllShortest) map[int64]float64

Harmonic returns the harmonic centrality for nodes in the graph g used to construct the given shortest paths.

H(v)= \sum_{u ≠ v} 1 / d(u,v)

For directed graphs the incoming paths are used. Infinite distances are not considered.

### func PageRank ¶

func PageRank(g graph.Directed, damp, tol float64) map[int64]float64

PageRank returns the PageRank weights for nodes of the directed graph g using the given damping factor and terminating when the 2-norm of the vector difference between iterations is below tol. The returned map is keyed on the graph node IDs.

### func PageRankSparse ¶

func PageRankSparse(g graph.Directed, damp, tol float64) map[int64]float64

PageRankSparse returns the PageRank weights for nodes of the sparse directed graph g using the given damping factor and terminating when the 2-norm of the vector difference between iterations is below tol. The returned map is keyed on the graph node IDs.

### func Residual ¶

func Residual(g graph.Graph, p path.AllShortest) map[int64]float64

Residual returns the Dangalchev's residual closeness for nodes in the graph g used to construct the given shortest paths.

C(v)= \sum_{u ≠ v} 1 / 2^d(u,v)

For directed graphs the incoming paths are used. Infinite distances are not considered.

### type HubAuthority ¶

type HubAuthority struct { Hub float64 Authority float64 }

HubAuthority is a Hyperlink-Induced Topic Search hub-authority score pair.

### type Laplacian ¶

type Laplacian struct { // Matrix holds the Laplacian matrix. mat.Matrix // Nodes holds the input graph nodes. Nodes []graph.Node // Index is a mapping from the graph // node IDs to row and column indices. Index map[int64]int }

Laplacian is a graph Laplacian matrix.

### func NewLaplacian ¶

func NewLaplacian(g graph.Undirected) Laplacian

NewLaplacian returns a Laplacian matrix for the simple undirected graph g. The Laplacian is defined as D-A where D is a diagonal matrix holding the degree of each node and A is the graph adjacency matrix of the input graph. If g contains self edges, NewLaplacian will panic.

### func NewRandomWalkLaplacian ¶

func NewRandomWalkLaplacian(g graph.Graph, damp float64) Laplacian

NewRandomWalkLaplacian returns a damp-scaled random walk Laplacian matrix for the simple graph g. The random walk Laplacian is defined as I-D^(-1)A where D is a diagonal matrix holding the degree of each node and A is the graph adjacency matrix of the input graph. If g contains self edges, NewRandomWalkLaplacian will panic.

### func NewSymNormLaplacian ¶

func NewSymNormLaplacian(g graph.Undirected) Laplacian

NewSymNormLaplacian returns a symmetric normalized Laplacian matrix for the simple undirected graph g. The normalized Laplacian is defined as I-D^(-1/2)AD^(-1/2) where D is a diagonal matrix holding the degree of each node and A is the graph adjacency matrix of the input graph. If g contains self edges, NewSymNormLaplacian will panic.