-
Notifications
You must be signed in to change notification settings - Fork 0
/
SmallWorldGraph.py
64 lines (61 loc) · 2.32 KB
/
SmallWorldGraph.py
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
import RandomGraph
import Graph
import random
import search
class SmallWorldGraph(RandomGraph.RandomGraph):
def __init__(self, vs, k, p):
RandomGraph.RandomGraph.__init__(self, vs)
self.add_regular_edges(k)
self.rewire(p)
#self.customRewire(p)
def rewire(self, p):
edges = list(self.edges())
vertices = self.vertices()
for e in edges:
if random.random() < p:
v, temp = e
self.remove_edge(e)
w = random.choice(vertices)
while (v == w or self.get_edge(v, w) != None):
w = random.choice(vertices)
self.add_edge(Graph.Edge(v, w))
def customRewire(self, p):
edges = list(self.edges())
vertices = self.vertices()
for e in edges:
if random.random() < p:
self.remove_edge(e)
w = random.choice(vertices)
v = random.choice(vertices)
while (v == w or self.get_edge(v, w) != None):
v = random.choice(vertices)
self.add_edge(Graph.Edge(v, w))
def clustering_coefficient(self):
coefficientSum = 0;
for v1 in self:
vertices = self.out_vertices(v1)
verticesN = len(vertices)
if (verticesN < 2):
coefficientSum += 1
continue
possibleEdges = verticesN*(verticesN - 1)/2.0
totalEdges = 0
for i in range(verticesN):
for j in range(i, verticesN):
if(self.get_edge(vertices[i], vertices[j]) != None):
totalEdges += 1
coefficientSum += totalEdges/possibleEdges
return coefficientSum/len(self.vertices())
def avg_path_length(self):
vertices = self.vertices()
verticesLen = len(vertices)
totalPathLen = 0
for v in vertices:
distances = search.dijkstraSearch(self, v)
#distances = search.floydMarshall(self)
# for i in range(verticesLen):
# for j in range(i + 1, verticesLen):
# totalPathLen += distances[i][j]
totalPathLen += sum(distances.values())
verticePairs = (verticesLen - 1)*verticesLen
return totalPathLen/float(verticePairs)