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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
// Copyright ©2015 The Gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package network
import (
"math"
"gonum.org/v1/gonum/floats"
"gonum.org/v1/gonum/graph"
)
// HubAuthority is a Hyperlink-Induced Topic Search hub-authority score pair.
type HubAuthority struct {
Hub float64
Authority float64
}
// 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 HITS(g graph.Directed, tol float64) map[int64]HubAuthority {
nodes := graph.NodesOf(g.Nodes())
// Make a topological copy of g with dense node IDs.
indexOf := make(map[int64]int, len(nodes))
for i, n := range nodes {
indexOf[n.ID()] = i
}
nodesLinkingTo := make([][]int, len(nodes))
nodesLinkedFrom := make([][]int, len(nodes))
for i, n := range nodes {
id := n.ID()
from := g.To(id)
for from.Next() {
u := from.Node()
nodesLinkingTo[i] = append(nodesLinkingTo[i], indexOf[u.ID()])
}
to := g.From(id)
for to.Next() {
v := to.Node()
nodesLinkedFrom[i] = append(nodesLinkedFrom[i], indexOf[v.ID()])
}
}
w := make([]float64, 4*len(nodes))
auth := w[:len(nodes)]
hub := w[len(nodes) : 2*len(nodes)]
for i := range nodes {
auth[i] = 1
hub[i] = 1
}
deltaAuth := w[2*len(nodes) : 3*len(nodes)]
deltaHub := w[3*len(nodes):]
var norm float64
for {
norm = 0
for v := range nodes {
var a float64
for _, u := range nodesLinkingTo[v] {
a += hub[u]
}
deltaAuth[v] = auth[v]
auth[v] = a
norm += a * a
}
norm = math.Sqrt(norm)
for i := range auth {
auth[i] /= norm
deltaAuth[i] -= auth[i]
}
norm = 0
for u := range nodes {
var h float64
for _, v := range nodesLinkedFrom[u] {
h += auth[v]
}
deltaHub[u] = hub[u]
hub[u] = h
norm += h * h
}
norm = math.Sqrt(norm)
for i := range hub {
hub[i] /= norm
deltaHub[i] -= hub[i]
}
if floats.Norm(deltaAuth, 2) < tol && floats.Norm(deltaHub, 2) < tol {
break
}
}
hubAuth := make(map[int64]HubAuthority, len(nodes))
for i, n := range nodes {
hubAuth[n.ID()] = HubAuthority{Hub: hub[i], Authority: auth[i]}
}
return hubAuth
}
|
