-
Notifications
You must be signed in to change notification settings - Fork 10
/
slpa.py
75 lines (57 loc) · 2.09 KB
/
slpa.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
import numpy as np
import networkx as nx
from collections import defaultdict
def find_communities(G,T,r):
"""
Speaker-Listener Label Propagation Algorithm (SLPA)
see http://arxiv.org/abs/1109.5720
"""
##Stage 1: Initialization
memory = {i:{i:1} for i in G.nodes()}
##Stage 2: Evolution
for t in range(T):
listenersOrder = list(G.nodes())
np.random.shuffle(listenersOrder)
for listener in listenersOrder:
speakers = G[listener].keys()
if len(speakers)==0:
continue
labels = defaultdict(int)
for j, speaker in enumerate(speakers):
# Speaker Rule
total = float(sum(memory[speaker].values()))
labels[list(memory[speaker].keys())[np.random.multinomial(1,[freq/total for freq in memory[speaker].values()]).argmax()]] += 1
# Listener Rule
acceptedLabel = max(labels, key=labels.get)
# Update listener memory
if acceptedLabel in memory[listener]:
memory[listener][acceptedLabel] += 1
else:
memory[listener][acceptedLabel] = 1
## Stage 3:
for node, mem in memory.iteritems():
for label, freq in mem.items():
if freq/float(T+1) < r:
del mem[label]
# Find nodes membership
communities = {}
for node, mem in memory.iteritems():
for label in mem.keys():
if label in communities:
communities[label].add(node)
else:
communities[label] = set([node])
# Remove nested communities
nestedCommunities = set()
keys = communities.keys()
for i, label0 in enumerate(keys[:-1]):
comm0 = communities[label0]
for label1 in keys[i+1:]:
comm1 = communities[label1]
if comm0.issubset(comm1):
nestedCommunities.add(label0)
elif comm0.issuperset(comm1):
nestedCommunities.add(label1)
for comm in nestedCommunities:
del communities[comm]
return communities