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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
// 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 gen
import (
"errors"
"fmt"
"golang.org/x/exp/rand"
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/simple"
"gonum.org/v1/gonum/stat/sampleuv"
)
// TunableClusteringScaleFree constructs a subgraph in the destination, dst, of order n.
// The graph is constructed successively starting from an m order graph with one node
// having degree m-1. At each iteration of graph addition, one node is added with m
// additional edges joining existing nodes with probability proportional to the nodes'
// degrees. The edges are formed as a triad with probability, p.
// If src is not nil it is used as the random source, otherwise rand.Float64 and
// rand.Intn are used for the random number generators.
//
// The algorithm is essentially as described in http://arxiv.org/abs/cond-mat/0110452.
func TunableClusteringScaleFree(dst graph.UndirectedBuilder, n, m int, p float64, src rand.Source) error {
if p < 0 || p > 1 {
return fmt.Errorf("gen: bad probability: p=%v", p)
}
if n <= m {
return fmt.Errorf("gen: n <= m: n=%v m=%d", n, m)
}
var (
rnd func() float64
rndN func(int) int
)
if src == nil {
rnd = rand.Float64
rndN = rand.Intn
} else {
r := rand.New(src)
rnd = r.Float64
rndN = r.Intn
}
// Initial condition.
wt := make([]float64, n)
id := make([]int64, n)
for u := 0; u < m; u++ {
un := dst.NewNode()
dst.AddNode(un)
id[u] = un.ID()
// We need to give equal probability for
// adding the first generation of edges.
wt[u] = 1
}
ws := sampleuv.NewWeighted(wt, src)
for i := range wt {
// These weights will organically grow
// after the first growth iteration.
wt[i] = 0
}
// Growth.
for v := m; v < n; v++ {
vn := dst.NewNode()
dst.AddNode(vn)
id[v] = vn.ID()
var u int
pa:
for i := 0; i < m; i++ {
// Triad formation.
if i != 0 && rnd() < p {
// TODO(kortschak): Decide whether the node
// order in this input to permute should be
// sorted first to allow repeatable runs.
for _, w := range permute(graph.NodesOf(dst.From(id[u])), rndN) {
wid := w.ID()
if wid == id[v] || dst.HasEdgeBetween(wid, id[v]) {
continue
}
dst.SetEdge(dst.NewEdge(w, vn))
wt[wid]++
wt[v]++
continue pa
}
}
// Preferential attachment.
for {
var ok bool
u, ok = ws.Take()
if !ok {
return errors.New("gen: depleted distribution")
}
if u == v || dst.HasEdgeBetween(id[u], id[v]) {
continue
}
dst.SetEdge(dst.NewEdge(dst.Node(id[u]), vn))
wt[u]++
wt[v]++
break
}
}
ws.ReweightAll(wt)
}
return nil
}
func permute(n []graph.Node, rnd func(int) int) []graph.Node {
for i := range n[:len(n)-1] {
j := rnd(len(n)-i) + i
n[i], n[j] = n[j], n[i]
}
return n
}
// PreferentialAttachment constructs a graph in the destination, dst, of order n.
// The graph is constructed successively starting from an m order graph with one
// node having degree m-1. At each iteration of graph addition, one node is added
// with m additional edges joining existing nodes with probability proportional
// to the nodes' degrees. If src is not nil it is used as the random source,
// otherwise rand.Float64 is used for the random number generator.
//
// The algorithm is essentially as described in http://arxiv.org/abs/cond-mat/0110452
// after 10.1126/science.286.5439.509.
func PreferentialAttachment(dst graph.UndirectedBuilder, n, m int, src rand.Source) error {
if n <= m {
return fmt.Errorf("gen: n <= m: n=%v m=%d", n, m)
}
// Initial condition.
wt := make([]float64, n)
for u := 0; u < m; u++ {
if dst.Node(int64(u)) == nil {
dst.AddNode(simple.Node(u))
}
// We need to give equal probability for
// adding the first generation of edges.
wt[u] = 1
}
ws := sampleuv.NewWeighted(wt, src)
for i := range wt {
// These weights will organically grow
// after the first growth iteration.
wt[i] = 0
}
// Growth.
for v := m; v < n; v++ {
for i := 0; i < m; i++ {
// Preferential attachment.
u, ok := ws.Take()
if !ok {
return errors.New("gen: depleted distribution")
}
dst.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
wt[u]++
wt[v]++
}
ws.ReweightAll(wt)
}
return nil
}
|
