-
Notifications
You must be signed in to change notification settings - Fork 2
/
celf.go
80 lines (67 loc) · 1.54 KB
/
celf.go
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
package algorithm
import (
"github.com/jtejido/goim/model"
"github.com/jtejido/goim/util"
"github.com/jtejido/set"
)
const (
default_cascade_samples = 100
)
type celfNode struct {
Node
mg float64
}
type CELF struct {
base
covQueue *util.PriorityQueue
graph *util.Graph
config *util.Config
ic *model.IndependentCascade
}
func NewCELF(graph *util.Graph, config *util.Config, t int) *CELF {
c := new(CELF)
c.graph = graph
c.config = config
c.covQueue = util.NewPriorityQueue(func(n1, n2 interface{}) bool {
if n1.(*celfNode).mg != n2.(*celfNode).mg {
return n2.(*celfNode).mg < n1.(*celfNode).mg // we want sorting in DESC order
}
return n1.(*celfNode).id < n2.(*celfNode).id
})
c.ic = model.NewIndependentCascade(graph, config, t)
return c
}
func (c *CELF) Select(activated set.Set) set.Set {
s := set.NewSet()
for node := range c.graph.Nodes().Iter() {
u := new(celfNode)
u.id = node.(util.Node)
seeds := set.NewSet()
seeds.Add(node.(util.Node))
u.mg = c.ic.Sample(activated, seeds)
c.covQueue.Push(u)
}
s.Add(c.covQueue.Peek().(*celfNode).id)
c.covQueue.Pop()
for s.Len() < c.config.Seeds {
var found bool
for !found {
u := c.covQueue.Peek().(*celfNode)
c.covQueue.Pop()
seeds := set.NewSet()
for node := range s.Iter() {
seeds.Add(node.(util.Node))
}
seeds.Add(u.id)
prev_val := u.mg
u.mg = c.ic.Sample(activated, seeds) - prev_val
if u.mg >= c.covQueue.Peek().(*celfNode).mg {
s.Add(u.id)
found = true
} else {
c.covQueue.Push(u)
}
}
}
return s
}