-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDrivers.py
153 lines (116 loc) · 3.86 KB
/
Drivers.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
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
'''
Implements algorithms to find the drivers of a graph.
A driver is a node whose ego-network is not contained in
the ego-network of any other node.
Copyright (C) 2012 Steven Laan
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see http://www.gnu.org/licenses/
'''
import string
import numpy as np
from copy import deepcopy
import networkx as nx
def find_drivers(G):
'''
Finds the lifters and drivers in a graph.
Parameters
----------
G : networkx.Graph
The graph to find the drivers of
Returns
-------
(drivers, peers) : tuple
A tuple containing the drivers and peers of the network.
A driver is a node whose ego-network is not contained in
the ego-network of any other node.
Peers are nodes whose ego-networks coincide. Only one of
the peers is mentioned in the driver set.
'''
nodes = G.nodes()
N = len(nodes)
A = nx.adjacency_matrix(G) + np.eye(N)
items = dict()
driver_candidates = dict()
for i in xrange(N):
items[i] = set([j for j in xrange(N) if A[i,j]])
driver_candidates[nodes[i]] = set()
for i in xrange(N):
# Temporarily remove center
items[i].remove(i)
for j in xrange(N):
if i == j:
continue
# If all items of i are in j, i is a lifter of j
if items[i] < items[j]:
driver_candidates[nodes[j]].add(nodes[i])
# Add center back
items[i].add(i)
drivers = driver_candidates.copy()
peers = dict()
for i in xrange(N):
peers[nodes[i]] = set()
for j in xrange(N):
if i == j:
continue
set_A = items[i] - set([nodes[j]])
set_B = items[j] - set([nodes[i]])
if set_A == set_B:
peers[nodes[i]].add(nodes[j])
elif nodes[i] in driver_candidates[nodes[j]]:
del drivers[nodes[i]]
break
return drivers, peers
def find_drivers_id(G):
'''
Finds the lifters and drivers in a graph.
Parameters
----------
G : networkx.Graph
The graph to find the drivers and lifters of
Returns
-------
drivers : dict
dict containing IDs of the lifters of each driver
'''
nodes = G.nodes()
N = len(nodes)
A = nx.adjacency_matrix(G) + np.eye(N)
items = dict()
driver_candidates = dict()
for i in xrange(N):
items[i] = set([j for j in xrange(N) if A[i,j]])
driver_candidates[i] = set()
for i in xrange(N):
# Temporarily remove center
items[i].remove(i)
for j in xrange(N):
if i == j:
continue
# If all items of i are in j, i is a lifter of j
if items[i] < items[j]:
driver_candidates[j].add(i)
# Add center back
items[i].add(i)
drivers = driver_candidates.copy()
peers = dict()
for i in xrange(N):
peers[i] = set()
for j in xrange(N):
if i == j:
continue
set_A = items[i] - set([j])
set_B = items[j] - set([i])
if set_A == set_B:
peers[i].add(j)
elif i in driver_candidates[j]:
del drivers[i]
break
# TODO: Remove peers to obtain minimal driver set
return drivers, peers